forked from jainaman224/Algo_Ds_Notes
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Breadth_First_Search.py
69 lines (54 loc) · 1.2 KB
/
Breadth_First_Search.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
66
67
68
69
from collections import deque
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = [[] for _ in xrange(num_vertices)]
def addEdge(self, source, destination):
self.adj_list[source].append(destination)
def bfs(self, start):
visited = [False] * self.num_vertices
queue_vertex = deque([])
visited[start] = True
queue_vertex.append(start)
while len(queue_vertex) != 0:
current = queue_vertex.popleft()
print current,
for vertex in self.adj_list[current]:
if (not visited[vertex]):
visited[vertex] = True
queue_vertex.append(vertex)
def main():
# Create a graph with 8 vertices
nodes = int(input())
graph = Graph(nodes)
# Create arcs
edges = int(input())
for i in range(edges):
u, v = map(int, raw_input().split())
graph.addEdge(u, v)
print "Breadth First Traversal is:",
graph.bfs(0)
print ""
if __name__ == '__main__':
main()
"""
Input:
8
14
0 1
0 2
1 2
1 4
2 0
2 3
3 3
3 6
4 0
4 5
5 6
5 7
6 2
7 3
Output:
Breadth First Traversal is: 0 1 2 4 3 5 6 7
"""