有向图

一、有向图的基本概念

定义：
- 有向图由一组顶点和一组有向边组成，每条有向边连接一个有序顶点对。
- 边有方向，用 v → w 表示从 v 指向 w。
入度和出度：
- 出度：从某顶点指出的边数。
- 入度：指向某顶点的边数。
边的头和尾：
- v → w 中，v 为头，w 为尾。
顶点关系：
- 两个顶点可能有 4 种关系：无边、单向边 v → w、单向边 w → v、双向边。
特殊情况：
- 支持自环（指向自身的边）和平行边（同一方向的多条边），但一般讨论中忽略。

二、术语表

有向路径：
- 一系列顶点，依次通过有向边连接。
- 简单路径：除起点和终点外无重复顶点。
- 长度：路径中的边数。
有向环：
- 起点和终点相同，至少含一条边的路径。
- 简单环：除起点和终点外无重复顶点和边。
可达性：
- 若存在从 v 到 w 的有向路径，则 w 可从 v 达到。
- 约定：每个顶点可达自身。
- 注意：v → w 可达不意味着 w → v 可达，与无向图连通性不同。
有向无环图（DAG）：
- 不含任何有向环的有向图。
强连通：
- 若 v 和 w 互相可达（存在 v → w 和 w → v 的路径），则称强连通。
- 强连通图：任意两顶点都强连通。
强连通分量：
- 图中极大强连通子图。

三、有向图的表示

邻接表：
- 用顶点索引的数组，每个元素是一个链表，存储该顶点指出的邻接顶点。
- 空间复杂度：V + E。
- 添加边时间：常数。
- 查询出边时间：与出度成正比。
区别于无向图：
- 无向图中 v-w 在两顶点的邻接表中都出现；有向图中 v → w 只出现在 v 的邻接表中。
反向图：
- 将所有边的方向反转，生成新图，用于特定算法（如强连通分量计算）。
符号图：
- 用字符串表示顶点名，通过符号表映射到整数索引。

四、图处理算法

单点/多点可达性（DirectedDFS）：
- 问题：从起点 s 或一组起点能否到达顶点 v？
- 方法：深度优先搜索（DFS），标记可达顶点。
- 时间复杂度：V + E。
- 应用：垃圾回收（标记-清除策略）。
单点有向路径：
- 问题：是否存在从 s 到 v 的路径？若有，找出路径。
- 方法：DFS，用 edgeTo[] 记录路径。
- 时间复杂度：V + E。
单点最短有向路径：
- 问题：找出从 s 到 v 的最短路径。
- 方法：广度优先搜索（BFS），用队列逐层探索。
- 时间复杂度：V + E。
有向环检测（DirectedCycle）：
- 问题：图中是否有环？若有，找出环上顶点。
- 方法：DFS，用 onStack[] 跟踪递归栈，检测回边。
- 时间复杂度：V + E。
拓扑排序（Topological）：
- 问题：对有向无环图排序，使所有边从前指向后。
- 方法：
  1. 用 DirectedCycle 检测环，确保是 DAG。
  2. 用 DepthFirstOrder 获取逆后序。
- 时间复杂度：V + E。
- 性质：仅 DAG 可拓扑排序；逆后序即拓扑顺序。
- 应用：任务调度、课程安排。
强连通分量（KosarajuSCC）：
- 问题：找出所有强连通分量。
- 方法：
  1. 在反向图 GR 上用 DFS 获取逆后序。
  2. 在原图 G 上按逆后序 DFS，划分分量。
- 时间复杂度：V + E。
- 应用：网络分析、食物链研究。
顶点对可达性（TransitiveClosure）：
- 问题：任意 v 到 w 是否可达？
- 方法：对每个顶点运行 DirectedDFS，构建传递闭包。
- 时间复杂度：V(V + E)，空间 V²。
- 局限：不适合大型图。

五、深度优先次序（DepthFirstOrder）

前序：递归调用前加入队列。
后序：递归调用后加入队列。
逆后序：递归调用后压入栈。
时间复杂度：V + E。
应用：拓扑排序（逆后序）。

六、算法性能总结

问题	实现方法	时间复杂度
单点/多点可达性	DirectedDFS	V + E
单点路径	DepthFirstDirectedPaths	V + E
单点最短路径	BreadthFirstDirectedPaths	V + E
有向环检测	DirectedCycle	V + E
拓扑排序	Topological	V + E
强连通分量	KosarajuSCC	V + E
顶点对可达性	TransitiveClosure	V(V + E)

八、关键区别与无向图

方向性：有向图边单向，导致可达性不对称。
复杂度：检测路径、环和连通性更复杂。
算法调整：无向图算法需修改方向逻辑。