Advertisement

刷题方法:刷题法基于拓排法(BFSDFS)

阅读量:

BFS(广度优先)是一种遍历方式,在访问每个节点时,优先处理该节点的所有相邻节点。

其核心原理在于判断所有节点的最终入度是否为零。

1:首先统计图中各个节点的入度信息,并构建入度表 indegrees。
2:通过使用一个队列 queue,将所有初始入度为零的节点加入队列。
3:当队列不为空时,依次取出队首的节点 pre,并在课程安排图中将其移除。
4:并非真正从邻接表中删除该节点 pre,而是对与该节点相连的所有邻接节点 cur 的入度进行减一操作,即 indegrees[cur] -= 1。
5:若某个邻接节点 cur 的入度在减一后变为零,则说明其所有的前置条件已满足,此时将 cur 加入队列。
6:每次取出一个节点 pre 时,对应的课程数量 numCourses 会减少一;

如果整个课程安排图是一个有向无环图(即可以完成安排),则所有节点都会被依次加入和移出队列,完成拓扑排序。换言之,若存在环路,则必然会有某些节点的入度始终无法降为零。

因此,拓扑排序过程中出队的次数应等于课程总数。通过判断 numCourses 是否等于零来确定课程能否成功安排。

核心数据结构:

邻接表 [ [] for i in range(point) ] 用于记录每个节点所依赖的其他节点

入度表 [0 for i in range(point) ] 用于记录

全部评论 (0)

还没有任何评论哟~