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)
#add neighbours of current node
for x in range(len(structure)):
if structure[current][x] == 1:
list_to_visit.append(x)
#if we visited all nodes it is a tree
return len(list_visited) == len(structure)
print('Structure 1:', is_tree(structure1))
print('Structure 2:', is_tree(structure2))
print('Structure 3:', is_tree(structure3))