Lekcja – Czy istnieje ścieżka (BFS)

```V = {
'P' : ['K', 'Q', 'H'],
'D1': ['D2','E'],
'D2': ['D1',],
'K' : ['P', 'Q'],
'Q' : ['P', 'K', 'H'],
'H' : ['P', 'Q'],
'E' : ['D1']
}

def is_path_between(V, source, dest):

list_to_check = [source]
list_visited = []

while list_to_check:

current_node = list_to_check.pop(0)
if current_node == dest:
return True
else:
if current_node not in list_visited:
list_visited.append(current_node)
list_to_check.extend(V[current_node])

return False

for s in V.keys():
for d in V.keys():
if s != d:
print(f'Path {s} - {d} - {is_path_between(V, s, d)}')

#%%
V = {
'P' : ['K', 'Q', 'H'],
'D1': ['D2','E'],
'D2': ['D1',],
'K' : ['P', 'Q'],
'Q' : ['P', 'K', 'H'],
'H' : ['P', 'Q'],
'E' : ['D1']
}

def is_path_between(V, source, dest):

list_to_check = [source]
list_visited = []

while list_to_check:

current_node = list_to_check.pop(0)
# optimization 1 - if the destination is in the current node's neighbours
if current_node == dest or dest in V[current_node]:
return True
else:
if current_node not in list_visited:
list_visited.append(current_node)
list_to_check.extend(V[current_node])
# optimization 2 - add to "list_to_check" only nodes
list_to_check.extend( [x for x in V[current_node] if x not in list_visited] )

return False

for s in V.keys():
for d in V.keys():
if s != d:
print(f'Path {s} - {d} - {is_path_between(V, s, d)}')```

Lab

```import csv

network = {}
select_month = 1

with open('data/usa-domestic-flight-2019.csv') as csv_file:
line_count = 0
if line_count == 0:
print(f'Column names are {", ".join(row)}')
line_count += 1
else:
line_count += 1
origin = row
destination = row
month = int(row)

if month != select_month:# or passengers == 0:
continue

if origin not in network.keys():
network[origin] = [destination]
else:
if destination not in network[origin]:
network[origin].append(destination)

current_keys = list(network.keys())
for origin in current_keys:
for destination in network[origin]:
if destination not in network.keys():
network[destination] = []

print(f'Processed {line_count} lines.')
#print(network.keys())

def is_path_between(V, source, dest):

list_to_check = [source]
list_visited = []

while list_to_check:

current_node = list_to_check.pop(0)
if current_node == dest:
return True
else:
if current_node not in list_visited:
list_visited.append(current_node)
list_to_check.extend(V[current_node])

return False

start = 'San Francisco, CA'
stop = 'Vernal, UT'
print(f"connection from {start} to {stop}: {is_path_between(network, start, stop)}")

start = 'Vernal, UT'
stop = 'San Francisco, CA'
print(f"connection from {start} to {stop}: {is_path_between(network, start, stop)}")

start = 'Kotzebue, AK'
stop = 'Danger Bay, AK'
print(f"connection from {start} to {stop}: {is_path_between(network, start, stop)}")```