利用邻接表存储有向图

邻接表是一种常见的图的存储方式，它用一个数组来存储图中的所有顶点，对于每个顶点，用一个链表来存储所有指向它的边。下面是一个示例代码：

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class Graph:
    def __init__(self, n):
        self.n = n
        self.adj = [None] * n

    def add_edge(self, u, v):
        node = Node(v)
        node.next = self.adj[u]
        self.adj[u] = node

    def print_graph(self):
        for i in range(self.n):
            print(f"Vertex {i}: ", end="")
            node = self.adj[i]
            while node:
                print(f"{node.val} -> ", end="")
                node = node.next
            print("None")

以上代码中，Node 类表示链表中的节点，Graph 类表示图。在 Graph 类中，`n` 表示图的顶点数，`adj` 是一个长度为 `n` 的数组，用于存储每个顶点的链表头。`add_edge` 方法用于添加一条从顶点 `u` 指向顶点 `v` 的边，它将 `v` 添加到 `u` 的链表头中。`print_graph` 方法用于打印整个邻接表。

下面是一个示例代码，用于创建一个有向图并输出它的邻接表：

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.print_graph()

输出结果为：

Vertex 0: 4 -> 1 -> None
Vertex 1: 4 -> 3 -> 2 -> None
Vertex 2: 3 -> None
Vertex 3: 4 -> None
Vertex 4: None

其中每一行表示一个顶点及其指向的顶点。例如第一行表示顶点 0 指向顶点 4 和顶点 1。