-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph_traversals.py
65 lines (56 loc) · 1.31 KB
/
graph_traversals.py
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def BFS1(graph,start):
queue = [start]
visited = [start]
while queue:
v = queue.pop(0)
print(v)
for u in graph[v]:
if u not in visited:
visited.append(u)
queue.append(u)
def BFS_distance(graph,start):
queue = [start]
visited = [start]
distances = {k: 0 for k in graph.keys()}
while queue:
v = queue.pop(0)
for u,d in graph[v]:
if u not in visited:
visited.append(u)
queue.append(u)
distances[u] += distances[v] + d
print(distances)
def dfs(graph, start, visited):
visited.append(start)
for v in graph[start]:
if v not in visited:
dfs(graph,v,visited)
return visited
graph1 = {
'A': ['B','S'],
'B': ['A'],
'C': ['S','D','E','F'],
'D': ['C'],
'E': ['C','H'],
'F': ['C','G'],
'G': ['F','H','S'],
'H': ['E','G'],
'S':['A','C','G']
}
# BFS1(graph1,'A')
graph2 = {
'A': [('C',5),('B',5),('E',5)],
'B': [('A',5),('D',3)],
'C': [('A',5),('E',6),('D',4)],
'D': [('B',3),('C',4)],
'E': [('A',5),('C',6)],
}
graph3 = {
'A': [('B',3)],
'B': [('C',6),('D',1),('E',5)],
'C': [('E',6)],
'D': [('E',7)],
'E': [],
}
BFS_distance(graph3,'A')
print(dfs(graph1,'A',[]))