邻接矩阵及邻接表存储结构

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

邻接矩阵是指用一个二维数组来存储图的连接情况。如果图中有n个节点，那么邻接矩阵的大小就是n*n。邻接矩阵中第i行第j列的值为1，表示节点i和节点j相连；否则为0。对于无向图，邻接矩阵是一个对称矩阵。

邻接矩阵的优点是方便查找两个节点之间是否有连接关系，时间复杂度为O(1)；缺点是对于稀疏图，浪费空间。

邻接表是指用一个数组来保存节点，每个节点保存一个链表，链表中存储该节点连接的其他节点。对于无向图，每个节点的链表中需要存储与其相连的节点和连接的边；对于有向图，只需要存储与其相连的节点。

邻接表的优点是对于稀疏图节省空间；缺点是查找两个节点是否有连接关系需要遍历链表，时间复杂度为O(n)。

选择邻接矩阵还是邻接表取决于具体应用场景。如果对空间要求不高，需要频繁查询两个节点之间的连接关系，那么使用邻接矩阵比较合适；如果对空间要求较高，需要频繁查询一个节点连接的其他节点，那么使用邻接表比较合适。

相关问题

实现邻接矩阵和邻接表存储结构

这个问题是关于数据结构与算法的，可以回答。邻接矩阵和邻接表是两种常用的图的存储结构。邻接矩阵是通过一个二维数组来表示各个顶点之间的连接情况，如果两个顶点之间有连线则为1，否则为0。邻接表则是通过链表来表示顶点之间的相邻关系，每个顶点对应一个链表，保存与其相邻的顶点。对于稠密图，邻接矩阵更适合存储，而对于稀疏图，邻接表更适合存储。

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

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

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))