使用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)]
使用此列表,我想遍历每个顶点,并找到每个相邻的顶点,但是我想按顺序进行。因此,我想得到的是例如一个嵌套列表,其中的i
th子列表包含每个顶点的邻居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]]
,但也可以是另一种排序的数据结构。
但是,由于我的图形可能包含一百万个边和顶点,因此我想实现一个例程,该例程不会在每个顶点上遍历整个列表,因为我想将运行时间保持在较低水平。
有什么方法可以做到这一点?很感谢任何形式的帮助。
您可以使用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]]
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句