1 基本概念
有向图是由顶点和有向边共同构成的图结构。与无向图强调“双向连接”不同，有向图更重视关系的方向性，因此常用于描述某种从一端指向另一端的联系。由于方向的存在，同一对顶点之间的连通方式会产生不同含义，这也使有向图在建模中具有较强的表达能力。
1.1 顶点与有向边
顶点是有向图中的基本节点，通常记作 \(v\)、\(u\)、\(w\) 等。顶点之间的连接被称为有向边，常写作 \((u, v)\) 或 \(u \to v\)，表示边从 \(u\) 指向 \(v\)。
在语义上，顶点可以代表人、地点、状态、任务或对象，而有向边则可表示“关注”“依赖”“流向”“先后顺序”等关系。边的方向并不只是形式上的区别，它直接决定了信息、资源或影响的传递方向。
1.2 有向图的定义与表示
一个有向图通常记为 \(G=(V,E)\)，其中 \(V\) 为顶点集合，\(E\) 为有向边集合。每条边都对应一个有序顶点对，这意味着边的起点和终点不能交换而不改变其含义。
有向图的定义强调两点：其一，图由有限或可数个顶点组成；其二，边具有明确方向。基于这一点，有向图在图论中形成了与无向图不同的一套术语和性质，例如入度、出度、可达性和强连通性等。
1.2.1 有序对表示法
有向边一般用有序对表示，即 \((u,v)\)。这里的顺序具有决定性：\((u,v)\) 与 \((v,u)\) 表示的是两条不同的边，除非二者同时存在。
这种表示法适合精确表达方向关系，也便于在数学证明和算法处理中统一处理边的起点与终点。若一张图中包含从 \(u\) 到 \(v\) 的边，则称 \(u\) 是 \(v\) 的前驱之一，\(v\) 是 \(u\) 的后继之一。
1.2.2 邻接关系与入度出度
在有向图中，若存在边 \(u \to v\)，则称 \(u\) 与 \(v\) 邻接，但这种邻接是带方向的。为了区分方向性，通常还会分别讨论顶点的入度与出度。
入度指指向某顶点的边数，出度指从该顶点发出的边数。二者反映了一个顶点在图中的“被指向程度”与“外发程度”，在网络分析和算法设计中都很重要。
1.3 简单有向图与多重有向图
简单有向图通常指不含重复边且不含自环的有向图。也就是说，同一对顶点之间最多只有一条方向固定的边，且不存在从某顶点指向自身的边。
多重有向图则允许同一对顶点之间出现多条平行边，这些边可以具有相同或不同的附加属性，例如权值、标签或时间戳。在实际应用中，多重边可用来表达多种关系并存的情形。
1.4 有向图与无向图的区别
有向图与无向图最核心的差异在于边是否具有方向。无向图中的边表示双向可达或对称关系，而有向图中的边仅表示单向关系，因而路径、连通性和遍历方式都更为复杂。
从结构上看，无向图中的一条边通常只需一个无序对来描述；有向图则必须说明起点和终点。从性质上看，无向图的连通概念较为直接，而有向图还要区分强连通、弱连通以及可达性等层面。
2 有向图的结构性质
有向图的结构性质主要围绕方向带来的约束展开。与无向图相比，有向图中的“能否到达”“是否形成闭合路径”“边的流向是否一致”等问题更为突出，这些性质也是判定图结构的重要基础。
2.1 入度与出度
每个顶点都对应一个入度和一个出度。入度反映该顶点从外部接收连接的数量，出度反映它向外发出的连接数量。对于所有顶点而言，图中全部顶点的入度总和等于出度总和，也等于边数。
这一结论来自每条边都同时贡献一个入度和一个出度。它在统计图结构、验证数据完整性以及设计图算法时都有实际意义。
2.2 邻接点与可达性
若存在边 \(u \to v\)，则称 \(v\) 是 \(u\) 的邻接点或后继点，\(u\) 是 \(v\) 的前驱点。对于一条方向明确的边来说，邻接关系并不对称，这也是有向图区别于无向图的基本特征之一。
可达性描述的是从一个顶点出发，沿有向边能否到达另一个顶点。若存在一条有向路径从 \(u\) 到 \(v\)，则称 \(v\) 从 \(u\) 可达。可达性构成了有向图中许多分析问题的核心。
2.3 路径、通路与回路
在有向图中，沿边移动时必须始终遵守边的方向。由此形成的路径、通路和回路，都是研究图结构的重要对象。它们不仅关系到连通性，也影响循环检测、排序和最短路等算法。
2.3.1 有向路径
有向路径是指一串顶点序列，其中相邻两个顶点之间都存在一条方向一致的边，并且这些边的方向与访问顺序相匹配。例如 \(v_1 \to v_2 \to \cdots \to v_k\) 就构成一条从 \(v_1\) 到 \(v_k\) 的有向路径。
若路径中顶点不重复，通常称为简单路径。简单路径在很多理论推导中更便于分析，因为它避免了重复经过同一顶点而形成的复杂环路。
2.3.2 有向回路
有向回路是指一条起点和终点相同的有向路径，且路径长度至少为一条边以上。若回路中的方向连续一致，则说明图中存在某种闭合的流动或循环依赖。
有向回路在实际问题中往往意味着循环关系。例如依赖系统中的循环依赖、状态机中的反馈环等，都会受到回路存在与否的影响。
2.4 环与自环
环通常指图中形成闭合的路径结构，而自环则是特殊情形，即一条边从某顶点指向自身，记作 \((v,v)\)。自环在表示上最为直接，但在一些模型中会被禁止，以避免引入不必要的递归关系。
自环会影响顶点的入度和出度，同时也可能改变图的连通性质和算法表现。在某些场景下，自环可表示自反馈、自引用或自身状态转移。
3 特殊类型的有向图
根据边的分布和连通特征，有向图可以进一步细分为若干特殊类型。这些类型不仅具有明确的结构特征，也常对应特定的应用场景。
3.1 完全有向图
完全有向图指任意两个不同顶点之间都存在双向有向边的有向图。也就是说，对于任意 \(u \neq v\)，既有 \(u \to v\)，也有 \(v \to u\)。
这种图的连接最为密集，常用于作为理论分析中的极端例子。由于任意顶点之间都能直接到达，因此它在可达性和连通性方面表现出最强的性质之一。
3.2 强连通有向图
若有向图中任意两个顶点都能彼此到达，则称该图为强连通有向图。强连通性体现了方向约束下的双向可达，是有向图中最重要的连通概念之一。
强连通有向图说明图中不存在把顶点分割成“只能单向流动”的孤立部分。此类图在通信网络、循环系统和反馈结构中较为常见。
3.2.1 强连通分量
强连通分量是指有向图中的极大强连通子图。这里的“极大”意味着再加入任何其他顶点后，就不再保持强连通。
强连通分量将复杂图分解为若干互不相交的强连通块，是分析有向图结构的重要工具。许多算法都会先求出强连通分量，再在分量层面进行进一步处理。
3.2.2 弱连通性
弱连通性是指忽略边的方向后，图仍然连通。也就是说，把所有有向边当作无向边来看，若整张图成为一个连通图，则原图是弱连通的。
弱连通只关注顶点间是否存在某种连接，而不要求方向上彼此可达。因此，它比强连通更宽松，也更适合描述“结构上相连但流向不对称”的网络。
3.3 DAG（有向无环图）
DAG 是有向无环图的缩写，表示图中不存在任何有向回路。由于没有循环，DAG 在层次结构、依赖关系和流程安排中极其重要。
DAG 的一个显著特点是可以进行拓扑排序。这使得它在任务执行顺序、编译过程、版本依赖等问题中具有广泛用途。
3.3.1 拓扑排序
拓扑排序是将 DAG 的顶点排列成一个线性序列，使得每条边的起点都排在终点之前。这个序列反映了依赖先后关系，是 DAG 的典型应用之一。
若图中存在多个满足条件的排序，则说明拓扑序并不唯一。拓扑排序通常要求图无环，因为一旦出现有向回路，就不可能得到满足所有边方向约束的线性顺序。
3.3.2 依赖关系建模
DAG 常被用来表示依赖关系，例如任务 A 必须先于任务 B 完成，或者模块 X 必须在模块 Y 之前构建。边的方向可以直观表达“先发生”的含义。
这种建模方式简洁清晰，适合描述项目流程、编译顺序、课程先修关系等。由于无环，系统中的依赖层级也更易于分解和管理。
3.4 源点与汇点
源点是出度较大而入度为零的顶点，表示信息或流动从这里开始。汇点则是入度较大而出度为零的顶点，表示流动最终汇聚到这里。
在实际图模型中，源点常对应起始状态、入口节点或起始任务；汇点则常对应终止状态、出口节点或最终结果。一个有向图可以有多个源点和多个汇点，也可能两者都不存在。
4 有向图的表示方法
有向图在计算机中需要通过数据结构保存。不同表示方法在空间占用、查询效率和适用场景上各有特点，因此通常根据图的稠密程度和算法需求进行选择。
4.1 邻接矩阵
邻接矩阵使用一个二维数组表示图中顶点之间的连接关系。若顶点 \(i\) 到顶点 \(j\) 存在边，则矩阵对应位置记为 1、权值或其他标记；否则记为 0 或无穷大。
邻接矩阵的优点是判断两点之间是否有边非常方便，时间复杂度较低；缺点是当顶点很多而边较少时，会占用较多空间。它更适合稠密图或需要频繁查询边存在性的场景。
4.2 邻接表
邻接表为每个顶点维护一个后继顶点列表，列表中记录所有从该顶点出发的边。对于有向图来说，这种结构尤其适合表示出边关系。
邻接表空间利用率较高，适合稀疏图。它在遍历某个顶点的所有后继时效率较好，但判断任意两点之间是否直接相连通常不如邻接矩阵方便。
4.3 关联矩阵
关联矩阵以“顶点—边”的关系为核心进行表示。矩阵的行对应顶点，列对应边，每一项记录该顶点与该边之间的关联方式，例如作为起点、终点或不相关。
这种表示法更接近代数图论中的形式化描述，适用于需要统一分析顶点与边关系的场合。它在理论研究中较常见，但在一般程序实现中使用频率相对较低。
4.4 边集表示
边集表示直接将所有有向边存储为集合或列表，每条边以有序对形式保存。若图中还存在权值、标签等信息，也可一并记录。
这种方法结构简单，适合用于边的批量处理和输入输出。但如果需要频繁查询邻接关系，单纯的边集表示往往不够高效。
5 有向图上的常见算法
围绕有向图，可设计多种基础与进阶算法，用于遍历、排序、分解和路径计算。很多经典图算法在有向图上会呈现出不同于无向图的实现方式。
5.1 深度优先搜索
深度优先搜索是一种沿着一条路径尽可能向深处扩展的遍历方法。在有向图中，DFS 只沿边的方向继续搜索，因此得到的访问顺序会受到方向约束。
DFS 常用于寻找路径、检测回路、求强连通分量以及构造拓扑序等问题。由于它可以递归或借助栈实现，因此在理论和工程中都十分常用。
5.2 广度优先搜索
广度优先搜索按照层次逐步扩展，从起点出发先访问所有一步可达的顶点，再继续访问更远一层的顶点。在有向图中，BFS 依然遵循边的方向前进。
BFS 常用于求单源最短路径的无权情形、检测可达点集以及分层分析。它的层序特征使其特别适合寻找“最少边数”的路径。
5.3 拓扑排序算法
拓扑排序算法用于生成 DAG 的顶点线性序列，使所有边都从前面的顶点指向后面的顶点。若图中存在环，则拓扑排序一般无法完成或无法满足要求。
拓扑排序既是理论工具，也是实际调度中的核心方法。常见实现方式主要有两类：基于入度的方法和基于 DFS 的方法。
5.3.1 基于入度的算法
基于入度的拓扑排序通常从所有入度为零的顶点开始，将它们依次加入序列，并在删除这些顶点后更新相邻顶点的入度。若某些顶点最终无法被处理，则说明图中存在回路。
这种方法实现直观，适合处理任务依赖和课程安排等问题。它常通过队列维护当前可选顶点，因此也被称为一种“层层剥离”的过程。
5.3.2 基于 DFS 的算法
基于 DFS 的拓扑排序先对图进行深度优先遍历，再按照顶点的完成时间逆序输出结果。完成时间较晚的顶点通常依赖于较早完成的顶点，因此逆序后可形成合法序列。
该方法实现简洁，也便于与回路检测结合使用。若在 DFS 中发现回边，则可判断图中存在有向环，从而中止拓扑排序。
5.4 强连通分量算法
强连通分量算法用于将有向图分解为若干强连通块。分解之后，原图可压缩成一个分量图，通常成为 DAG，便于进一步分析。
这类算法的关键目标是高效识别“互相可达”的顶点集合。经典方法包括 Kosaraju 算法和 Tarjan 算法。
5.4.1 Kosaraju 算法
Kosaraju 算法通常分两次 DFS 完成。第一次在原图上按完成时间排序，第二次在转置图上按逆序处理顶点，从而逐个找出强连通分量。
该算法思想清晰，便于理解强连通分量与转置图之间的关系。其核心依据是完成时间顺序能帮助定位分量的处理先后。
5.4.2 Tarjan 算法
Tarjan 算法使用一次 DFS 便可求出所有强连通分量。它通过维护栈、时间戳和低链接值，判断哪些顶点属于同一个分量。
这一算法以效率高和实现紧凑著称，适合处理大规模图。由于其只需一次遍历，常被视为强连通分量问题的经典解法之一。
5.5 最短路径相关算法
有向图中的最短路径问题关注从一个顶点到另一个顶点沿方向前进时的最小代价。代价可以是边数、距离、时间或权重之和。
常见算法包括适用于无权图的 BFS，以及适用于带权图的 Dijkstra 算法、Bellman-Ford 算法等。由于边具有方向，路径是否存在、是否可行以及最短代价都可能与无向图明显不同。
6 有向图的应用
有向图的实用价值很高，许多现实系统都可自然抽象为有向图。其核心优势在于能够清晰表达方向、层级和依赖，从而便于分析与优化。
6.1 计算机网络与路由
在计算机网络中，数据包传输路径、转发方向和可达关系都可用有向图描述。节点代表设备或路由点，边代表数据流的可能方向。
路由问题常与最短路径、可达性和负载分配相关。通过有向图建模，能够更直观地分析信息如何在网络中单向或双向传播。
6.2 程序控制流与依赖分析
程序执行中的控制流可以用有向图表示，例如基本块之间的跳转关系、函数调用关系以及条件分支走向。编译器和静态分析工具常使用这类结构来检查程序行为。
依赖分析则关注模块、变量、表达式之间的先后约束。若存在循环依赖，往往需要额外处理，因此有向图在程序设计和构建系统中非常关键。
6.3 数据库与关系建模
在数据库设计中，有向图可用于表示实体之间的引用关系、外键依赖和层级结构。某些记录只能依赖另一些记录存在，这种方向性很适合用图来表达。
关系建模时，有向图还能帮助刻画流程型数据或状态转换型数据，特别是在需要分析记录演化顺序的场景中较为有用。
6.4 交通与物流系统
交通网络中的道路单行方向、航线安排、运输路线等都可以抽象为有向图。节点代表站点、路口或仓库，边则代表允许通行或运输的方向。
在物流系统中，有向图可辅助规划配送路径、仓储转运流程和节点间的货物流向。若边带有权值，还能进一步支持成本、时间和容量分析。
6.5 社会网络与信息传播
在社会网络中，关注关系、点赞流向、引用关系等通常具有方向性，因此常用有向图表示。一个用户指向另一个用户的边，可以代表单向关注或信息传播可能。
信息传播模型也常基于有向图展开。边的方向说明消息、影响或行为是否能够从一个节点传递到另一个节点，这有助于研究扩散路径和影响范围。
6.6 任务调度与项目管理
项目管理中的任务先后顺序天然适合用有向图建模。若任务 A 必须先完成，任务 B 才能开始，则可用一条从 A 指向 B 的边表示。
这种结构常与 DAG 和拓扑排序结合使用，以安排合理的执行次序。通过分析源点、汇点和依赖链，还可以识别关键路径和瓶颈环节。
7 有向图的理论扩展
有向图不仅是一种应用模型，也构成了许多理论研究的基础。围绕可达性、序关系、结构等主题，图论发展出了一系列更深入的分析工具。
7.1 可达性与传递闭包
可达性研究从一个顶点出发，沿有向边最终能到达哪些顶点。若将所有间接可达关系也补充到图中，就得到传递闭包。
传递闭包有助于快速判断任意两点之间是否存在路径。它在数据库查询、依赖分析和图算法优化中都具有理论与实践价值。
7.2 偏序与有向无环图
偏序关系具有自反、反对称和传递等性质，而 DAG 常被用来表示偏序结构中的“先于”关系。若将顶点视为元素，边视为局部先后约束，则图中无环特性与偏序的反对称性相呼应。
因此，DAG 不只是工程上的便利模型，也是在形式化描述顺序关系时的重要工具。许多层次结构和排序问题都可以借此建立统一框架。
7.3 图同构与结构判定
图同构关注的是两个图是否在结构上完全等价，即能否通过重新命名顶点使边关系一一对应。对于有向图而言，方向信息增加了判定难度，也使结构比较更加精细。
结构判定常用于分析网络模式、识别重复子结构或比较不同系统的拓扑特征。虽然一般情形下图同构判定较为复杂，但在特定类别的有向图中往往可以得到更有效的判断方法。
7.4 随机有向图
随机有向图是通过随机机制生成边集合的一类模型，常用于研究大规模网络的统计性质。顶点数、边概率和方向分布等参数会影响图的整体特征。
这类模型有助于分析连通阈值、环的出现概率、度分布和传播行为。它们为真实网络提供了简化而可分析的参照框架。
7.5 有向图的谱性质
有向图的谱性质通常与其矩阵表示，尤其是邻接矩阵的特征值和特征向量有关。谱信息能够反映图的整体结构、路径分布以及某些稳定性特征。
在有向图中，由于矩阵往往不是对称的，谱分析比无向图更复杂。尽管如此，谱方法仍然是研究网络结构、动力系统和传播过程的重要工具。