java - 广度优先搜索 : How many states of a vertex are needed?

Question

我正在研究广度优先搜索，我尝试编写 BFS 来打印所有边。第一个版本改编自算法书，其中一个顶点有 3 个状态:NOT_VISIT(初始状态)、VISIT 和 PROCESSED。当您第一次看到顶点时，它就是“VISIT”。当一个顶点的所有邻居都被访问时，它是“已处理”的。第二个版本是我写的那个，只使用 2 个状态:初始状态和 VISITED。两者都有效:

public static void BFS(Graph g, int start) {
    boolean[] visit = new boolean[g.size()];
    boolean[] process = new boolean[g.size()];
    List<Integer> queue = new ArrayList<Integer>();
    queue.add(start);
    visit[start] = true;
    while (!queue.isEmpty()) {
        int currentVertex = queue.remove(0);
        process[currentVertex] = true;
        List<Integer> adj = g.getAdjacents(currentVertex);
        if (adj != null) {
            for (Integer i : adj) {
                if (visit[i] == false) {
                    visit[i] = true;
                    queue.add(i);
                }
                if (process[i] == false) {
                    System.out.println(currentVertex + " --- "
                            + i);

                }
            }
        }
    }
}




public static int BFS2(Graph g, int start) {
    List<Integer> queue = new ArrayList<Integer>();
            boolean[] visited = new boolean[g.size()];
    queue.add(start);
    while (!queue.isEmpty()) {
        int v = queue.remove(0);
        visited[v] = true;// only mark visited[v] = true when processing all
                            // its neighbors
        List<Integer> adj = g.getAdjacents(v);
        if (adj != null) {
            for (Integer i : adj) {
                if (!visited[i]) {
                    queue.add(i);
                    System.out.println(v + " --- "
                            + i);
                }
            }
        }
      }
  }

我的问题是:什么时候需要 BFS 中的顶点有 3 个状态？当我们需要 3 个状态时，您能举个例子吗？

Answer 1

通常您添加中间状态(在您的情况下为“访问”，在使用颜色标记节点时通常为“灰色”)只是为了可视化 BFS 的工作方式。在标准实现中，这是没有必要的(您可以切换到“已访问”，而无需经过中间状态。)

你自己看吧，尽量跟着BFS走(纸笔也行)。您将看到处于“访问”状态的节点与源的距离相等(具体而言，最大差异为 1)。出于教育目的，最好对 DFS 做同样的事情(这样您就可以观察广度优先和深度优先搜索之间的区别)。