DFS查找所有可能的路径

Question

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

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

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

第一路径：1 - > 2 - > 3 - > 4

第二路径：1 - > 3 - > 4

代码：

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; 

import java.util.List;

公共类深度优先搜索{

// 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); 

} 

}