Java搜索无向图中两点之间所有路径的算法

算法思路

该算法使用深度优先搜索来查找两个节点之间的所有路径。在搜索期间，对于每个遍历到的未访问节点，我们可以标记它为已访问，并沿着它的所有未访问邻居递归搜索。在这个过程中，我们将到达一个目标节点作为目标终点，或遍历了所有的节点，这代表着没有路径可以到达目标终点，此时我们就回溯到上一步去探索其它可能的路径，直到找到所有的路径或者遍历完所有路径。

代码实现

代码实现分为如下几个步骤：

1. 初始化所有节点为未访问状态，把起始节点添加到路径中，标记起始节点为已访问状态；
2. 从起始节点开始深度优先搜索，对于每个遍历到的未访问节点，标记它为已访问，并将其添加到路径中；
3. 如果当前节点为目标节点，则输出这个路径；
4. 如果当前节点不是目标节点，则在继续递归搜索之前，搜索其所有未访问邻居节点；
5. 回溯到上一个节点，回收资源，从路径中删除该节点并将其标记为未访问；
6. 重复上述操作，直到搜索完所有路径。

public class Graph {
    private int V;
    private LinkedList<Integer>[] adj;

    public Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList();
        }
    }

    void addEdge(int v, int w) {
        adj[v].add(w); // Add w to v's list.
        adj[w].add(v); // Add v to w's list.
    }

    // A recursive function to print all paths from 'u' to 'd'.
    // visited[] keeps track of vertices in current path.
    // path[] stores actual vertices and path_index is current
    // index in path[]
    void printAllPathsUtil(int u, int d, boolean[] visited, int[] path, int pathIndex) {
        visited[u] = true;
        path[pathIndex] = u;
        pathIndex++;

        if (u == d) {
            for (int i = 0; i < pathIndex; i++) {
                System.out.print(path[i] + " ");
            }
            System.out.println("");
        } else {
            Iterator<Integer> i = adj[u].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    printAllPathsUtil(n, d, visited, path, pathIndex);
                }
            }
        }

        // Remove current vertex from path[] and mark it as unvisited
        pathIndex--;
        visited[u] = false;
    }

    void printAllPaths(int s, int d) {
        boolean[] visited = new boolean[V];
        int[] path = new int[V];
        int pathIndex = 0;
        // Initialize all vertices as not visited
        for (int i = 0; i < V; i++) {
            visited[i] = false;
        }

        // Call the recursive helper function to print all paths
        printAllPathsUtil(s, d, visited, path, pathIndex);
    }

    public static void main(String[] args) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(0, 3);
        g.addEdge(2, 0);
        g.addEdge(2, 1);
        g.addEdge(1, 3);

        int s = 2, d = 3;
        System.out.println("Following are all different paths from " + s + " to " + d);
        g.printAllPaths(s, d);
    }
}

示例说明

示例1

例如，我们有一个无向图，有四个节点，边的连接如下所示：

  0 ------- 1
  |         |
  |         |
  |         |
  2 ------- 3

我们要查找从节点2到节点3之间的所有路径，那么可以使用如下代码来实现：

Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(2, 0);
g.addEdge(2, 1);
g.addEdge(1, 3);

int s = 2, d = 3;
System.out.println("Following are all different paths from " + s + " to " + d);
g.printAllPaths(s, d);

输出结果为：

Following are all different paths from 2 to 3
2 0 1 3
2 1 3
2 0 3

可以看出，从节点2到节点3，有三条不同的路径，分别是2->0->1->3，2->1->3，2->0->3。

示例2

再例如，我们有一个无向图，有六个节点，边的连接如下所示：

     0 ----- 1
     |\     /|
     | \   / |
     |  \ /  |
     |   3   |
     |  / \  |
     | /   \ |
     |/     \|
     2 ----- 4
            |
            |
            |
            5

我们要查找从节点0到节点5之间的所有路径，那么可以使用如下代码来实现：

Graph g = new Graph(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.addEdge(4, 5);

int s = 0, d = 5;
System.out.println("Following are all different paths from " + s + " to " + d);
g.printAllPaths(s, d);

输出结果为：

Following are all different paths from 0 to 5
0 1 3 4 5 
0 1 4 5 
0 2 3 4 5 
0 2 4 5 
0 3 4 5 

可以看出，从节点0到节点5，有五条不同的路径，分别是0->1->3->4->5，0->1->4->5，0->2->3->4->5，0->2->4->5，0->3->4->5。