强连通分量(strongly connected components, SCCs)是一个能让有向路径上所有节点彼此到达的最大子图。
Kosaraju的查找强连通分量算法
def strongly_connected_components(graph):
transpose_graph = get_transpose_graph(graph)
scc, seen = [], set()
for u in dfs_top_sort(graph):
if u in seen:
continue
component = walk(transpose_graph, u, seen)
seen.update(component)
scc.append(component)
return scc
def get_transpose_graph(graph):
transposed = {}
for u in graph:
transposed[u] = set()
for u in graph:
for v in graph[u]:
transposed[v].add(u)
return transposed
def dfs_top_sort(graph):
visited, res = set(), []
def recurse(u):
if u in visited:
return
visited.add(u)
for v in graph[u]:
recurse(v)
res.append(u)
for u in graph:
recurse(u)
res.reverse()
return res
def walk(graph, start, s=None):
nodes, current = set(), dict()
current[start] = None
nodes.add(start)
while nodes:
u = nodes.pop()
for v in graph[u].difference(current, s):
nodes.add(v)
current[v] = u
return current
graph = {
'a': set('bc'),
'b': set('dei'),
'c': set('d'),
'd': set('ah'),
'e': set('f'),
'f': set('g'),
'g': set('eh'),
'h': set('i'),
'i': set('h'),
}
print(strongly_connected_components(graph))
# [{'a': None, 'd': 'a', 'b': 'd', 'c': 'd'}, {'e': None, 'g': 'e', 'f': 'g'}, {'h': None, 'i': 'h'}]
(最近更新:2019年05月31日)