拓扑排序, BFS 做法
无论是 directed 还是 undirected Graph,其 BFS 的核心都在于 "indegree",处理顺序也多是从 indegree 最小的开始,从外向内。
我们先用一个 HashMap 统计下所有节点的 indegree; 值越高的,在拓扑排序中位置也就越靠后,因为还有 N = current indegree 的 parent node 们没有处理完。
因此在循环最开始,我们可以把所有 indegree = 0 (也即不在 hashmap 中) 的节点加到 list 中,也作为 BFS 的起点。
在 BFS 过程中,我们依次取出队列里取出节点 node 的 neighbors, next,并且对 next 对应的 indegree -1,代表其 parent node 已经被处理完,有效 indegree 减少。
当-1之后如果 next 的 indegree 已经是 0 , 则可以加入 list,并且作为之后 BFS 中新的起始节点。
从 Course Schedule 的 BFS 做法学到的经验是,如果图中有环,会有环上的 node 永远无法减到 indegree = 0 的情况,导致一些 node 没有被访问。
这也是当初面试被问到的为什么 JVM 不只靠 reference counting 来做 GC,就是因为有环的时候,indegree 不会减到 0.
Last updated