如何将它存储在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)