同步操作将从 程序员充电站/LeetCode-Py 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
拓扑排序(Topological Sorting):一种对有向无环图(DAG)的所有顶点进行线性排序的方法,使得图中任意一点 $u$ 和 $v$,如果存在有向边 $<u, v>$,则 $u$ 必须在 $v$ 之前出现。对有向图进行拓扑排序产生的线性序列称为满足拓扑次序的序列,简称拓扑排序。
图的拓扑排序是针对有向无环图(DAG)来说的,无向图和有向有环图没有拓扑排序,或者说不存在拓扑排序。
如上图中的有向无环图(DAG)所示,$v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4 \rightarrow v_5 \rightarrow v_6$ 是该图的一个拓扑序列。与此同时,$v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4 \rightarrow v_6 \rightarrow v_5$ 也是该图的一个拓扑序列。也就是说,对于一个有向无环图来说,拓扑序列可能不止一个。
拓扑排序有两种实现方法,分别是「Kahn 算法」和「DFS 深度优先搜索算法」。接下来我们依次来看下它们是如何实现的。
Kahn 算法的基本思想:
- 不断找寻有向图中入度为 $0$ 的顶点,将其输出。
- 然后删除入度为 $0$ 的顶点和从该顶点出发的有向边。
- 重复上述操作直到图为空,或者找不到入度为 $0$ 的节点为止。
import collections
class Solution:
# 拓扑排序,graph 中包含所有顶点的有向边关系(包括无边顶点)
def topologicalSortingKahn(self, graph: dict):
indegrees = {u: 0 for u in graph} # indegrees 用于记录所有顶点入度
for u in graph:
for v in graph[u]:
indegrees[v] += 1 # 统计所有顶点入度
# 将入度为 0 的顶点存入集合 S 中
S = collections.deque([u for u in indegrees if indegrees[u] == 0])
order = [] # order 用于存储拓扑序列
while S:
u = S.pop() # 从集合中选择一个没有前驱的顶点 0
order.append(u) # 将其输出到拓扑序列 order 中
for v in graph[u]: # 遍历顶点 u 的邻接顶点 v
indegrees[v] -= 1 # 删除从顶点 u 出发的有向边
if indegrees[v] == 0: # 如果删除该边后顶点 v 的入度变为 0
S.append(v) # 将其放入集合 S 中
if len(indegrees) != len(order): # 还有顶点未遍历(存在环),无法构成拓扑序列
return []
return order # 返回拓扑序列
def findOrder(self, n: int, edges):
# 构建图
graph = dict()
for i in range(n):
graph[i] = []
for u, v in edges:
graph[u].append(v)
return self.topologicalSortingKahn(graph)
基于 DFS 实现拓扑排序算法的基本思想:
- 对于一个顶点 $u$,深度优先遍历从该顶点出发的有向边 $<u, v>$。如果从该顶点 $u$ 出发的所有相邻顶点 $v$ 都已经搜索完毕,则回溯到顶点 $u$ 时,该顶点 $u$ 应该位于其所有相邻顶点 $v$ 的前面(拓扑序列中)。
- 这样一来,当我们对每个顶点进行深度优先搜索,在回溯到该顶点时将其放入栈中,则最终从栈顶到栈底的序列就是一种拓扑排序。
使用集合 $visited$ 用于记录当前顶点是否被访问过,避免重复访问。
使用集合 $onStack$ 用于记录同一次深度优先搜索时,当前顶点是否被访问过。如果当前顶点被访问过,则说明图中存在环路,无法构成拓扑序列。
使用布尔变量 $hasCycle$ 用于判断图中是否存在环。
从任意一个未被访问的顶点 $u$ 出发。
将顶点 $u$ 标记为被访问过,并在本次深度优先搜索中标记为访问过。然后深度优先遍历从顶点 $u$ 出发的有向边 $<u, v>$。
当顶点 $u$ 的所有相邻顶点 $v$ 都被访问后,回溯前记录当前节点 $u$(将当前节点 $u$ 输出到拓扑序列 $order$ 中)。
取消本次深度优先搜索时,顶点 $u$ 的访问标记。
对其他未被访问的顶点重复 $4 \sim 7$ 步过程,直到所有节点都遍历完,或者出现环。
如果不存在环路,则将 $order$ 逆序排序后,顶点的顺序就是拓扑排序的结果。
import collections
class Solution:
# 拓扑排序,graph 中包含所有顶点的有向边关系(包括无边顶点)
def topologicalSortingDFS(self, graph: dict):
visited = set() # 记录当前顶点是否被访问过
onStack = set() # 记录同一次深搜时,当前顶点是否被访问过
order = [] # 用于存储拓扑序列
hasCycle = False # 用于判断是否存在环
def dfs(u):
nonlocal hasCycle
if u in onStack: # 同一次深度优先搜索时,当前顶点被访问过,说明存在环
hasCycle = True
if u in visited or hasCycle: # 当前节点被访问或者有环时直接返回
return
visited.add(u) # 标记节点被访问
onStack.add(u) # 标记本次深搜时,当前顶点被访问
for v in graph[u]: # 遍历顶点 u 的邻接顶点 v
dfs(v) # 递归访问节点 v
order.append(u) # 后序遍历顺序访问节点 u
onStack.remove(u) # 取消本次深搜时的 顶点访问标记
for u in graph:
if u not in visited:
dfs(u) # 递归遍历未访问节点 u
if hasCycle: # 判断是否存在环
return [] # 存在环,无法构成拓扑序列
order.reverse() # 将后序遍历转为拓扑排序顺序
return order # 返回拓扑序列
def findOrder(self, n: int, edges):
# 构建图
graph = dict()
for i in range(n):
graph[i] = []
for v, u in edges:
graph[u].append(v)
return self.topologicalSortingDFS(graph)
拓扑排序可以用来解决一些依赖关系的问题,比如项目的执行顺序,课程的选修顺序等。
描述:给定一个整数 $numCourses$,代表这学期必须选修的课程数量,课程编号为 $0 \sim numCourses - 1$。再给定一个数组 $prerequisites$ 表示先修课程关系,其中 $prerequisites[i] = [ai, bi]$ 表示如果要学习课程 $ai$ 则必须要先完成课程 $bi$。
要求:返回学完所有课程所安排的学习顺序。如果有多个正确的顺序,只要返回其中一种即可。如果无法完成所有课程,则返回空数组。
说明:
示例:
输入:numCourses = 2, prerequisites = [[1,0]]
输出:[0,1]
解释:总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1]。
输入:numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出:[0,2,1,3]
解释:总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此,一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3]。
这道题是「0207. 课程表」的升级版,只需要在上一题的基础上增加一个答案数组 $order$ 即可。
import collections
class Solution:
# 拓扑排序,graph 中包含所有顶点的有向边关系(包括无边顶点)
def topologicalSortingKahn(self, graph: dict):
indegrees = {u: 0 for u in graph} # indegrees 用于记录所有顶点入度
for u in graph:
for v in graph[u]:
indegrees[v] += 1 # 统计所有顶点入度
# 将入度为 0 的顶点存入集合 S 中
S = collections.deque([u for u in indegrees if indegrees[u] == 0])
order = [] # order 用于存储拓扑序列
while S:
u = S.pop() # 从集合中选择一个没有前驱的顶点 0
order.append(u) # 将其输出到拓扑序列 order 中
for v in graph[u]: # 遍历顶点 u 的邻接顶点 v
indegrees[v] -= 1 # 删除从顶点 u 出发的有向边
if indegrees[v] == 0: # 如果删除该边后顶点 v 的入度变为 0
S.append(v) # 将其放入集合 S 中
if len(indegrees) != len(order): # 还有顶点未遍历(存在环),无法构成拓扑序列
return []
return order # 返回拓扑序列
def findOrder(self, numCourses: int, prerequisites):
graph = dict()
for i in range(numCourses):
graph[i] = []
for v, u in prerequisites:
graph[u].append(v)
return self.topologicalSortingKahn(graph)
描述:给定一个有向图 $graph$,其中 $graph[i]$ 是与节点 $i$ 相邻的节点列表,意味着从节点 $i$ 到节点 $graph[i]$ 中的每个节点都有一条有向边。
要求:找出图中所有的安全节点,将其存入数组作为答案返回,答案数组中的元素应当按升序排列。
说明:
示例:
输入:graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出:[2,4,5,6]
解释:示意图如上。
节点 5 和节点 6 是终端节点,因为它们都没有出边。
从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6。
输入:graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出:[4]
解释:
只有节点 4 是终端节点,从节点 4 开始的所有路径都通向节点 4。
class Solution:
# 拓扑排序,graph 中包含所有顶点的有向边关系(包括无边顶点)
def topologicalSortingKahn(self, graph: dict):
indegrees = {u: 0 for u in graph} # indegrees 用于记录所有节点入度
for u in graph:
for v in graph[u]:
indegrees[v] += 1 # 统计所有节点入度
# 将入度为 0 的顶点存入集合 S 中
S = collections.deque([u for u in indegrees if indegrees[u] == 0])
while S:
u = S.pop() # 从集合中选择一个没有前驱的顶点 0
for v in graph[u]: # 遍历顶点 u 的邻接顶点 v
indegrees[v] -= 1 # 删除从顶点 u 出发的有向边
if indegrees[v] == 0: # 如果删除该边后顶点 v 的入度变为 0
S.append(v) # 将其放入集合 S 中
res = []
for u in indegrees:
if indegrees[u] == 0:
res.append(u)
return res
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
graph_dict = {u: [] for u in range(len(graph))}
for u in range(len(graph)):
for v in graph[u]:
graph_dict[v].append(u) # 逆序建图
return self.topologicalSortingKahn(graph_dict)
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。