algorithm - 使用 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关联的生成树)。

有向图

Back edges、cross edges和forward edges都可以“发现”新的循环。例如:

我们将以下可能性分开(假设您达到了 u -> v 边缘):

• 后边:u和 v属于同一个 3 周期 iff parent[parent[u]] = v .
• 交叉边缘:u和 v属于同一个 3 周期 iff parent[u] = parent[v] .
• 前沿:u和 v属于同一个 3 周期 iff 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