一、有向图的定义
有向图是图的重要类型，由顶点集合和有向边集合组成，其中每条边都有明确的方向，仅能从一个顶点指向另一个顶点。若存在一条从顶点u指向顶点v的边，可表示为<u, v>，该边仅允许从u到v的通行，反之不成立。
资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf
有向图可形式化表示为G=(V, E)，其中：
V是顶点的非空有限集合；E是有向边的有限集合，每条边关联V中两个有序顶点（允许存在自环边，即<u, u>形式的边）。
二、有向图的核心概念
1. 顶点的度
有向图中顶点的度分为入度和出度：
- 入度：记为
indeg(v)，指以顶点v为终点的有向边数量； - 出度：记为
outdeg(v)，指以顶点v为起点的有向边数量； - 顶点的总度数为入度与出度之和，且有向图所有顶点的入度之和等于出度之和，均等于边数
|E|。
2. 路径与环
- 有向路径：从顶点
u到v的顶点序列v₀=u, v₁, v₂, ..., vₖ=v，其中每个相邻顶点对<vᵢ, vᵢ₊₁>都存在有向边，路径长度为边的数量； - 简单路径：路径中所有顶点互不重复的有向路径；
- 有向环：起点和终点为同一顶点、长度≥1且顶点不重复（除起点终点）的有向路径，例如
<A,B>,<B,C>,<C,A>构成一个有向环； - 有向无环图（DAG）：不存在有向环的有向图，是拓扑排序的核心应用对象。
3. 连通性
有向图的连通性比无向图更复杂，主要分为两种：
- 强连通：若对于图中任意两个顶点
u和v，既存在从u到v的有向路径，也存在从v到u的有向路径，则称该有向图为强连通图； - 强连通分量：非强连通有向图中，每个最大的强连通子图称为强连通分量；
- 弱连通：若忽略边的方向后，有向图变为连通的无向图，则称该有向图为弱连通图。
4. 完全有向图
若对于有向图中任意两个不同顶点u和v，同时存在<u, v>和<v, u>两条有向边，则称为完全有向图。包含n个顶点的完全有向图，边数为n(n-1)。
三、有向图的存储方式
1. 邻接矩阵
用n×n的二维数组adj存储（n为顶点数），其中adj[i][j]表示是否存在从顶点i指向j的有向边：
- 若
adj[i][j]=1（或边的权重），表示存在有向边<i,j>； - 若
adj[i][j]=0（或无穷大），表示不存在该有向边； - 有向图的邻接矩阵非对称，即
adj[i][j]与adj[j][i]无必然相等关系。
优缺点：
- 优点：查询两顶点间是否存在指定方向边的时间复杂度为
O(1)，实现简单； - 缺点：空间复杂度为
O(n²)，稀疏图会造成大量空间浪费。
2. 邻接表
为每个顶点维护一个链表（或数组），存储该顶点指向的所有邻接顶点。整体为数组adj，其中adj[v]是顶点v的出边邻接顶点列表。
若需快速查询入边，可额外维护逆邻接表，存储以每个顶点为终点的所有起点。
优缺点：
- 优点：空间复杂度为
O(|V|+|E|)，适合稀疏图，遍历顶点出边效率高； - 缺点：查询从
u到v是否存在有向边的时间复杂度为O(outdeg(u))。
四、有向图的核心算法
1. 深度优先搜索（DFS）
与无向图DFS逻辑类似，但需遵循边的方向，仅能沿有向边遍历。可用于有向环检测和强连通分量求解（如Tarjan算法）。
- 时间复杂度：邻接矩阵存储为
O(n²)，邻接表存储为O(|V|+|E|)。
2. 广度优先搜索（BFS）
按层遍历有向图，仅能沿有向边扩散，可用于求解有向无权图的单源最短路径。
- 时间复杂度：邻接矩阵存储为
O(n²)，邻接表存储为O(|V|+|E|)。
3. 拓扑排序
拓扑排序是对有向无环图（DAG）顶点的一种线性排序，满足：若存在有向边<u, v>，则排序中u一定在v之前。
- 常用算法：Kahn算法（基于入度的贪心算法）、DFS逆序法；
- 应用场景：任务调度、课程安排、依赖关系解析等。
4. 关键路径
针对带权有向无环图，关键路径是从起点到终点的最长路径，决定了整个工程的最短完成时间，常用于项目进度规划。
五、有向图的实现示例
1. 邻接表实现（含拓扑排序）
fromcollectionsimportdequeclassDirectedGraph:def__init__(self,num_vertices):self.num_vertices=num_vertices# 邻接表：存储出边self.adj_list=[[]for_inrange(num_vertices)]# 入度数组self.indegree=[0]*num_verticesdefadd_edge(self,u,v):"""添加有向边<u, v>"""ifvnotinself.adj_list[u]:self.adj_list[u].append(v)self.indegree[v]+=1defremove_edge(self,u,v):"""删除有向边<u, v>"""ifvinself.adj_list[u]:self.adj_list[u].remove(v)self.indegree[v]-=1defdfs(self,start,visited=None):"""深度优先搜索"""ifvisitedisNone:visited=[False]*self.num_vertices visited[start]=Trueprint(start,end=" ")forneighborinself.adj_list[start]:ifnotvisited[neighbor]:self.dfs(neighbor,visited)defbfs(self,start):"""广度优先搜索"""visited=[False]*self.num_vertices queue=deque([start])visited[start]=Truewhilequeue:vertex=queue.popleft()print(vertex,end=" ")forneighborinself.adj_list[vertex]:ifnotvisited[neighbor]:visited[neighbor]=Truequeue.append(neighbor)deftopological_sort(self):"""Kahn算法实现拓扑排序，返回拓扑序列"""queue=deque()# 初始化队列：入度为0的顶点foriinrange(self.num_vertices):ifself.indegree[i]==0:queue.append(i)topo_order=[]whilequeue:u=queue.popleft()topo_order.append(u)# 遍历u的出边，减少邻接顶点入度forvinself.adj_list[u]:self.indegree[v]-=1ifself.indegree[v]==0:queue.append(v)# 若拓扑序列长度不等于顶点数，说明存在环iflen(topo_order)!=self.num_vertices:return"图中存在有向环，无法进行拓扑排序"returntopo_order使用示例
# 初始化6个顶点的有向图（顶点0-5，模拟课程依赖）graph=DirectedGraph(6)# 添加有向边：表示课程先修关系，如<0,1>表示0是1的先修课graph.add_edge(0,1)graph.add_edge(0,2)graph.add_edge(1,3)graph.add_edge(2,3)graph.add_edge(3,4)graph.add_edge(3,5)print("DFS遍历结果（起点0）:")graph.dfs(0)# 输出 0 1 3 4 5 2（顺序可能因邻接表存储不同有差异）print("\nBFS遍历结果（起点0）:")graph.bfs(0)# 输出 0 1 2 3 4 5print("\n拓扑排序结果:")print(graph.topological_sort())# 输出 [0,2,1,3,5,4] 等合法序列六、有向图的典型应用
- 依赖关系建模：如软件包的依赖、代码模块的调用关系、课程先修体系；
- 路径规划：如城市单行道的导航、网络数据包的路由；
- 状态机：如程序的状态转移、自动售货机的行为逻辑；
- 网络流：如物流运输的单向通路、通信网络的信号传输方向。