圖的廣度優先搜索（BFS）Java 實現：鄰接矩陣與隊列實戰

圖的存儲：鄰接矩陣

適用於稠密圖，空間 O(V²)。頂點信息存一維數組 vertices，邊關係存二維數組 arcs[i][j]（1 表示連通，0 表示不連通）。

BFS 算法流程

1. 初始化訪問標記數組 visited[] 為 false。
2. 創建隊列 Queue<Integer>。
3. 對每個未訪問頂點：標記、入隊、輸出。
4. 隊列非空時循環：出隊頂點 v，遍歷其所有鄰接點 w，未訪問則標記、入隊、輸出。

完整代碼實現

package com.teradata.lsw.sort;

import java.util.*;

public class BFS {
    private Object[] vertices;      // 頂點信息
    private int[][] arcs;           // 鄰接矩陣
    private int vexnum;             // 頂點數
    private boolean[] visited;      // 訪問標記
    private List<Object> temp = new ArrayList<>(); // 遍歷結果

    public BFS(int n) {
        vexnum = n;
        vertices = new Object[n];
        arcs = new int[n][n];
        visited = new boolean[n];
        for (int i = 0; i < n; i++) 
            Arrays.fill(arcs[i], 0);
    }

    public void addVertex(Object[] objs) { this.vertices = objs; }

    public void addEdge(int i, int j) {
        if (i == j) return;
        arcs[i][j] = 1;
        arcs[j][i] = 1; // 無向圖
    }

    // 獲取第一個鄰接點
    public int firstAdjVex(int i) {
        for (int j = 0; j < vexnum; j++) 
            if (arcs[i][j] > 0) return j;
        return -1;
    }

    // 獲取下一個鄰接點
    public int nextAdjVex(int i, int k) {
        for (int j = k + 1; j < vexnum; j++) 
            if (arcs[i][j] > 0) return j;
        return -1;
    }

    public void bfs() {
        for (int i = 0; i < vexnum; i++) visited[i] = false;
        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < vexnum; i++) {
            if (!visited[i]) {
                visited[i] = true;
                visit(i);
                q.add(i);
                while (!q.isEmpty()) {
                    int j = q.remove();
                    if (temp.size() == vexnum) return; // 全遍歷完提前退出
                    for (int k = firstAdjVex(j); k >= 0; k = nextAdjVex(j, k)) {
                        if (!visited[k]) {
                            visited[k] = true;
                            visit(k);
                            q.add(k);
                        }
                    }
                }
            }
        }
    }

    private void visit(int i) {
        temp.add(vertices[i]);
        System.out.print(vertices[i] + " ");
    }

    public static void main(String[] args) {
        BFS g = new BFS(8);
        Character[] vs = {'A','B','C','D','E','F','G','H'};
        g.addVertex(vs);
        g.addEdge(0,1); g.addEdge(0,2);
        g.addEdge(1,3); g.addEdge(1,4);
        g.addEdge(3,5); g.addEdge(4,5);
        g.addEdge(2,6); g.addEdge(2,7);
        System.out.println("圖的廣度優先遍歷：");
        g.bfs(); // 輸出: A B C D E F G H
    }
}

關鍵點解析

• 多連通分量：外層 for 循環確保所有連通分量均被遍歷。
• 鄰接點遍歷：firstAdjVex/nextAdjVex 封裝矩陣掃描邏輯，便於改為鄰接表。
• 隊列選擇：LinkedList 實現 Queue 接口，O(1) 入隊出隊。

複雜度

• 時間：O(V²) —— 矩陣掃描鄰接點；改用鄰接表可降為 O(V+E)。
• 空間：O(V) —— visited 數組、隊列、結果列表。

擴展建議

• 將圖結構與遍歷算法解耦（Strategy 模式），支援 DFS、拓撲排序等。
• 使用 Map<V, List<V>> 鄰接表存儲稀疏圖。
• 泛型化頂點類型 <V> 提升復用性。