如何將它存儲在python圖形的鄰接列表中？

Question

假設我有一個包含這個文本文件：

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

列表示：

1. 頂點
2. 另一個頂點
3. 這兩個頂點之間的距離。

例如，在文本文件中的第一線，4點0和1

之間的距離，因此，如何將我存儲在蟒蛇鄰接表的頂點和距離？

Answer 1

在圖論中，adjacent-list是用於表示圖的無序列表的集合。每個列表描述圖中頂點的一組鄰居。

由於您正在討論加權圖的相鄰列表，因此您需要定義一個結構來存儲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-linked-list。

假設您的圖表定向，該曲線圖的相鄰列表是：

其中

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來表示。請查詢weighted-graph-adjacent-list瞭解更多信息。

爲了表示整個圖中，可以簡單地使用的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類型（固定大小）不同，python list是一種可變類型，您可以在Python中執行添加，刪除操作list。所以LinkedList實際上是不必要的。我們可以在一個Python的方式重新定義這些類：

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是這樣的算法：

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

看看NetworkX圖書館，它真棒，易於使用。

從the docs，你可以有優勢屬性存儲感興趣的任何值 - 距離，你的情況：

邊緣往往與他們相關的數據。 任意數據可以作爲邊緣屬性與邊緣關聯。如果數據是數字，目的是表示加權圖形，那麼使用屬性的「weight」關鍵字。某些圖算法（如Dijkstra的最短路徑算法）使用此屬性名稱來獲取每個邊的權重。

你的情況的一種可能的實現是：

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)