java - 深度优先搜索给出错误的输出

Question

我编写了下面的代码来使用深度优先搜索遍历上面的图，我得到的输出是 0 1 3 6 4 5 2 。

我想检查使用DFS是否是正确的遍历，如果不是，正确的遍历是什么。另外，我需要在代码中进行哪些更改才能带来正确的输出。

public void DFSTraversal()
{

    int v;
    int vFirst = 0;
    Stack<Integer> st = new Stack<Integer>();
    Boolean[] visited = new Boolean[vert];
    for(int j = 0 ; j < vert ; j++ )
    {
        visited[j] = false;
    }

    // st is a stack
    st.push(vFirst);

    while(!st.isEmpty())
    {
        v = st.peek();
        if(!visited[v])
        {
            System.out.printf("%d " , +v);
            visited[v]=true;
        }

            for (int i = 0; i < vert; i++)
            {
                if ((matrix[v][i] == 1) && (!visited[i]))
                {
                    st.push(i);
                    visited[i] = true;
                    System.out.printf("%d ", +i);
                    v = i;
                }
            }

            st.pop();
    }

邻接度量

`0 1 1 0 0 0 0`
`1 0 0 1 1 1 0`
`1 0 0 0 0 0 1`
`0 1 0 0 0 0 1`
`0 1 0 0 0 0 1`
`0 1 0 0 0 0 0`
`0 0 1 1 1 0 0`

Answer 1

从图中，假设顶点的边按其指向的节点按递增顺序排列，则正确的输出为:0 1 3 6 2 4 5。

您遇到的问题是，您将动态编程方法与堆栈混合在一起，以及在所有顶点上重写 for 循环的迭代方法。如果一个顶点与另一个索引比自己索引低的顶点有边，那么它不会立即访问该节点，而是诉诸堆栈；具有未访问边的第一条边的最后一个顶点。

您可以通过仅使用动态编程方法来解决此问题，然后向后循环边缘，如果未访问它们，则将它们插入堆栈。这会将边缘保留到堆栈顶部的最低值顶点，准备在下一次迭代中访问。

您的深度优先搜索循环将变为:

while (!st.isEmpty()) {
  int vertex = st.pop();
  if (!visited[vertex]) {
    System.out.printf("%d ", vertex);
    visited[vertex] = true;

    for (int i = numVertices - 1; i >= 0; --i) {
      if (edges[vertex][i] == 1 && !visited[i]) {
        st.push(i);
      }
    }
  }
}

这样，您只使用单个循环(您的 while 循环)，它会不断从堆栈中弹出。当访问一个顶点时，它将以相反的顺序将所有未访问的和连接的顶点压入堆栈。这意味着顶点中编号最小的子节点是下一个要访问的子节点 (DFS)。如果一个顶点被访问并且在堆栈中较深，那么当再次访问时它会被忽略，它的子顶点也是如此(它们也已经被访问过)。

然后，通过将堆栈设置为队列并按升序添加顶点，可以非常简单地将其更改为“面包优先搜索”。