Lekcja  – Wyszukiwanie Depth First Search (DFS)

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

def is_path_betweenBFS(V, source, dest):

list_to_check = [source]
list_visited = []

while list_to_check:

current_node = list_to_check.pop(0)
if current_node == dest:
print('Found!', current_node)
return True
else:
if current_node not in list_visited:
print('Checking', current_node)
list_visited.append(current_node)
list_to_check.extend(V[current_node])

return False

def is_path_betweenDFS(V, source, dest):

list_to_check = [source]
list_visited = []

while list_to_check:

current_node = list_to_check.pop(0)
if current_node == dest:
print('Found!', current_node)
return True
else:
if current_node not in list_visited:
print('Checking', current_node)
list_visited.append(current_node)
list_to_check = V[current_node] + list_to_check

return False

print(is_path_betweenDFS(V, 'E', 'H'))
print(is_path_betweenBFS(V, 'E', 'H'))```

Lab

```names = ['1 CEO', '2 Cognitive', '2 Systems', '2 Operations','3 Healthcare',
'3 Cloud', '3 Research', '3Security', '3 Storage']

structure1 = [
[0,1,1,1,0,0,0,0,0],
[0,0,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0]
]

structure2 = [
[0,1,1,1,0,0,0,0,0],
[0,0,0,0,1,1,1,0,0],
[0,1,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0]
]

structure3 = [
[0,1,1,0,0,0,0,0,0],
[0,0,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0]
]

# only one starting node
def get_root(structure):

the_root = None
#review all columns
for c in range(len(structure)):
#chek how many parents the node has
number_of_parents = 0
for r in range(len(structure)):
number_of_parents += structure[r][c]
#if the node hasn't parents, it is the root
if number_of_parents == 0:
the_root = c
break
#return found root or none
return the_root

def is_tree(structure):
# get the root, if there is no root, it is not a tree
the_root = get_root(structure)
if the_root == None:
return False

#visit all nodes, each node should be visited exactly one time
list_visited = []
list_to_visit = [the_root]

while list_to_visit:
current = list_to_visit.pop()
print(names[current])
#if the node was already visited it is not a tree
if current in list_visited:
return False
list_visited.append(current)