java - 邻接矩阵 DFS 遍历以在有向图 (Java) 中查找从 x 到 y 的路径数

Question

private Stack<Integer> stack = new Stack<Integer>();

public int dfs(int maxDepth){ //path A-C with 'x' stops maximum
    int src = 0;
    int dest = 2;
    int i;
    int countDepth = 0;
    int countPaths = 0;
    int element;

    stack.add(src);

    while(!stack.isEmpty() && countDepth <= maxDepth)
    {
        element = stack.pop();
        i = 0;

        while(i < gSize) // i < 5
        {
            if(arr[element][i] > 0)
            {
                stack.add(i);

                if(i == dest)
                    countPaths++;
            }       

            i++;
        }
        countDepth++;
    }
    return countPaths;
}

这段代码的想法是找出从 A 点到 B 点(任意点 A 和 B)有多少条路径，最多有“x”个停靠点。所以从C到C最多停3站，有两种可能:

C -> D -> C(2 站)

C -> D -> E -> C(3 站)

从 A 到 C，最多停 3 站，有 3 种可能性:

A -> B -> C(2 站)

A -> D -> C(2 站)

A -> E -> B -> C(3 站)

但是，它只找到一个，程序就停止了。这是因为我的 countDepth 变量。它在 depth > maxDepth 时停止。换句话说，它并没有像我想要的那样遍历我的图表，它沿着一个分支向下移动，然后程序停止。我如何正确跟踪它当前的深度？谢谢!

Answer 1

每次从堆栈中弹出一些东西时，您都在增加深度，并且注意到您永远不会减少它。所以你的for循环只会执行gSize次。

虽然在深度优先搜索期间，一旦到达路径的末端(最大长度或死胡同)，您需要返回到树上，并且您的深度需要减少。

我建议的方法是将节点和深度都存储在堆栈中。

所以首先你推送 (src, 0)入栈。

然后你说(node, i)出栈，如果 i < gSize然后推(child, i + 1)每个 child 入栈的 node .如果node == dest , 加一。