新・アルゴリズムとデータ構造入門Java編14: 幅優先探索・深さ優先探索

準備：
・空のキューを用意して、最初の頂点をキューに追加
・訪問済みかどうかを記録する配列を未訪問で初期化し、最初の頂点を訪問済みに設定

探索：
・キューが空になるまで、以下のことを繰り返す
1. キューから頂点を取り出し、頂点に対する処理をおこなう
2. 隣接する頂点を順番に見て、もしその頂点が未訪問であれば、訪問済みに設定してキューに追加する

グラフの各頂点に対して辺で結ばれているすべての頂点を並べたリストのことを隣接リストといいます。隣接リスト g において、頂点 u に隣接する頂点のリストはインデックスが u の場所に格納されています。

5 4 1
1 2
1 3
2 4
2 5

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.ArrayDeque;

public class Main {

    static void printVertex(int v) {
        System.out.println("頂点 " + (v + 1) + " を探索");
    }

    static void bfs(int n, List<List<Integer>> g, int s) {
        // 空のキュー q を用意
        Queue<Integer> q = new ArrayDeque<>();
        // 最初の頂点 s をキューに追加
        q.add(s);
        // 訪問済みかどうかを表す配列 visited を用意
        boolean[] visited = new boolean[n];
        // 最初の頂点 s を訪問済みにする
        visited[s] = true;

        // キューが空になるまで
        while (!q.isEmpty()) {
            // キューから頂点 v を取り出す
            int v = q.poll();
            // 頂点 v を探索
            printVertex(v);
            // 隣接する頂点 u を順に見る
            for (int u : g.get(v)) {
                // もし頂点 u が未訪問であれば
                if (!visited[u]) {
                    // 頂点 u を訪問済みにして
                    visited[u] = true;
                    // 頂点 u をキューに追加
                    q.add(u);

                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(), m = sc.nextInt(), s = sc.nextInt() - 1;
        List<List<Integer>> graph = new ArrayList<List<Integer>>(n);

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt() - 1, b = sc.nextInt() - 1;
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        bfs(n, graph, s);

        sc.close();
    }
}