DFS查找所有可能的路径

Question

我有以下Java代码，可以在图中找到从一个节点到另一个节点的路径，如何修改它，以便显示所有可能的路径。这里只显示了一条路径，它是一个循环？

输出：路径：[1、2、3、4、1]

对于节点1和4之间的路径，正确的输出应该是：

第一条路径：1-

第二条路径：1-

代码：

import java.util.Iterator;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;
import java.util.List;
import java.util.ArrayList;

public class Graph {

    Stack<Integer> pilha = new Stack<Integer>();


    private int numVertex;
    private boolean[][] adj;

    public Graph(int numVertex, int numEdges) {
        this.numVertex = numVertex;
        this.adj = new boolean[numVertex][numVertex];
    }

    public void addEdge(int start, int end){
        adj[start-1][end-1] = true;
        adj[end-1][start-1] = true;
    }

    List<Integer> visited = new ArrayList<Integer>();
    public void DFS(Graph G, int startVertex){
        int i=0;
        pilha.push(startVertex);

        while (!pilha.empty()) {
            int v = pilha.peek();
            Boolean hasNeighbor = false;
            for (i = 1; i <= G.numVertex; i++) {
                if(G.adj[i-1][v-1] != false) {
                    hasNeighbor = true;
                    pilha.push(i);
                    G.adj[i-1][v-1] = false;
                    G.adj[v-1][i-1] = false;
                    break;
                }
            }
            if (!hasNeighbor) {
                visited.add(0, pilha.pop());
            }
        }
        System.out.println("Path: " + visited);
    }



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

Answer 1

在您的代码中，您没有提到目的地，这是查找源和目的地之间所有可能路径的解决方案。

import java.util.ArrayList;

导入java。util。列表

公共类DepthFirstSearch{

// recursive dfs
private static void dfs_rec(ArrayList<ArrayList<Integer>> adjLists, boolean[] visited, int v, int d,
        List<Integer> path) {
    visited[v] = true;
    path.add(v);

    if (v == d) {

        for (int i = 0; i < path.size(); i++) {
            System.out.print(path.get(i));
        }
        System.out.println("");
    }

    else {
        for (int w : adjLists.get(v)) {
            if (!visited[w]) {
                dfs_rec(adjLists, visited, w, d, path);
            }

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

// Usually dfs_rec() would be sufficient. However, if we don't want to pass
// a boolean array to our function, we can use another function dfs().
// We only have to pass the adjacency list and the source node to dfs(),
// as opposed to dfs_rec(), where we have to pass the boolean array
// additionally.
public static void dfs(ArrayList<ArrayList<Integer>> adjLists, int s, int d) {
    int n = adjLists.size();
    boolean[] visited = new boolean[n];

    List<Integer> path = new ArrayList<Integer>();
    int path_index = 0; // Initialize path[] as empty
    dfs_rec(adjLists, visited, s, d, path);
}

// ----------------------------------------------------------------------
// Testing our implementation
public static void main(String[] args) {

    // Create adjacency list representation
    ArrayList<ArrayList<Integer>> adjLists = new ArrayList<ArrayList<Integer>>();
    final int n = 7;

    // Add an empty adjacency list for each vertex
    for (int v = 0; v < n; v++) {
        adjLists.add(new ArrayList<Integer>());
    }

    // insert neighbors of vertex 0 into adjacency list for vertex 0
    adjLists.get(0).add(1);
    adjLists.get(0).add(2);
    adjLists.get(0).add(3);

    // insert neighbors of vertex 1 into adjacency list for vertex 1
    adjLists.get(1).add(5);
    adjLists.get(1).add(6);

    // insert neighbors of vertex 2 into adjacency list for vertex 2
    adjLists.get(2).add(4);

    // insert neighbors of vertex 3 into adjacency list for vertex 3
    adjLists.get(3).add(2);
    adjLists.get(3).add(4);

    // insert neighbors of vertex 4 into adjacency list for vertex 4
    adjLists.get(4).add(1);

    // insert neighbors of vertex 5 into adjacency list for vertex 5
    // -> nothing to do since vertex 5 has no neighbors

    // insert neighbors of vertex 6 into adjacency list for vertex 5
    adjLists.get(6).add(4);

    // Print vertices in the order in which they are visited by dfs()
    dfs(adjLists, 0, 4);

}

}