Count alle möglichen Pfade zwischen zwei Knoten in einem Graph mit Java und DFS mit Adjazenzliste

Question

Ich versuche, dies auf geeksforgeeks unten Problem zu lösen java

https://www.geeksforgeeks.org/count-possible-paths-two-vertices/

Aber Problem ist, dass pathCount 0 zwischen jedem bekommt rekursiver Aufruf. Unten ist mein vollständiger Code:

public class Graph { 
private int V; // No. of vertices 

// Array of lists for Adjacency List Representation 
private LinkedList<Integer> adj[]; 

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

// Function to add an edge into the graph 
void addEdge(int v, int w) { 
    adj[v].add(w); // Add w to v'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 countPathsUtil(int u, int d, boolean visited[], int pathCount) { 
    // Mark the current node as visited and print it 
    visited[u] = true; 

    // If current vertex is same as destination, then increment count 
    if (u == d) { 
     pathCount++; 
     System.out.println(pathCount); 
    } 


    // Recur for all the vertices adjacent to this vertex 
    //else { 
     Iterator<Integer> i = adj[u].listIterator(); 
     while (i.hasNext()) { 
      int n = i.next(); 
      if (!visited[n]) { 
       System.out.print(pathCount+" :"); 
       countPathsUtil(n, d, visited, pathCount); 
      } 
     } 
    //} 

    visited[u] = false; 
} 

// Returns count of paths from 's' to 'd' 
int countPaths(int s, int d) { 
    // Mark all the vertices as not visited 
    boolean visited[] = new boolean[V]; 
    Arrays.fill(visited, false); 

    // Call the recursive helper function to print 
    // all paths 
    int pathCount = 0; 
    countPathsUtil(s, d, visited, pathCount); 
    return pathCount; 
} 

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("Total paths:"); 
    System.out.println(g.countPaths(s, d)); 
} 

}

Rest des Code korrekt ist nur mein pathCount Wert 0 am Ende zurück.

Bitte helfen Sie eine einfache Lösung ist erforderlich!

Answer 1

Java ist von Wert Pass nicht durch Verweis übergeben, so diesen Code

int pathCount = 0; 
countPathsUtil(s, d, visited, pathCount); 
return pathCount; 

bedeutet, dass egal, was in Ihrer countPathsUtil Methode geschieht, wird pathCount immer als 0 try Ihre countPathsUntil Methode Ändern zurückgegeben werden zurückkehren der PfadCount.

Answer 2

Dank der festgelegte Code ist wie folgt @PillHead:

public class Graph { 
    private int V; // No. of vertices 

    // Array of lists for Adjacency List Representation 
    private LinkedList<Integer> adj[]; 

    @SuppressWarnings("unchecked") 
    Graph(int v) { 
     V = v; 
     adj = new LinkedList[v]; 
     for (int i = 0; i < v; ++i) 
      adj[i] = new LinkedList<>(); 
    } 

    // Method to add an edge into the graph 
    void addEdge(int v, int w) { 
     adj[v].add(w); // Add w to v's list. 
    } 

    /** 
    * A recursive method to count all paths from 'u' to 'd'. 
    */ 
    int countPathsUtil(int u, int d, boolean visited[], int pathCount) { 
     // Mark the current node as visited and print it 
     visited[u] = true; 

     // If current vertex is same as destination, then increment count 
     if (u == d) { 
      pathCount++; 
     } 

     // Recur for all the vertices adjacent to this vertex 
     else { 
      Iterator<Integer> i = adj[u].listIterator(); 
      while (i.hasNext()) { 
       int n = i.next(); 
       if (!visited[n]) { 
        pathCount = countPathsUtil(n, d, visited, pathCount); 
       } 
      } 
     } 

     visited[u] = false; 
     return pathCount; 
    } 

    /* Returns count of paths from 's' to 'd'*/ 
    int countPaths(int s, int d) { 
     // Mark all the vertices as not visited 
     boolean visited[] = new boolean[V]; 
     Arrays.fill(visited, false); 

     // Call the recursive method to count all paths 
     int pathCount = 0; 
     pathCount = countPathsUtil(s, d, visited, pathCount); 
     return pathCount; 
    } 

    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(g.countPaths(s, d)); 
    } 
}