如何使用邻接表构造有向图

邻接表是一种常用的图的存储结构，可以用来表示有向图。下面是构造有向图的邻接表的步骤：

1. 定义一个包含 n 个链表的数组，其中 n 是图中的节点数。
2. 对于每个节点 i，创建一个链表，用于存储所有从节点 i 出发的边。链表中的每个元素存储一个有向边的终点和权重（如果有的话）。
3. 遍历所有的有向边 (i, j)，将 j 添加到节点 i 的链表中。
4. 构造完成后，可以通过遍历每个节点的邻接表来访问有向图中的所有节点和边。

下面是一个示例代码，用于构造具有 5 个节点和 6 条有向边的有向图的邻接表。

# 定义邻接表
graph = [[] for i in range(5)]

# 添加有向边
graph[0].append((1, 3))
graph[0].append((2, 2))
graph[1].append((2, 1))
graph[1].append((3, 4))
graph[2].append((3, 1))
graph[4].append((3, 5))

# 打印邻接表
for i in range(5):
    print("Node", i, ":", graph[i])

输出结果为：

Node 0 : [(1, 3), (2, 2)]
Node 1 : [(2, 1), (3, 4)]
Node 2 : [(3, 1)]
Node 3 : []
Node 4 : [(3, 5)]

可以看到，节点 0 有两条边分别指向节点 1 和节点 2，节点 1 有两条边分别指向节点 2 和节点 3，节点 2 有一条边指向节点 3，节点 3 没有出边，节点 4 有一条边指向节点 3。