力扣第 207 题「 课程表」
单边成图
def buildGraph(numCourses, prerequisites):
"""
:param numCourses: 图中节点数
:param prerequisites: 边的依赖关系
:return: 图-邻接表形式
"""
graph = []
for i in range(numCourses):
graph.append([])
for edge in prerequisites:
fro, to = edge[1], edge[0]
graph[fro].append(to)
return graph
图的遍历
def traverse(graph, s):
# basecase
# 类比贪吃蛇游戏,visited 记录蛇 经过过的 格子(整体), 而 on_path 记录蛇身(局部)
if on_path[s]:
# 出现环(贪吃蛇自己咬到自己)
self.has_cycle = True
if visited[s] or self.has_cycle:
# 如果已经找到了环, 也不用再遍历了
return
# 前序位置(标记为True表示进入节点)
visited[s] = True # 对于整个盘, 经过了[s]
on_path[s] = True # 对于当前路径, 经过了[s]
for t in graph[s]: # 遍历[s]可达的所有节点
traverse(graph, t)
# 后序位置
on_path[s] = False # 对于整个盘, 不变; 对于当前路径, 回退
题解
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
def buildGraph(numCourses, prerequisites):
"""
:param numCourses: 图中节点数
:param prerequisites: 边的依赖关系
:return: 图-邻接表形式
"""
graph = []
for i in range(numCourses):
graph.append([])
for edge in prerequisites:
fro, to = edge[1], edge[0]
graph[fro].append(to)
return graph
def traverse(graph, s):
if on_path[s]:
# 出现环
self.has_cycle = True
if visited[s] or self.has_cycle:
# 如果已经找到了环, 也不用再遍历了
return
# 前序位置
visited[s] = True
on_path[s] = True
for t in graph[s]:
traverse(graph, t)
# 后序位置
on_path[s] = False
on_path = [None] * numCourses # 记录每一次递归堆栈中的节点
visited = [None] * numCourses # 记录遍历过的节点, 防止走回头路
self.has_cycle = False # 记录图中是否有环
graph = buildGraph(numCourses, prerequisites)
for i in range(numCourses):
# 遍历图中的所有节点
traverse(graph, i)
return not self.has_cycle