使用Java和带有邻接列表的DFS计算图形中两个顶点之间的所有可能路径

Question

我试图使用java解决geeksforgeeks下面的这个问题

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

但问题是每个递归调用之间pathCount为0。以下是我的完整代码：

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

}

其余的代码是正确的，我的pathCount值最后返回0。

请帮忙进行简单的修复！

Answer 1

Java是按值传递而不是通过引用传递所以这个代码

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

意味着无论您的countPathsUtil方法发生什么，pathCount将始终返回为0.尝试更改您的countPathsUntil方法以返回pathCount。

Answer 2

感谢@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));
    }
}