如何结合现有算法实现有向图中指定长度环的计数？

你已经掌握了有向图的环检测方法，但更关注如何确定环的长度，同时现有一段仅适用于无向图的指定长度环计数代码。下面结合这段代码，实现支持有向图、且能查找（计数+输出路径）指定长度环的算法。

一、原无向图代码逻辑解析 #

这段代码基于深度优先搜索（DFS）实现无向图中指定长度n的简单环计数：

• DFS函数：从起点start出发，寻找长度为n-1的路径，若路径终点能回到start，则计数+1
• countCycles函数：遍历起点（避免重复计数，只遍历前V-(n-1)个节点），调用DFS后标记起点为已访问，最后将计数除以2（无向图中每个环会被正反方向各统计一次）

二、适配有向图的指定长度环计数算法 #

针对有向图，只需修改两处核心逻辑：

1. 无需除以2：有向图的环方向唯一，不会出现无向图的重复计数问题
2. 调整起点遍历范围：遍历所有节点（因为有向图中不同起点可能找到不同方向的环）

修改后的代码如下：

def dfs_directed(V, graph, marked, n, vert, start, count):
    marked[vert] = True
    # 找到长度为n-1的路径，检查是否能回到起点
    if n == 0:
        marked[vert] = False
        if graph[vert][start] == 1:
            count += 1
        return count
    # 遍历所有邻接节点，跳过已访问的节点（保证是简单环）
    for i in range(V):
        if not marked[i] and graph[vert][i] == 1:
            count = dfs_directed(V, graph, marked, n-1, i, start, count)
    marked[vert] = False
    return count

def count_cycles_directed(graph, n, V):
    marked = [False] * V
    count = 0
    # 遍历所有节点作为起点
    for i in range(V):
        count = dfs_directed(V, graph, marked, n-1, i, i, count)
        # 标记起点为已访问，避免重复统计以该点为起点的环
        marked[i] = True
    return count

三、实现指定长度环的查找（输出具体环路径） #

如果需要找到具体的环路径而非仅计数，可修改DFS函数，在递归过程中记录路径：

def dfs_find_cycles(V, graph, marked, n, vert, start, path, cycles):
    marked[vert] = True
    path.append(vert)
    # 路径长度达到n-1，检查是否能回到起点
    if n == 0:
        if graph[vert][start] == 1:
            # 复制路径并添加起点，形成完整环
            cycle = path.copy()
            cycle.append(start)
            cycles.append(cycle)
        path.pop()
        marked[vert] = False
        return
    # 遍历邻接节点
    for i in range(V):
        if not marked[i] and graph[vert][i] == 1:
            dfs_find_cycles(V, graph, marked, n-1, i, start, path, cycles)
    path.pop()
    marked[vert] = False

def find_cycles_of_length(graph, n, V, is_directed=True):
    marked = [False] * V
    cycles = []
    for i in range(V):
        dfs_find_cycles(V, graph, marked, n-1, i, i, [], cycles)
        marked[i] = True
    # 无向图去重：每个环会被正反记录一次，保留其中一个
    if not is_directed:
        unique_cycles = []
        seen = set()
        for cycle in cycles:
            # 将环转为元组，排序后去重（无向图的环顺序不影响）
            sorted_cycle = tuple(sorted(cycle))
            if sorted_cycle not in seen:
                seen.add(sorted_cycle)
                unique_cycles.append(cycle)
        return unique_cycles
    return cycles

四、使用示例 #

无向图测试（复用你提供的邻接矩阵） #

import numpy as np

V = 5
adj0 = np.array([[0, 1, 0, 1, 1],
                 [1, 0, 1, 1, 0],
                 [0, 1, 0, 1, 0],
                 [1, 1, 1, 0, 1],
                 [1, 0, 0, 1, 0]])

# 计数长度为3的环
print("无向图长度3的环数量：", count_cycles_directed(adj0.tolist(), 3, V) // 2)
# 查找长度为3的环
cycles_3 = find_cycles_of_length(adj0.tolist(), 3, V, is_directed=False)
print("无向图长度3的环：", cycles_3)

有向图测试 #

# 有向图邻接矩阵：包含一个长度为2的环（0→1→0）和一个长度为3的环（1→2→3→1）
V_dir = 4
adj_dir = [[0,1,0,0],
           [1,0,1,0],
           [0,0,0,1],
           [0,1,0,0]]

# 计数长度为2的环
print("有向图长度2的环数量：", count_cycles_directed(adj_dir, 2, V_dir))
# 查找长度为3的环
cycles_3_dir = find_cycles_of_length(adj_dir, 3, V_dir)
print("有向图长度3的环：", cycles_3_dir)

关键说明 #

• 上述代码仅统计简单环（环中无重复节点），若需统计包含重复节点的环，需移除marked标记的逻辑
• 无向图去重通过排序环节点实现，确保每个环只被记录一次
• 时间复杂度为O(V*(V+E))，适用于小规模图；大规模图可考虑使用矩阵快速幂等更高效的方法

内容的提问来源于stack exchange，提问作者Abolfazl