关于 numerOfSelfLoops(Graph G) p.523 in Algorithms by Sedgewick and Wayne，

Question

我正在阅读 Sedgewick 和 Wayne 的算法。

以下代码计算无向图G中自环的数量。

我不明白为什么这个代码 returns count/2 而不是 count.

请说明原因。

第 523 页

public static int numerOfSelfLoops(Graph G)
{
    int count = 0;
    for (int v = 0; v < G.V(); v++)
        for (int w : G.adj(v))
            if (v == w) count++;
    return count/2;
}

Answer 1

可以这么说，算法会两次找到相同的循环。松散地说一次顺时针和一次逆时针。书中最后一行的注释是“每边计算两次。”