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

我编写了以下代码，使用深度优先搜索遍历上述图形，我得到的输出是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`

最佳答案

从图片中，假设顶点的边缘按其指向的节点的顺序递增，则正确的输出为：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）。如果顶点被访问并且在堆栈中更深，则再次访问该顶点时会被忽略，其子顶点也会被忽略（它们也已经被访问过）。

然后，可以通过使堆栈成为队列并按递增顺序添加顶点，将其更改为“面包优先搜索”。

关于java - 深度优先搜索给出错误的输出，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54071958/