图算法之连通分量

发表于 更新于
使用深度优先遍历，查看图有多少个连通分量。

连通分量算法可以近似看作一种硬聚类算法，该算法旨在寻找相关数据的簇类。

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
class Components:
    '''
    查找图中所有的连通分量
    '''
    def __init__(self, graph):
        self.graph = graph
        self.count = 0  # 连通子图数量
        self.result = []  # 连通子图

    def dfsTravel(self, source):
        travel = [] 
        stack = [source]
        while stack:
            current = stack.pop()
            if current not in travel:
                travel.append(current)
            for next_adj in self.graph[current]:
                if next_adj not in travel:
                    stack.append(next_adj)
        return travel

    def main(self):
        for vertex in self.graph:
            travel = self.dfsTravel(vertex)
            if set(travel) not in self.result:
                self.result.append(set(travel))
                self.count += 1
        print(self.result)
        print(self.count)

if __name__ == '__main__':

    Graph = {'A':  ['B', 'C', 'D'],
             'B':  ['E'],
             'C':  ['D', 'F'],
             'D':  ['B', 'E', 'G'],
             'E':  [],
             'F':  ['D', 'G'],
             'G':  ['E']}

    c = Components(Graph)
    c.main()