如何计算无向图中所有可能的路径数量？

首先咱们得先明确问题里的路径定义：从你的示例来看，这里的路径指的是所有长度≥1的简单路径（路径中没有重复访问的节点），并且无向图里A→B和B→A会被算作两条不同的路径——这也是你示例总数12的计算依据。

先拆解你的示例验证总数 #

你的示例图邻接关系是1-2、2-3、2-4，咱们逐个起点统计所有简单路径：

• 起点1：1→2、1→2→3、1→2→4（共3条）
• 起点2：2→1、2→3、2→4（共3条）
• 起点3：3→2、3→2→1、3→2→4（共3条）
• 起点4：4→2、4→2→1、4→2→3（共3条）
  把这些加起来3×4=12，正好和你给出的总数一致。

通用计算思路 #

要计算这类路径的总数，核心思路是遍历每个节点作为起点，用DFS/BFS枚举所有从该起点出发的简单路径，最后累加所有起点的路径数：

1. 把图转换成邻接表形式（便于遍历邻居节点）
2. 对每个节点作为起点，使用深度优先搜索（DFS），记录已经访问过的节点（避免重复访问形成回路）
3. 每走到一个新的节点，就代表找到一条从起点到该节点的路径，统计数量
4. 把所有起点的路径数相加，得到最终总数

Python代码实现 #

下面是用DFS实现的代码，直接可以运行验证你的示例：

def count_all_simple_paths(graph):
    total_paths = 0
    all_nodes = list(graph.keys())
    
    def dfs(current_node, visited_nodes):
        # 用nonlocal引用外层函数的路径计数器
        nonlocal path_count
        # 遍历当前节点的所有邻居
        for neighbor in graph[current_node]:
            if neighbor not in visited_nodes:
                # 每访问一个新邻居，就代表找到一条从起点到该邻居的路径
                path_count += 1
                # 标记该邻居已访问，继续递归探索更长的路径
                visited_nodes.add(neighbor)
                dfs(neighbor, visited_nodes)
                # 回溯，移除标记，探索其他分支
                visited_nodes.remove(neighbor)
    
    # 遍历每个节点作为起点
    for start_node in all_nodes:
        path_count = 0
        # 初始化已访问集合，先加入起点
        visited = set()
        visited.add(start_node)
        dfs(start_node, visited)
        total_paths += path_count
    
    return total_paths

# 你的示例图邻接表
sample_graph = {
    1: [2],
    2: [1, 3, 4],
    3: [2],
    4: [2]
}

# 运行测试，输出12
print(count_all_simple_paths(sample_graph))

注意事项 #

• 这里统计的是简单路径（无重复节点），如果允许路径中重复访问节点（比如走回路，像2→3→2→4），那路径数量会是无限的，所以默认只统计简单路径
• 无向图的双向性：因为无向边可以双向走，所以A到B和B到A会被算作两条独立路径，这也是示例总数的关键

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