python - 如何将其存储在 python 图形的邻接列表中？

Question

假设我有一个包含以下内容的文本文件:

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

列代表:

1. 一个顶点
2. 另一个顶点
3. 这两个顶点之间的距离。

例如，在文本文件的第一行中，4 是点 0 和 1 之间的距离。

那么我如何将顶点和距离存储在 python 的邻接列表中？

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用来表示一个顶点的相邻列表。我不会为您实现整个类(class)。参见 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其实是不必要的。我们可以用 pythonic 方式重新定义这些类:

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))

注意:您需要为边缘的两端添加一个新节点。

在实践中，在处理图形问题时，我认为边列表或稀疏矩阵是最常见的表示形式。所以如果可能的话，我建议你使用这种表示。

谢谢。