創建從EdgeList都鄰居列表（Python的：訪問元組與指定的第一值）

Question

使用NetworkX，我已經獲得描述在圖中的邊（對頂點的）元組的列表：

G = [(1, 2), (1, 3), (1, 4), (2, 4), (3, 8), (4, 5), (8, 15), (5, 6), (5, 7), (6, 17), (7, 11), (7, 15), (7, 16), (17, 12), (11, 12), (11, 13), (15, 9), (15, 10), (16, 9), (9, 18), (18, 13), (18, 14), (10, 14)] 

使用此列表，我想遍歷每個頂點，並找到每個相鄰的頂點，但我想按順序執行此操作。所以我想得到的是例如一個嵌套列表，其中ith子列表包含頂點i的每個鄰居。

Neighbors = [[2, 3, 4], [1, 4], [1, 8], [1, 2, 5], [4, 6, 7], [5, 17], [5, 11, 15, 16], [3, 15], [15, 16, 18], [14, 15], [7, 12, 13], [11, 17], [11, 18], [10, 18], [7, 8, 9, 10], [7, 9], [6, 12], [9, 13, 14]] 

，但它也可以是另一個排序的數據結構。但是，由於我的圖可能包含一百萬條邊和頂點，因此我希望實現一個不會遍歷每個頂點的整個列表的例程，因爲我想保持運行時較低。

有什麼辦法可以達到這個目的嗎？很感謝任何形式的幫助。

Answer 1

可以使用defaultdict如下：

from collections import defaultdict 
d = defaultdict(set) 

for x, y in G: 
    d[x].add(y) 
    d[y].add(x) 

d 
defaultdict(set, 
      {1: {2, 3, 4}, 
      2: {1, 4}, 
      3: {1, 8}, 
      4: {1, 2, 5}, 
      5: {4, 6, 7}, 
      6: {5, 17}, 
      7: {5, 11, 15, 16}, 
      8: {3, 15}, 
      9: {15, 16, 18}, 
      10: {14, 15}, 
      11: {7, 12, 13}, 
      12: {11, 17}, 
      13: {11, 18}, 
      14: {10, 18}, 
      15: {7, 8, 9, 10}, 
      16: {7, 9}, 
      17: {6, 12}, 
      18: {9, 13, 14}}) 

您可以轉換字典到列表：

[sorted(d[k]) for k in range(1, max(d.keys())+1)] 
[[2, 3, 4], 
[1, 4], 
[1, 8], 
[1, 2, 5], 
[4, 6, 7], 
[5, 17], 
[5, 11, 15, 16], 
[3, 15], 
[15, 16, 18], 
[14, 15], 
[7, 12, 13], 
[11, 17], 
[11, 18], 
[10, 18], 
[7, 8, 9, 10], 
[7, 9], 
[6, 12], 
[9, 13, 14]] 

Answer 2

如果您有訪問原始圖形g，您可以通過迭代原始邊緣列表（如果不是，您可以從G構造g）：

[list(v.keys()) for _,e in g.edge.items()] 
#[[2, 3, 4], [1, 4], [8, 1], [1, 2, 5], [4, 6, 7], [17, 5], [16, 11, 5, 15], ...] 

可以省略list()如果您沒有問題dict_keys，這是一個簡單的列表的只讀版本：

[v.keys() for _,e in g.edge.items()] 
#[dict_keys([2, 3, 4]), dict_keys([1, 4]), dict_keys([8, 1]), ...]