java获取有向图所有路径

在Java中，我们可以通过深度优先搜索算法来获取有向图的所有路径。

首先，我们需要定义一个有向图的类，并实现相关的方法。在这个类中，我们可以使用邻接矩阵或邻接表的方式来表示有向图。

在获取有向图所有路径的方法中，我们可以使用递归来实现深度优先搜索。从图的某一节点开始，我们遍历它的所有邻居节点，并将当前节点添加到路径中。然后，对每个邻居节点，我们继续递归调用获取路径的方法，直到到达终点或找不到邻居节点为止。在递归调用结束后，我们需要从路径中移除当前节点。

具体的代码实现如下所示：

import java.util.ArrayList;
import java.util.List;

public class DirectedGraph {
    private int numVertices;
    private List<List<Integer>> adjacencyList;

    public DirectedGraph(int numVertices) {
        this.numVertices = numVertices;
        this.adjacencyList = new ArrayList<>();

        for (int i = 0; i < numVertices; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest) {
        adjacencyList.get(src).add(dest);
    }

    public List<List<Integer>> getAllPaths(int src, int dest) {
        List<List<Integer>> paths = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        path.add(src);
        getAllPathsUtil(src, dest, path, paths);

        return paths;
    }

    private void getAllPathsUtil(int curr, int dest, List<Integer> path, List<List<Integer>> paths) {
        if (curr == dest) {
            paths.add(new ArrayList<>(path));
        } else {
            for (Integer neighbor : adjacencyList.get(curr)) {
                path.add(neighbor);
                getAllPathsUtil(neighbor, dest, path, paths);
                path.remove(path.size() - 1);
            }
        }
    }
}

使用示例代码来进行测试：

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

    int src = 2;
    int dest = 3;
    List<List<Integer>> paths = graph.getAllPaths(src, dest);

    for (List<Integer> path : paths) {
        for (int node : path) {
            System.out.print(node + " -> ");
        }
        System.out.println();
    }
}

以上代码将会输出所有从节点2到节点3的路径。