图-邻接表（链表实现）：`node.next = self.graph[src]`作用及边添加疑问

一、代码node.next = self.graph[src]的功能解析 #

Graph类的self.graph是一个数组，数组下标对应图的顶点，每个元素是AdjNode类型的链表头节点，用来存储该顶点的所有邻接顶点。

add_edge方法用于添加一条从src到dest的有向边，node.next = self.graph[src]这行代码的核心作用是：

• 将新建的dest节点的next指针，指向src顶点当前邻接链表的头节点
• 配合后续的self.graph[src] = node，把新节点设为src邻接链表的新头节点
• 这是典型的头插法添加链表节点，插入效率为O(1)，但邻接顶点的显示顺序会与添加顺序相反（比如先添加1→2，再添加1→3、1→4，输出中顶点1的邻接表会是4 -> 3 -> 2）

二、将顶点3添加到顶点2的后续节点的实现方法 #

要把顶点3设为顶点2的邻接顶点（即添加边2→3），直接调用现有Graph类的add_edge方法即可，传入参数src=2、dest=3：

graph.add_edge(2, 3)

具体执行流程： #

1. 创建存储顶点3的AdjNode实例
2. 执行node.next = self.graph[2]：此时self.graph[2]初始为None（若之前未给顶点2添加邻接边），新节点的next指向None
3. 执行self.graph[2] = node：将顶点2对应的数组元素更新为该新节点，此时顶点2的邻接链表仅包含顶点3的节点
4. 打印时会输出2 -> 3，与给定示例输出中的顶点2邻接表一致

完整实现代码 #

class AdjNode:
    def __init__(self, data):
        self.vertex = data
        self.next = None

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.graph = [None] * self.vertices
    
    def add_edge(self, src, dest):
        node = AdjNode(dest)
        node.next = self.graph[src]
        self.graph[src] = node
    
    def print_graph(self):
        for i in range(self.vertices):
            print("Adjacency list of vertex {}
 {}".format(i,i), end="")
            temp = self.graph[i]
            while temp:
                print(" -> {}".format(temp.vertex), end="")
                temp = temp.next
            print(" \n")               

V = 5
graph = Graph(V)
graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 3)
graph.add_edge(3, 4)

graph.print_graph()

运行输出 #

Adjacency list of vertex 0
 0 -> 4 -> 1 

Adjacency list of vertex 1
 1 -> 4 -> 3 -> 2 

Adjacency list of vertex 2
 2 -> 3 

Adjacency list of vertex 3
 3 -> 4 

Adjacency list of vertex 4
 4 

内容的提问来源于stack exchange，提问作者Heba Allah Hashim