ACM-ICPC-Algorithms/BFS/python/bfs.py at e3f9a7c8c329f89fe69a4d742127d4c9d64ccc1c · SVUCE-Programmers/ACM-ICPC-Algorithms · GitHub

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
from collections import defaultdict


class Graph():
    def __init__(self, numberOfNode):
        self.graph = defaultdict(list)
        self.visited = [False] * numberOfNode

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def BFS(self, node):
        queue = [node]
        self.visited[node] = True

        while queue:
            currentNode = queue.pop(0)
            print(currentNode)

            children = self.graph[currentNode]
            for child in children:
                if not self.visited[child]:
                    queue.append(child)
                    self.visited[child] = True


if __name__ == '__main__':
    graph = Graph(5)

    # Add edges to vertex 0, 1, 2, 3 and 4
    graph.addEdge(0, 1)
    graph.addEdge(0, 3)
    graph.addEdge(1, 2)
    graph.addEdge(1, 3)
    graph.addEdge(2, 1)
    graph.addEdge(2, 3)
    graph.addEdge(3, 1)
    graph.addEdge(3, 2)
    graph.addEdge(3, 4)

    print("Breadth First Search starting from vertex 0:")
    graph.BFS(0)