0

私は幅優先検索に取り組んでおり、すべてのエッジを印刷するために BFS を作成しようとしました。最初のバージョンは、頂点に NOT_VISIT (初期状態)、VISIT、および PROCESSED の 3 つの状態がある Algorithm book から採用されています。頂点は、最初に見たときは「VISIT」です。頂点は、隣接する頂点がすべて訪問されると「処理済み」になります。2 番目のバージョンは私が書いたもので、初期状態と VISITED の 2 つの状態のみを使用します。どちらも機能します：

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 つの状態が必要な場合の例を教えてください。

4

1 に答える 1

2

通常、BFS がどのように機能しているかを視覚化するために、中間状態 (この場合は「Visit」、色を使用してノードをマークする場合は「Gray」) を追加します。標準実装では必要ありません（中間状態を経由せずに「訪問済み」に切り替えてもかまいません）。

自分で見ることができます。BFS に従ってみてください (紙と鉛筆でもできます)。「Visit」状態のノードは、ソースから等距離にあることがわかります (具体的には、最大差は 1 です)。教育目的で、DFS で同じことを行うのは良いことです (したがって、幅優先検索と深さ優先検索の違いを観察できます)。

于 2014-05-13T14:39:12.400 に答える