图算法之连通分量

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

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()
0%