有向图的邻接矩阵和邻接表

在图论中，有向图（Directed Graph）是一种特殊的数据结构，用于表示一组节点（顶点）之间的有方向的连接。有两种常见的数据结构用于表示有向图：邻接矩阵和邻接表。

**1. 邻接矩阵**:
邻接矩阵是一个二维数组，其中的行代表源节点，列表示目标节点。对于有向图中的每条边 (u, v)，矩阵中的元素 A[u][v] 将为 1（或非零值），表示从 u 到 v 有一条有向边。如果不存在这条边，则 A[u][v] 通常为 0 或空。邻接矩阵适合于以下情况：
- 求解路径查询或判断两点间是否有路径时，时间复杂度为 O(1)。
- 当图的边数相对较多且稠密时，空间效率较高。

**2. 邻接表**:
邻接表则是一个链表数组，每个节点对应一个顶点，链表里存储的是所有指向该节点的边。对于每条边 (u, v)，邻接表会有一个链表，其中包含指向从 u 出发到 v 的边的信息。邻接表的主要优点和适用场景是：
- 空间效率高，特别适用于稀疏图，即边的数量远小于节点数量的平方。
- 插入和删除边的时间复杂度通常为 O(1)，因为只需要更新对应的链表。
- 对于求解路径查询，如果使用深度优先搜索（DFS）或广度优先搜索（BFS），邻接表的表现更好，因为它们不需要预先计算所有可能的路径。

**相关问题--:**
1. 邻接矩阵如何表示无向图？
2. 什么情况下会选择邻接表而不是邻接矩阵？
3. 如何在邻接表中查找某个顶点的所有出边？

相关问题

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

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

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

图的邻接矩阵和邻接表

图是一种非线性数据结构，邻接矩阵和邻接表是两种表示图的方式。

邻接矩阵是用一个二维数组来表示图的。对于无向图而言，邻接矩阵是对称的，而对于有向图而言则不一定对称。如果图中有n个节点，那么邻接矩阵就是一个n * n的矩阵。如果节点i到节点j之间有边，则邻接矩阵中第i行第j列的元素为1，否则为0。对于带权图而言，邻接矩阵中的元素可以表示边的权值。

邻接表则是由一组链表来表示图的。对于图中的每个节点，邻接表中都有一个对应的链表，链表中存储该节点所连的所有边的信息。对于无向图而言，邻接表中的每条边都会在两个节点对应的链表中出现。因为邻接表只存储实际存在的边，所以它通常比邻接矩阵更省空间。