Как представить графы / деревья в Python и как обнаружить циклы? - PullRequest
9 голосов
/ 14 декабря 2010

Я хочу реализовать алгоритм Крускала в Python. Как мне представить дерево / граф и какой подход следует использовать для обнаружения циклов?

Ответы [ 2 ]

11 голосов
/ 14 декабря 2010

Простейший способ его представления (на мой взгляд) - использование набора массивов списков:

graph = {}
graph[node_id] = [other_node_id for other_node_id in neighbors(node_id)]

Простой способ найти циклы - использовать поиск BF или DF:

def df(node):
    if visited(node):
        pass # found a cycle here, do something with it
    visit(node)
    [df(node_id) for node_id in graph[node]]

Отказ от ответственности: на самом деле это эскиз; neighbors(), visited() и visit() - просто фиктивные элементы, представляющие, как должен выглядеть алгоритм.

4 голосов
/ 14 декабря 2010

Python Graph API - хорошее место для начала.

Например, NetworkX имеет реализацию алгоритма Крускала для поиска минимального остовного дерева.

Если вы хотите заново изобрести колесо и сделать это самостоятельно, это также возможно.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...