实现图的邻接矩阵和邻接表的存储

邻接矩阵是一种将图中各个节点之间的关系用矩阵形式存储的方式，可以使用二维数组来实现。

假设有一个有向图，其中有5个节点，节点编号为0~4，邻接矩阵的实现方式如下：

# 初始化邻接矩阵
n = 5  # 节点数
graph = [[0] * n for _ in range(n)]

# 添加边
graph[0][1] = 1
graph[0][3] = 1
graph[1][2] = 1
graph[1][4] = 1
graph[2][0] = 1
graph[3][4] = 1
graph[4][2] = 1

# 打印邻接矩阵
for i in range(n):
    for j in range(n):
        print(graph[i][j], end=" ")
    print()

输出结果为：

0 1 0 1 0 
0 0 1 0 1 
1 0 0 0 0 
0 0 0 0 1 
0 0 1 0 0 

其中，`graph[i][j]`表示节点i到节点j是否有边相连，1表示有，0表示没有。

邻接表是一种将图中各个节点之间的关系用链表形式存储的方式，可以使用数组和链表来实现。

假设有一个有向图，其中有5个节点，节点编号为0~4，邻接表的实现方式如下：

# 定义邻接表节点
class AdjNode:
    def __init__(self, val):
        self.val = val
        self.next = None

# 定义图
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [None] * self.V

    # 添加边
    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.V):
            print("Adjacency list of vertex {}\n head".format(i), end="")
            curr_node = self.graph[i]
            while curr_node:
                print(" -> {}".format(curr_node.val), end="")
                curr_node = curr_node.next
            print()

# 创建图
graph = Graph(5)
graph.add_edge(0, 1)
graph.add_edge(0, 3)
graph.add_edge(1, 2)
graph.add_edge(1, 4)
graph.add_edge(2, 0)
graph.add_edge(3, 4)
graph.add_edge(4, 2)

# 打印邻接表
graph.print_graph()

输出结果为：

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

其中，`graph[i]`表示节点i的邻接表，`graph[i].val`表示i的一个邻居节点，`graph[i].next`表示i的下一个邻居节点。