数据结构：有向图-育师

一、有向图的定义

有向图是图的重要类型，由顶点集合和有向边集合组成，其中每条边都有明确的方向，仅能从一个顶点指向另一个顶点。若存在一条从顶点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] 等合法序列