有向图 有向图是图论中一个基础且重要的扩展概念。与之前讨论的无向图不同，有向图中的边具有方向性。下面我将为你详细讲解。 基本定义 一个有向图 D 由一个有序二元组 (V, A) 构成。 V 是一个非空集合，其元素称为顶点或节点。 A 是一个由 V 中元素的有序对构成的集合，其元素称为弧或有向边。 一条有向边通常记作 (u, v)，其中 u 称为弧尾（起点），v 称为弧头（终点）。这意味着关系是从 u 指向 v 的。在图形表示中，我们用一条带箭头的线从 u 指向 v 来表示。 相关术语 由于边的方向性，有向图中的一些概念比无向图更复杂： 出度 ：对于顶点 v，以其为起点的有向边的数量称为 v 的出度。 入度 ：对于顶点 v，以其为终点的有向边的数量称为 v 的入度。 邻接点 ：如果存在一条有向边 (u, v)，则称 v 是 u 的直接后继（或外邻接点），u 是 v 的直接前驱（或内邻接点）。 有向路径 ：一个顶点和边的交替序列 P = v0, a1, v1, a2, v2, ..., ak, vk，其中每条边 ai = (v{i-1}, vi)。即路径中每条边的方向都必须与序列的方向一致。 有向环 ：起点和终点相同且长度大于零的有向路径称为有向环或圈。 强连通性 ：如果有向图 D 中任意两个顶点 u 和 v 之间，都存在一条从 u 到 v 的有向路径，同时也存在一条从 v 到 u 的有向路径，则称 D 是强连通的。这与无向图中的连通性不同，要求是双向可达的。 表示方法 有向图同样可以使用邻接矩阵和邻接表来表示，但需要体现方向信息。 邻接矩阵 ：对于一个有 n 个顶点的有向图，其邻接矩阵 M 是一个 n×n 的矩阵。矩阵元素 M[ i][ j] 的值表示从顶点 i 到顶点 j 的有向边的数量（对于简单图，通常是 0 或 1）。注意，在有向图中，邻接矩阵通常是非对称的，即 M[ i][ j] 不一定等于 M[ j][ i ]。 邻接表 ：为每个顶点维护一个链表，但通常只记录从该顶点 出发 所能直接到达的顶点（即其直接后继），这样可以节省空间。 特殊类型的有向图 有向无环图 ：顾名思义，即不包含任何有向环的有向图。这是非常重要的一类图，在任务调度、项目管理和编译优化等领域有广泛应用。在一个 DAG 中，我们可以进行拓扑排序，即生成一个顶点的线性序列，使得对于任何一条有向边 (u, v)，u 在序列中都出现在 v 之前。 竞赛图 ：在完全图的基础上，为每一条无向边任意指定一个方向而得到的有向图。也就是说，任意两个不同的顶点之间都有且仅有一条有向边相连。竞赛图常用于表示循环赛的结果。 与无向图的区别与深化 理解有向图的关键在于时刻牢记方向的存在，这导致了许多性质的根本改变。 路径和连通性 ：在无向图中，如果存在从 u 到 v 的路径，则必然存在从 v 到 u 的路径。但在有向图中，这并不成立，因此产生了强连通、弱连通（如果将边视为无向后图是连通的）等概念。 度的概念 ：无向图中顶点的度是一个统一的标量，而有向图中则必须区分入度和出度。 算法差异 ：之前学过的一些算法，如深度优先搜索和广度优先搜索，可以自然地应用到有向图上，但其结果和解释（比如遍历树的结构）会因方向而不同。一些经典算法，如寻找强连通分量的 Kosaraju 算法或 Tarjan 算法，则是专门为有向图设计的。 有向图极大地扩展了图的建模能力，能够描述现实世界中大量具有方向性的关系，如网页链接、交通单行道、任务依赖关系、食物链等。