0

我在一个 java 项目中工作，我想在一个图中显示所有路径（这个图使用邻接矩阵表示）。我尝试使用 DFS 算法，但如何显示所有这些路径？

我试试这个

for(int i=0; i<nr; i++) 
        for(int j=0; j<nr; j++)
            dfs(i,j);

DFS算法是这样的：

public static void dfs(int src, int dst) {

        al.add(src);
        size++;
        color[src] = true;
        if (src == dst) {       // tests for base condition to stop
            for (Integer i : al) {
                //     Prints the path
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }
        for (int I = 0; I < nr; I++) {
            if (matrix[src][I].contains("1")  {
                if (color[I] == false) {
                    dfs(I, dst);        // These lines do
                    color[I] = false;   // main job of backtracking
                    size--;
                    al.remove(size);
                }
            }
        }
    }

如果我调用函数 dfs(2,3) 结果很好，但该循环似乎不起作用。

4

1 回答 1

0

在我看来，在尝试查找路径时，您会混淆两件事，两者都存储在color[I]索引中。

一，你需要一些东西（颜色会做）来存储你是否访问过节点。看来您的dfs例程已准备好为已访问的节点“着色”，以及“取消着色”未访问的节点。

但不明显的是，您似乎没有正在搜索的邻接矩阵。您能否指出检查两个节点是否连接的代码行？如果没有决定何时知道何时适合跟随一个节点到达另一个节点，您就会冒着简单地遍历最大数量的可能互连（而不是存在的互连）的风险。

于 2013-10-17T18:38:42.980 回答