使用 DFS 计算长度为 3 的循环

Question

设G=(V,E)为无向图。我们如何使用以下 DFS 计算长度为 3 的周期恰好一次：

DFS(G,s):
    foreach v in V do
        color[v] <- white; p[v] <- nil
    DFS-Visit(s)

DFS-Visit(u)
    color[u] <- grey
    foreach v in Adj[u] do
        if color[v] = white then 
            p[v] = u; DFS-Visit(v)
    color[u] <- black

每当我们发现一个已经被发现的节点（灰色）时，就会有一个循环。该节点的边缘称为后边缘。当 p[p[p[v]]] = v 时，循环的长度为 3，对吗？所以

DFS-Visit(u)
    color[u] <- grey
    foreach v in Adj[u] do
        if color[v] = grey and p[p[p[v]]] = v then
            // we got a cycle of length 3
        else if color[v] = white then 
            p[v] = u; DFS-Visit(v)
    color[u] <- black

但是，我怎样才能创建一个合适的计数器来计算周期数，我怎样才能每个周期只计数一次？

Answer 1

我不确定您的条件 parent[parent[parent[v]]] == v 是如何工作的。 IMO 只要 parent 表示树结构（因为它应该对应于与 DFS 关联的生成树），它就永远不会是真的。

有向图

向后边缘、交叉边缘和向前边缘都可以"discover"新循环。例如：

我们将以下可能性分开（假设您达到 u -> v 边缘）：

后沿：u 和 v 属于同一个 3 循环当且仅当 parent[parent[u]] = v.
交叉边：u和v属于同一个3-cycle iff parent[u] = parent[v].
前沿：u 和 v 属于同一个 3 周期当且仅当 parent[parent[v]] = u.

无向图

没有更多的交叉边。后边缘和前边缘是多余的。因此，您只需检查后沿：当您到达 u -> v 后沿时，u 和 v 属于相同的 3 周期 iff parent[parent[u]] = v.

def dfs(u):
    color[u] = GREY
    for v in adj[u]:
        # Back edge
        if color[v] == GREY:
            if parent[parent[u]] == v: 
                print("({}, {}, {})".format(v + 1, parent[u] + 1, u + 1))
        # v unseen
        elif color[v] == WHITE:
            parent[v] = u
            dfs(v)
    color[u] = BLACK

如果你想测试一下：

WHITE, GREY, BLACK = 0, 1, 2
nb_nodes, nb_edges = map(int, input().split())
adj = [[] for _ in range(nb_nodes)]
for _ in range(nb_edges):
    u, v = map(int, input().split())
    adj[u - 1].append(v - 1) 
    adj[v - 1].append(u - 1) 
parent = [None] * nb_nodes
color = [WHITE] * nb_nodes

Answer 2

如果不使用 DFS 的解决方案是可行的，那么有一个简单的解决方案可以在 O(NMlog(N³)) 中运行，其中 N 是图中的顶点数，M 是边数。

我们将迭代边而不是迭代顶点。对于每条边 u-v，我们必须找到连接到 u 和 v 的每个顶点。我们可以通过遍历图中的每个顶点 w 并检查是否存在边 v-w 和 w-u 来做到这一点。每当您找到这样的顶点时，对 u、v、w 进行排序并将有序的三元组添加到不允许重复的 BBST（例如：C++ 中的 std::set）。检查图中每条边后，长度为 3 个周期的计数将恰好是 BBST 的大小（添加的元素数量）。

我们来分析一下算法的复杂度：

我们遍历每条边。当前复杂度为 O(M)
对于每条边，我们遍历每个顶点。当前复杂度为 O(NM)
对于形成循环的每个（边，顶点）对，我们将向 BBST 添加一个三元组。添加到 BBST 的复杂度为 O(log(K))，其中 K 是 BST 的大小。在最坏的情况下，每个顶点的三元组形成一个循环，因此我们可以将 O(N³) 个元素添加到 BST，而添加一些元素的复杂度可能高达 O(log(N³))。那么最终的复杂度是 O(NMlog(N³))。这听起来可能很多，但在最坏的情况下 M = O(N²) 因此复杂度将为 O(N³log(N³))。由于我们最多可能有 O(N³) 个长度为 3 的循环，因此我们的算法与最优算法仅差一个对数因子。

使用 DFS 计算长度为 3 的循环

Count cycles of length 3 using DFS

algorithm

graph-theory

depth-first-search

graph-algorithm

有向图

无向图