目录
拓扑排序
定义
有向图的拓扑排序是对其顶点的一种线性排序，使得对于从顶点 \(u\) 到顶点 \(v\) 的每个有向边 \(uv\)，\(u\) 在排序中都在 \(v\) 之前。
注意：当且仅当图中没有定向环时（即 有向无环图 ），才有可能进行拓扑排序。
拓扑排序主要有Kahn算法和DFS算法两种：
- Kahn算法采用入度方法，以循环迭代方法实现；
- DFS算法采用出度方法，以递归方法实现。
Kahn算法和DFS算法的复杂度是一样的，算法过程也是等价的，不分优劣，因为本质上循环迭代 + 栈 = 递归。
算法
Kahn（卡恩）算法
Kahn算法采用入度方法，其算法过程如下：
- 选择入度为0的节点，输出到结果序列中；
- 删除该节点以及该节点的边；
- 重复执行步骤1和2，直到所有节点输出到结果序列中，完成拓扑排序；
- 如果最后还存在入度不为0的节点，说明有向图中存在环，无法进行拓扑排序。
DFS 算法
深度优先搜索以任意顺序循环遍历图中的每个节点，若搜索进行中碰到之前已经遇到的节点，或碰到叶节点，则中止算法。
DFS算法采用出度算法，其算法过程如下：
- 对有向图进行深度优先搜索；
- 在执行深度优先搜索时，若某个顶点不能继续前进，即顶点的出度为0，则将此顶点入栈;
- 最后对栈中的序列进行逆排序，即完成拓扑排序；如果深度优先搜索时，碰到已遍历的节点，说明存在环。
应用
应用1：Leetcode.207
题目
解题思路
方法一：深度优先
深度优先搜索以任意顺序循环遍历图中的每个节点。若搜索进行中碰到之前已经遇到的节点，或碰到叶节点，则中止算法。
首先，我们将边转换成邻接表，然后通过深度优先遍历，用数组 \(visited\) 记录顶点是否访问过，同时使用 \(path\) 记录所有访问的路径，如果访问过的路径没有成环，那说明可以完成课程，如果成环，则不能完成所有课程。
方法二：广度优先
假设L是存放结果的列表，先找到那些入度为零的节点，把这些节点放到L中，因为这些节点没有任何的父节点。
然后把与这些节点相连的边从图中去掉，再寻找图中的入度为零的节点。
对于新找到的这些入度为零的节点来说，他们的父节点已经都在L中了，所以也可以放入L。
重复上述操作，直到找不到入度为零的节点。如果此时L中的元素个数和节点总数相同，说明排序完成；如果L中的元素个数和节点总数不同，说明原图中存在环，无法进行拓扑排序。
代码实现
DFS算法实现
from collections import defaultdict
from typing import List
class Solution:
def __init__(self):
self._has_cycle = False
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
self._has_cycle = False
# 创建一个邻接表
graph = self.build_graph(prerequisites)
# 记录是否已经访问过
visited = [False] * numCourses
# 记录当前路径
path = [False] * numCourses
# 遍历图中所有的节点
for i in range(numCourses):
self.dfs(graph, i, visited, path)
return not self._has_cycle
def build_graph(self, prerequisites: List[List[int]]):
graph = defaultdict(list)
for prerequisite in prerequisites:
graph[prerequisite[0]].append(prerequisite[1])
return graph
def dfs(self, graph, v, visited, path):
if path[v]:
self._has_cycle = True
if visited[v] or self._has_cycle:
return
visited[v] = True
path[v] = True
for neighbor in graph[v]:
self.dfs(graph, neighbor, visited, path)
path[v] = False
return
Kahn算法实现
from collections import defaultdict, deque
from typing import List
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# 用邻接表记录依赖关系
graph = defaultdict(list)
# 记录每个顶点的入度
incoming_edges = [0] * numCourses
# 创建图
for prerequisite in prerequisites:
graph[prerequisite[1]].append(prerequisite[0])
incoming_edges[prerequisite[0]] += 1
# 将入度为零的顶点放入队列
q = deque([u for u in range(numCourses) if incoming_edges[u] == 0])
# 广度优先搜索
visited = 0
while q:
visited += 1
u = q.popleft()
for v in graph[u]:
incoming_edges[v] -= 1
if incoming_edges[v] == 0:
q.append(v)
return visited == numCourses
参考：
标签：graph,拓扑,self,算法,排序,节点 From： https://www.cnblogs.com/larry1024/p/17002453.html