Графические соединения в python

Question

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

{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. Чтобы найти связанные компоненты графа , вы можете просто использовать depth-first search. Начните с любого узла и следуйте по краям, пока вы не сможете достичь большего количества узлов, не нажимая дубликатов. Это первый подключенный компонент. Затем начните с любого узла, который вы еще не коснулись, и повторите. Вы закончили, когда достигли всех узлов на графике.

Answer 2

Думаю, вы говорите о Tarjan's strongly connected components algorithm.

Это реализация 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) 

Это от this question.

Answer 3

Если вы собираетесь делать много вещей графа и не хотят накладных расходов с помощью 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]]