Как мне сохранить это в списке смежности для графов в Python?

Question

Предположим, у меня есть текстовый файл, содержащий это:

0 1 4
0 2 3
1 4 7
5 3 8

Столбцы представляют:

1. вершина
2. другая вершина
3. расстояние между этими двумя вершинами.

Например, в первой строке текстового файла 4 - это расстояние между точками 0 и 1.

Так как мне хранить вершины и расстояния в списке смежности в python?

Answer 1

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

Поскольку вы говорите о смежном списке взвешенного графика, вам необходимо определить структуру для хранения обоих vertex а также weight, Теория графов или структура данных способ реализации смежного списка выглядит следующим образом:

class Node():
    def __init__(self, v, w, next=None):
        self.v = v
        self.w = w
        self.next = next
    ...

class LinkedList():
    def __init__(self, head=None)
        self.head = head

    def add_node():
        pass
    ...

Вот Node класс является базовым элементом для составления LinkedList а также LinkedList используется для представления смежного списка одной вершины. Я не реализую целые классы для вас. Смотрите python-связанный список.

Предполагая, что ваш график направлен, смежный список этого графика:

0 -> [1:4]-> [2:3]
1 -> [4:7]
2 -> []
3 -> []
4 -> []
5 -> [3:8]

в котором, 0 -> [1:4] -> [2:3] представляет смежный список вершин 0, который содержит два ребра: 0->1 с весом 4 а также 0->2 с весом 3, [1:4] может быть описано классом Nodeи весь ряд может быть представлен классом LinkedList, Проверьте взвешенный график-смежный список для получения дополнительной информации.

Чтобы представить весь график, вы можете просто использовать список LinkedListнапример,

g = [LinkedList_for_0, LinkedList_for_1, ...]

При таком подходе g[i] будет смежный список вершин i,

Чтобы построить весь граф, вы можете перебрать все ребра:

g = [[] for v in range(number_of_vertex)]
for f, t, w in edges:
    g[f].add_node(Node(t,w))

Выше, как я уже сказал, это более структурированный способ реализации смежного списка. Если вы хотите попрактиковаться в понимании структуры данных и знания теории графов, вы можете попробовать этот способ. Но, на самом деле, в отличие от C/C++array тип (фиксированный размер), питон list это изменчивый тип, вы можете делать такие операции, как добавить, удалить на питоне list, Так LinkedList на самом деле излишне необходимо. Мы можем переопределить эти классы питонским способом:

class Node():
    def __init__(self, v, w):
        self.v = v
        self.w = w

Здесь Node класс не содержит next член. Таким образом, соседний список может быть представлен в виде списка NodeНапример, смежный список вершин 0:

[Node(1,4), Node(2,3)]

И весь граф может быть представлен в виде двумерного списка (Здесь мы предполагаем, что это неориентированный граф.):

[
 [Node(1,4), Node(2,3)],
 [Node(0,4), Node(4,7)],
 [Node(0,3)],
 [Node(5,8)],
 [Node(1,7)],
 [Node(3,8)]
] 

Алгоритм Python Way:

g = [[] for v in range(number_of_vertex)]
for f,t,w in edges:
    g[f].append(Node(t,w))
    g[t].append(Node(f,w))

Примечание: вам нужно добавить новый узел для обоих концов ребра.

На практике, при решении проблем с графами, я считаю, что список ребер или разреженная матрица является наиболее распространенным представлением. Поэтому, если это возможно, я бы посоветовал вам использовать этот вид представления.

Благодарю.

Answer 2

Вложенные словари являются естественным способом представления списков смежности. Словари удобны в этой ситуации, потому что они могут представлять разреженные отображения лучше, чем списки, и обеспечивают эффективный поиск.

adjacency_list = {}
for line in open(file):
    from, to, weight = map(int, line.split())
    adjacency_list.setdefault(from, {})[to] = weight
    adjacency_list.setdefault(to, {})[from] = weight  # for undircted graph add reverse edges

Чтобы получить вес ребра между узлами i а также jпосмотришь adjacency_list.get(i, {}).get(j) (который вернется None если край не существует).

Если вы не хотите иметь дело с setdefault а также getвы можете использовать defaultdict по крайней мере, словарь верхнего уровня. Если вы инициализируете с adjacency_list = defaultdict(dict), тогда установка весов будет просто adjacency_list[from][to] = weight (внутренние словари будут создаваться автоматически при необходимости).

Answer 3

Вы можете использовать этот скрипт для взвешенного графика!

from collections import defaultdict

adj = defaultdict(list)

content = open('input.txt', 'r').readlines()

for line in content:
    u, v, w = map(int, line.strip().split(' '))
    # if edge is on-way
    adj[u].append((v, w))
    # otherwise,
    adj[u].append((v, w))
    adj[v].append((u, w))

Answer 4

Взгляните на библиотеку NetworkX, она потрясающая и простая в использовании.

Из документов вы можете иметь атрибуты ребер, хранящие любое значение интереса - расстояние, в вашем случае:

Края часто имеют данные, связанные с ними. Произвольные данные могут быть связаны с ребрами как атрибут ребра. Если данные являются числовыми, и цель состоит в том, чтобы представить взвешенный график, тогда используйте ключевое слово 'weight' для атрибута. Некоторые из алгоритмов графа, такие как алгоритм кратчайшего пути Дейкстры, используют это имя атрибута, чтобы получить вес для каждого ребра.

Возможная реализация в вашем случае будет:

import networkx as nx

G=nx.Graph()

for line in file:
    a, b, w = map(int, line.strip().split(' '))
    G.add_edge(a, b, weight=w)