Структура данных, чтобы найти компоненты в неориентированных графов в Python

Question

неориентированный граф из представлен в виде пары узлов:

ребер = (А, В), (В, С), (D, Е), (F, E), (G, E), (G, I), (H, G)

Какой должна быть оптимальной структуры данных в Python, чтобы найти компоненты

подъязыка графа дан (например,

(D, E)). Я имею в виду использование глубинного первого поиска в качестве алгоритма поиска.

Answer 1

Вы проверили библиотеку networkx? Если вы не начинаете с нуля, он обеспечивает отличную структуру данных примитивов для графиков всех форм и размеров.

Входит в комплект Graph.subgraph, который вы можете прочитать на here.

Из документов:

>>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc 
>>> G.add_path([0,1,2,3]) 
>>> H = G.subgraph([0,1,2]) 
>>> H.edges() 
[(0, 1), (1, 2)] 

Answer 2

Если вы просто хотите легкую структуру данных, вы можете использовать двусвязную (эффективно неориентированную) пару словарей.

Узел Структура:

{ "имя": "что-то", "соединения": [список подключенных узлов]}

некоторые узлы из ваших данных:

e = {"name": "E"} 
d = {"name": "D"} 
f = {"name": "F"} 
g = {"name": "G"} 

e["connections"] = [d,f,g] 
#... etc with whatever code you want to build the graph itself 

Затем используйте любой алгоритм, который вы хотите. Если вы хотите знать алгоритм, отрегулируйте свой вопрос. Как упоминалось в нем, используйте библиотеку графов, если сможете. Это хорошо протекая территория.