Pythonアルゴリズムチュートリアル:図の連通成分を探し出す

1つの図構造の連通成分は、その中のすべてのノードを互いに到達させることができる最も大きなサブ図である.

def components(graph):
    component = []
    seen = set()
    for u in graph:
        if u in seen:
            continue
        current = walk(graph, u)
        seen.update(current)
        component.append(current)
    return component


def walk(graph, start, s=set()):
    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('d'),
    'c': set('bd'),
    'd': set(),
}
print(components(graph))

(最近更新:2019年05月31日)