Граф соединений в питоне

Question

Я не очень знаком с теорией графов, но я попытаюсь объяснить мою проблему.У меня есть словарь, как это:

{67: [68, 332],
 68: [67],
 265: [266],
 266: [265],
 332: [67, 333],
 333: [332, 334],
 334: [333, 335],
 335: [334, 336],
 336: [335]}

Ключи этого dict являются узлами, а значения являются ребрами графа.Как мы можем найти связанные группы в этом графе?[есть две группы - 265-> 266 и 67 -> ...-> 366]

Answer 1

Похоже, что ваш график ненаправленный, это означает, что для любых двух узлов A и B, если есть ребро от A до B, то есть ребро от B до A. Чтобы найти связанные компоненты графаВы можете просто использовать поиск в глубину .Начните с любого узла и следуйте по краям, пока вы не сможете достичь больше узлов, не нажимая на дубликаты.Это первый подключенный компонент.Затем начните с любого узла, которого вы еще не коснулись, и повторите.Вы закончили, когда достигли всех узлов на графике.

Answer 2

Если вы собираетесь делать много графических вещей и не хотите использовать Sage , я бы просто установил networkx :

>>> import networkx as nx
>>> 
>>> nodes_and_edges = {67: [68, 332], 68: [67], 265: [266],
...                    266: [265], 332: [67, 333],  333: [332, 334],
...                    334: [333, 335], 335: [334, 336],  336: [335]}
>>> 
>>> G = nx.Graph(nodes_and_edges)
>>> G
<networkx.classes.graph.Graph object at 0x11ac510>
>>> nx.connected_components(G)
[[67, 68, 332, 333, 334, 335, 336], [265, 266]]

Answer 3

Полагаю, вы говорите о алгоритме сильно связанных компонентов Тарьяна .

Вот реализация Python, которую я считаю верной. Вам придется преобразовать словарь в список ребер, как в [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'A'), ('A', 'E'), ('C', 'A'), ('C', 'E'), ('D', 'F'), ('F', 'B'), ('E', 'F')]:

import itertools

def strong_connect(vertex):
    global edges, indices, lowlinks, connected_components, index, stack
    indices[vertex] = index
    lowlinks[vertex] = index
    index += 1
    stack.append(vertex)

    for v, w in (e for e in edges if e[0] == vertex):
        if indices[w] < 0:
            strong_connect(w)
            lowlinks[v] = min(lowlinks[v], lowlinks[w])
        elif w in stack:
            lowlinks[v] = min(lowlinks[v], indices[w])

    if indices[vertex] == lowlinks[vertex]:
        connected_components.append([])
        while stack[-1] != vertex:
            connected_components[-1].append(stack.pop())
        connected_components[-1].append(stack.pop())

edges = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'A'), ('A', 'E'), ('C', 'A'), ('C', 'E'), ('D', 'F'), ('F', 'B'), ('E', 'F')]
vertices = set(v for v in itertools.chain(*edges))
indices = dict((v, -1) for v in vertices)
lowlinks = indices.copy()
connected_components = []

index = 0
stack = []
for v in vertices:
    if indices[v] < 0:
        strong_connect(v)

print(connected_components)

Это от этот вопрос .