0

I am working on Breadth First Search and I tried to write BFS to print all the edges. The first version is adapted from Algorithm book in which a vertex has 3 states: NOT_VISIT (initial state), VISIT and PROCESSED. A vertex is 'VISIT' when you first see it. A vertex is 'PROCESSED' when all of its neighbors are visited. The second version is the one that I wrote, use only 2 states: Initial state and VISITED. Both work:

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);
                }
            }
        }
      }
  }

My question is: When is it necessary to have 3 states for a vertex in BFS ? Can you give an example when we need 3 states ?

4

1 回答 1

2

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

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

于 2014-05-13T14:39:12.400 回答