判断有向图是否有环

2022-06-26 本文已影响0人 Robin92

问题来源于做题力扣-顺丰科技智慧物流校园技术挑战赛中的第一题。

没阅读《剑指Offer》之前看到题时不会做，在阅读过程中有自己的解题想法，也看到《剑指Offer》中提到的解法。先按自己的想法实现，结果发现了自己想法的误区，所以在这里记录一下误区及原因，以及正确的解法。

如下图，红线为故意加入的一个导致有向图中形成环。

2022-06-26_213954.jpg

入度和出度

入度统计的是有多少箭头指向自己。
出度统计的是自己有多少箭头指向别人。

如上图中节点 8 被两个箭头指向，所以它的入度为 2；有一个指向 12 的箭头，所以出度为 1。同理，上图节点 5入度为 1，出度为 2。

错误的想法

考虑到有环，所以直观的想法是：沿着路走，如果某条路一直导致重复走某些节点，那么就证明存在环。

细节：

怎么沿着路走：用广度优先算法（队列）。可以。
怎么确定有环的具体条件：Em...（支支吾吾）根据...入度次数？

问题就出在判断有环的条件上，你不好判断某几个点是一直在循环。考虑如下几点：

如果 A 点到 B 点的路径有 3 中，B 到 C 的路径有 5 种，那么 A 到 C 一共有 15 种路径。如果广度优先算法中不限制访问过的点再次访问，那么从到 C 点就至少有 15 种走法。如何定上限就是个问题。
上步中，如果要限制每个点都被走一次也不能判断有环。极端地例子如 A 能走向 B 和 C，B 能走向 C，C 也能走向 B，怎么判断这种环？
那统计边的次数呢？……

考虑边是正确的想法。但如何判断有环条件还需要进一步考虑细节：

规定每个边只走一次？每个边都会走到。单纯这个条件没法判断
规定每个边只走一次，再加上每个点只走一次呢？也不行，思考一下可以知道点上不能限制只走一次。
规定每个边只走一次，每个点上只走它的入度次？这个好像可以。验证一下好像还少个 “没有路时是否为终点” 的条件。
规定每个边只走一次，每个点上只走它的入度次，且最后无路时总是走向终点。若不是终点，则证明有环。哎，这个好像可以。

但上方最后一个方案还是有问题的：没有考虑 “孤岛” 的存在，如只有一个 A 节点没有入度也没有出度，或 A、B 节点相互有向连接。如果加逻辑判断又该怎么加呢？

此时已经差不多很接近正确的解法了，具体参考下节吧。

正确的解法

《剑指Offer-专项突击版》在图-拓扑排序一节中有提到解法。文中主要讲的是拓扑排序，我这里转化一下针对于查环描述：

每次从有向图中取出一个入度为 0 的节点删除，同时删除该节点及所有以他为起点的边，若最终图为空则证明无环，最终非空则证明有环。

原文：“一种常用的拓扑排序算法是每次从有向无环图中取出一个入度为 0 的节点添加到拓扑排序序列之中，然后删除该节点及所有以它为起点的边。重复这个步骤，直到图为空或图中不存在入度为 0 的节点。如果最终图为空，那么图是有向无环图，此时就找到了该图的一个拓扑排序序列。如果最终图不为空并且已经不存在入度为 0 的节点，那么图中一定有环。”

为什么呢？：我们来单独考虑一个单环，那么环中每一个点都是入度为 1，出度也为 1，即不可能入度为 0。按上面删环的描述过程，如果环存在，这个环中的的每个点都无法有机会变成入度为 0 的点，因此就证明了环的存在。

哈，类似于环中象棋中的“连环马”战术了：每个节点相互看守。“入度为 0”这只矛根本无从下手（无法入环）。

解题思路及代码

力扣-顺丰科技智慧物流校园技术挑战赛。

解题思路

整体思路：通过每次删除入度为 0 的边，最后判断是否还有删除不到的边存在。删除不到就是因为不存在入度 0 的边了。若存在就是有环，否则无环。

细节：

用边的集合来表示此图，因为要有删除边的操作。
要记录所有点的入度，所以用个 map 记录入度（inCounts）
要查找下一个节点，所以要用个 map 记录路径的两点
入度为 0 的点是要分析的点，所以用个队列记录所有入度为 0 的点（heads）

综上：每次通过入度为 0 的 heads 数组中取一个，遍历它的下一个节点 target，删除此路 edge，并更新 target 的入度（减一），若 target 入度为 0，加入到 heads 中，以备下次分析到。

解题代码

目前只记录了个人从书上获得的解法及自己写的思路。还需要看看书中是不是有其他细节的有环，或其他人的代码的方法。（力扣上用 dfs 遍历看一下）

// parseToMap parse edges to map[[2]int]struct{}
func parseToMap(graph string) map[[2]int]struct{} {
    paths := strings.Split(graph, ",")
    arr := make(map[[2]int]struct{}, len(paths))
    for _, path := range paths {
        temp := strings.Split(path, "->")
        a, _ := strconv.Atoi(temp[0])
        b, _ := strconv.Atoi(temp[1])
        arr[[2]int{a, b}] = struct{}{}
    }
    return arr
}
func hasCycle(graph string) bool {
    // parseToMap parse edges to map[[2]int]struct{}
    // 因为要有线的删除，所以用 map 存储边集
    edges := parseToMap(graph) // 边集

    // 记录点的指向
    paths := make(map[int][]int, 100)
    for edge := range edges {
        paths[edge[0]] = append(paths[edge[0]], edge[1])
    }

    // 计算入度
    inCounts := make(map[int]int, 100) // 入度：起始点=>入度
    for edge, _ := range edges {
        inCounts[edge[1]]++                       // 入度为箭头的箭头（头部），只能统计到非零入度的点
        inCounts[edge[0]] = inCounts[edge[0]] + 0 // 因为上步中统计不到入度为 0 的点（注意点）
    }

    // 入度为 0 的点就是 heads
    heads := make([]int, 0)
    for node, count := range inCounts {
        if count == 0 {
            heads = append(heads, node)
        }
    }

    // 按 heads 遍历（把 heads 当队列用，动态变化）
    for len(heads) > 0 {
        var head int
        head, heads = heads[0], heads[1:]

        for _, target := range paths[head] {
            inCounts[target]--                  // 入度 - 1
            delete(edges, [2]int{head, target}) // 删除图中的边
            if inCounts[target] == 0 {          // 入度减为 0，成为新的 head
                heads = append(heads, target)
            }
        }
    }

    // fmt.Println(inCounts)
    // fmt.Println(edges)
    return len(edges) > 0
}