多重图中指定长度无回溯路径的计数函数实现求助

核心思路 #

要实现这个计数功能，关键是在遍历路径时跟踪每条已使用的边（避免沿同一条边反向回溯），同时严格控制路径长度。我们可以用递归或迭代DFS实现，核心是维护以下状态：当前节点、剩余步数、已使用的边集合（记录不能再反向走的边）。

图的表示方式 #

因为是多重图，同一对顶点间可能有多条边，所以需要给每条边分配唯一ID。用邻接表存储图，每个节点的邻接项包含邻居节点和边ID，示例如下：

# 示例：A和B之间有2条边（ID 0、1），B和C之间有1条边（ID 2）
graph = {
    'A': [('B', 0), ('B', 1)],
    'B': [('A', 0), ('A', 1), ('C', 2)],
    'C': [('B', 2)]
}

递归实现方案 #

递归函数通过传递状态（当前节点、剩余步数、已使用边集合），遍历所有合法路径并计数：

def count_paths(graph, start, end, n, used_edges=None):
    # 初始化已使用边集合
    if used_edges is None:
        used_edges = set()
    # 终止条件：剩余步数为0时，判断是否到达终点
    if n == 0:
        return 1 if start == end else 0
    if n < 0:
        return 0
    
    total = 0
    # 遍历当前节点的所有邻接边
    for neighbor, edge_id in graph[start]:
        # 若这条边未被使用过（未反向回溯）
        if edge_id not in used_edges:
            # 复制已使用集合，避免污染其他分支
            new_used = used_edges.copy()
            new_used.add(edge_id)
            # 递归遍历下一个节点，步数减1
            total += count_paths(graph, neighbor, end, n-1, new_used)
    return total

迭代DFS实现（避免递归栈溢出） #

如果路径长度n很大，递归可能触发栈溢出，用迭代版DFS更安全：

def count_paths_iterative(graph, start, end, n):
    # 栈中存储状态：(当前节点, 剩余步数, 已使用边集合)
    stack = [(start, n, set())]
    total = 0
    
    while stack:
        current, remaining, used = stack.pop()
        # 终止判断
        if remaining == 0:
            if current == end:
                total += 1
            continue
        if remaining < 0:
            continue
        # 遍历邻接边
        for neighbor, edge_id in graph[current]:
            if edge_id not in used:
                new_used = used.copy()
                new_used.add(edge_id)
                stack.append((neighbor, remaining-1, new_used))
    return total

关键注意事项 #

• 边的唯一标识：必须给每条边分配唯一ID，否则无法区分同一对顶点间的不同边，会错误禁止合法路径。
• 状态隔离：每次遍历分支时要复制已使用边集合，不能直接修改原集合，否则会导致不同路径分支的状态互相干扰。
• 终止条件严格：只有当剩余步数为0时，才判断是否到达终点，不能提前返回。

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