图中两个顶点之间的所有简单路径查找

1. 概述

本文讨论如何在一个图中找出两个任意顶点之间的所有简单路径（Simple Path）。

我们将从问题定义开始，接着介绍解决该问题的算法，最后分析几种特殊场景下的表现，包括无向图、树、以及森林（非连通无环图）。

2. 问题定义

所谓简单路径，是指路径中不包含重复顶点的路径，即路径中不能有环。

给定一个图 G(V, E) （其中是顶点集合，是边集合），以及两个顶点和，我们的目标是找出从到的所有简单路径。

图可以是有向图也可以是无向图。我们先以有向图为切入点，再讨论无向图的处理方式。

示例

以如下有向图为例：

Graph Example

顶点 1 和顶点 4 之间有以下 5 条简单路径：

(1, 2, 3, 4)
(1, 2, 3, 5, 4)
(1, 2, 4)
(1, 3, 4)
(1, 3, 5, 4)

注意：路径 (1, 3, 4, 5, 4) 不是简单路径，因为它重复访问了顶点 4，形成了环。

3. 算法设计

3.1 核心思想

解决这个问题的经典方法是使用 深度优先搜索（DFS） + 回溯（Backtracking）。

从起点开始进行 DFS。
每次访问一个顶点时，标记为已访问，避免重复访问。
如果到达终点，将当前路径加入结果集。
回溯时，撤销当前顶点的访问标记，以便它能出现在其他路径中。

✅ 关键点

使用 visited[] 数组记录当前路径中已访问的顶点
使用 currentPath 记录当前路径
每次递归完成后要回溯状态

3.2 Java 实现示例

import java.util.*;

public class SimplePathFinder {
    private Map<Integer, List<Integer>> graph;
    private Set<List<Integer>> allPaths;
    private boolean[] visited;

    public SimplePathFinder() {
        graph = new HashMap<>();
        allPaths = new HashSet<>();
    }

    public void addEdge(int u, int v) {
        graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
    }

    public Set<List<Integer>> findAllSimplePaths(int start, int end) {
        visited = new boolean[graph.size() + 1]; // 假设顶点编号从1开始
        dfs(start, end, new ArrayList<>());
        return allPaths;
    }

    private void dfs(int current, int end, List<Integer> path) {
        if (visited[current]) return;

        visited[current] = true;
        path.add(current);

        if (current == end) {
            allPaths.add(new ArrayList<>(path));
        } else {
            for (int neighbor : graph.getOrDefault(current, Collections.emptyList())) {
                dfs(neighbor, end, path);
            }
        }

        path.remove(path.size() - 1);
        visited[current] = false;
    }
}

3.3 时间复杂度分析

在最坏情况下，图是完全图（即任意两个顶点之间都有边），此时算法相当于在找所有顶点的排列组合。

时间复杂度：✅ O(|V|!)
空间复杂度：✅ **O(|V|)**，主要取决于递归栈和路径存储

虽然复杂度很高，但这类问题本质上是组合爆炸问题，使用 DFS + 回溯是标准解法。

4. 无向图的处理

对于无向图，算法依然适用。因为我们可以将其转换为等价的有向图：每条无向边 u - v 替换为两条有向边 u -> v 和 v -> u 。

不过，如果图是一个树（Tree），则路径数量会大大减少。

5. 树结构中的路径

树是一种无环、无向、连通图。树中任意两个节点之间有且仅有一条唯一路径。

这条路径会经过这两个节点的最低公共祖先（LCA）：

从起点向上走到 LCA
再从 LCA 向下走到终点

例如：

Tree

在该树中：

节点 7 和 8 的 LCA 是节点 3
节点 4 和 9 的 LCA 是节点 1

因此，树结构中只需找到 LCA，即可构造唯一路径。

6. 森林结构中的路径

如果图是非连通的无环图（即森林），则可能出现以下情况：

✅ 两种情况：

两节点在同一棵树中 → 有唯一简单路径
两节点在不同树中 → 无路径

例如：

Forest Example

节点 2 和 3 在同一棵树中 → 有路径
节点 5 和 8 在不同树中 → 无路径

7. 小结

本文介绍了如何在一个图中找出两个节点之间的所有简单路径。

我们使用了 DFS + 回溯的方法，适用于有向图和无向图。同时分析了几个特殊场景：

✅ 有向图：标准 DFS + 回溯即可
✅ 无向图：转化为有向图处理
✅ 树结构：唯一路径，经过 LCA
✅ 森林结构：仅当节点在同一树中才有路径

虽然算法复杂度较高，但这是组合路径问题的必然代价。实际中可通过剪枝、缓存等手段优化性能。

Persistence

REST

Security