数据结构图的存储，邻接矩阵和邻接表

邻接矩阵和邻接表是两种常用的数据结构图的存储方式。

邻接矩阵是一个二维数组，其中第 i 行第 j 列的值表示节点 i 和节点 j 之间是否存在边，通常用 0 或 1 表示。如果节点 i 和节点 j 之间存在权值为 w 的边，则邻接矩阵的第 i 行第 j 列的值为 w。邻接矩阵的存储需要 O(n^2) 的空间，其中 n 表示节点数，适合于稠密图。

邻接表则是由一个链表数组组成，其中数组中的每个元素对应一个节点，链表中存储该节点所连接的所有节点和边的信息。邻接表的存储需要 O(n+m) 的空间，其中 n 表示节点数，m 表示边数，适合于稀疏图。

因此，在实际应用中，选择邻接矩阵还是邻接表需要根据具体的场景和图的特点进行选择。

相关问题

构造图的邻接矩阵存储结构和邻接表存储结构

邻接矩阵是一种二维数组，其中数组的行和列分别代表图中的顶点，数组元素的值表示这两个顶点之间是否有边。如果顶点i和j之间有边，则邻接矩阵中第i行第j列的元素为1，否则为0。对于无向图来说，邻接矩阵是对称的，即第i行第j列和第j行第i列的元素是相同的。

邻接表是一种链表的形式，其中每个顶点对应一个链表，链表中存储与该顶点相连的其他顶点。邻接表的优点是可以动态地添加或删除边，节省了存储空间。但是，查找任意两个顶点之间是否有边需要遍历链表，效率相对较低。

在实际应用中，邻接矩阵适用于稠密图，而邻接表适用于稀疏图。同时，邻接矩阵更加适合进行矩阵计算（比如矩阵乘法），而邻接表更加适合进行图的遍历。

有向图的邻接矩阵和邻接表存储结构

有向图的邻接矩阵和邻接表存储结构是用于表示有向图中顶点之间相邻关系的两种方法。

1. 邻接矩阵存储结构：
有向图的邻接矩阵是一个n×n的方阵，其中n为图中顶点的个数。对于有向图中的每一条边(i,j)，如果存在，则在邻接矩阵中第i行第j列的位置上标记为1，否则标记为0。如果有权值，则在对应位置上存储权值。邻接矩阵存储结构的空间复杂度为O(n^2)。

2. 邻接表存储结构：
邻接表是由一个一维数组和若干个链表组成，数组中的每个元素表示一个顶点，每个顶点vi的所有邻接点构成一个单链表，链表中的每个元素表示vi的一个邻接点。邻接表存储结构的空间复杂度为O(n+e)，其中e为边的个数。

下面是Python代码示例：

# 邻接矩阵存储结构
class DirectedGraph:
    def __init__(self, vertex_num):
        self.vertex_num = vertex_num
        self.adj_matrix = [[0] * vertex_num for i in range(vertex_num)]

    def add_edge(self, start, end, weight=1):
        self.adj_matrix[start][end] = weight

# 邻接表存储结构
class DirectedGraph:
    def __init__(self, vertex_num):
        self.vertex_num = vertex_num
        self.adj_list = [[] for i in range(vertex_num)]

    def add_edge(self, start, end, weight=1):
        self.adj_list[start].append((end, weight))