关于拓扑排序第一种实现

Question

请问第一种实现的判断环是否也可以写在循环内？就是当遍历到邻点入度为0时，说明有环存在。

while(!queue.isEmpty()){
            int w = queue.remove();
            result.add(w);
            for(int v: G.adj(w)){
                if(indegree[v] == 0){
                    hasCycle = true;
                    break;
                }else{
                    indegree[v] --;
                    if(indegree[v] == 0)
                        queue.add(v);
                }
            }
            if(hasCycle)
                break;
        }

Answer 1

liuyubobobo 2019-10-18 13:54:18

如果你能从 w 遍历到 v， 那么 v 的入度就不可能为 0。w-v 这条边肯定进 v 了。

继续加油！：） 

• 提问者 martin123_ #1

  但是老师，我们这里实际没有进行删边操作，所以也有可能存在这个"假入度"为0，但是我们仍可以遍历到该点的情况吧？

• liuyubobobo 回复 提问者 martin123_ #2

  w 是你现在正在遍历的节点，他还没有被删除。w-v是一条还没有被删除的边。

• 提问者 martin123_ 回复 liuyubobobo #3

  我正在遍历的不是w的相邻顶点v吗？ 主要是这里并没有真正的进行删边操作，所以我感觉是可以再遍历到那些"假入度"为0的点；比如视频里面那个0->1->2->0的图，我拿这个试了好像是可以的。。。而且只是运行视频里面的两个特殊例子的话，也确实可以验证出来；   不知道老师能不能举个反例。。。

点开查看后面6条评论