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

邻接矩阵是一种表示图的方法，它使用一个二维数组来存储图中各个顶点之间的边。如果顶点i和顶点j之间有一条边，则邻接矩阵的第i行第j列的元素为1，否则为0。

例如，下面是一个简单的无向图的邻接矩阵：

   0 1 2 3
0  0 1 1 0
1  1 0 0 1
2  1 0 0 1
3  0 1 1 0

代码实现：

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_matrix = [[0]*vertices for i in range(vertices)]

    def add_edge(self, u, v):
        self.adj_matrix[u][v] = 1
        self.adj_matrix[v][u] = 1

邻接表则是另一种表示图的方法，它使用一个列表来存储图中各个顶点之间的边。具体来说，对于每个顶点i，我们都维护一个与之相邻的顶点列表adj_list[i]。

例如，下面是一个简单的无向图的邻接表：

0: 1 2
1: 0 3
2: 0 3
3: 1 2

代码实现：

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_list = [[] for i in range(vertices)]

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

需要注意的是，邻接矩阵的空间复杂度为O(V^2)，而邻接表的空间复杂度为O(V+E)，其中E是边的数量。因此，在空间有限的情况下，邻接表通常是更好的选择。