Algorithms/connectCompBfs.py at main · debopriyobhowmick/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
43
44
45
# Program to find the number of connected components of a graph

# Instance of a graph stored as adjacency list using dictionary
# Keys : Nodes
# Values : Neighbours

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': ['G'],
    'G': [],
    'H': [],
    'I': ['J'],
    'J': []

}


def ccbfs(graph, start_node):
    vertices = graph.keys()
    explored = []
    queue = [start_node]
    cc = 0
    for index, node in enumerate(vertices):
        if node not in explored:
            cc += 1
            while queue:
                search = queue.pop(0)
                for neighbors in graph[search]:
                    if neighbors not in explored:
                        explored.append(neighbors)
                        queue.append(neighbors)
    return  cc

comp = ccbfs(graph, 'A')
print(comp)