forked from psounis/python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathexercise02.py
More file actions
44 lines (35 loc) · 1.17 KB
/
exercise02.py
File metadata and controls
44 lines (35 loc) · 1.17 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from graph import Graph
from queue import Queue
def breadth_first_search(graph, start, finish):
q = Queue()
discovered = [start]
q.enqueue(start)
parent = {}
while len(q) > 0:
v = q.dequeue()
if v == finish:
break
for neighbor in graph.neighbors(v):
if neighbor.descr not in discovered:
discovered += [neighbor.descr]
parent[neighbor.descr] = v
q.enqueue(neighbor.descr)
path = [finish]
while path[0] != start:
path = [parent[path[0]]] + path
print(path)
def main():
facebook_users = Graph()
for user in ["Bob", "Anne", "Elisa", "Diana", "Carl"]:
facebook_users.add_vertex(user)
facebook_users.add_edge("Carl", "Bob")
facebook_users.add_edge("Carl", "Elisa")
facebook_users.add_edge("Carl", "Diana")
facebook_users.add_edge("Diana", "Bob")
facebook_users.add_edge("Diana", "Anne")
facebook_users.add_edge("Elisa", "Anne")
facebook_users.add_edge("Anne", "Bob")
print(facebook_users)
print("\n")
breadth_first_search(facebook_users, "Carl", "Anne")
main()