您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 圖論演算法：廣度優先搜尋 (BFS) 計算最短路徑完整實現

編輯：Java 相關知識

問題背景

在無權無向圖中尋找兩點間最短路徑（邊數最少），BFS 是最優選擇。時間複雜度 O(V+E)，空間 O(V)。

圖的表示：鄰接表


public class Graph {
    private String startVertex;
    private final Map> adj = new HashMap<>();
    private final Algorithm algorithm; // 策略模式注入演算法
    
    public Graph(Algorithm algorithm) { this.algorithm = algorithm; }
    
    public void addVertex(String v) { adj.putIfAbsent(v, new ArrayList<>()); }
    
    public void addEdge(String from, String to) {
        if (startVertex == null) startVertex = from;
        adj.get(from).add(to);
        adj.get(to).add(from); // 無向圖
    }
    
    public Map> getAdj() { return adj; }
    public String getStartVertex() { return startVertex; }
    
    // 執行演算法
    public void execute() { algorithm.perform(this, startVertex); }
    
    // 根據前驅映射重構路徑
    public Stack findPathTo(String target) {
        Stack path = new Stack<>();
        path.push(target);
        Map parent = algorithm.getPath();
        for (String v = parent.get(target); !v.equals(startVertex); v = parent.get(v)) {
            path.push(v);
        }
        path.push(startVertex);
        return path;
    }
}

演算法介面設計（策略模式）


public interface Algorithm {
    void perform(Graph g, String source);
    Map getPath(); // 返回 child -> parent 映射
}

BFS 核心實現


public class BFSAlgorithm implements Algorithm {
    private final List visited = new ArrayList<>();
    private final Map parent = new HashMap<>(); // child -> parent
    
    @Override
    public void perform(Graph g, String source) {
        visited.clear();
        parent.clear();
        
        Queue queue = new LinkedList<>();
        visited.add(source);
        queue.offer(source);
        
        while (!queue.isEmpty()) {
            String current = queue.poll();
            for (String neighbor : g.getAdj().get(current)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    parent.put(neighbor, current); // 記錄前驅
                    queue.offer(neighbor);
                }
            }
        }
    }
    
    @Override
    public Map getPath() { return parent; }
}

BFS 執行流程圖解

圖結構：
North Gate -- Classroom -- Toilet -- South Gate
     |            |           |
     |            |           |
   Square ----- Canteen      |
     |                        |
     +------------------------+

起點: North Gate
目標: Canteen

BFS 展開：
層 0: [North Gate]
層 1: [Classroom, Square]        <- 從 North Gate 可達
層 2: [Toilet, Canteen]          <- 從 Classroom/Square 可達
找到 Canteen！路徑長度 = 2

前驅映射：
Classroom -> North Gate
Square -> North Gate
Toilet -> Classroom (或 Square)
Canteen -> Square

路徑重構：Canteen -> Square -> North Gate

完整測試用例


public class BFSTest {
    @Test
    public void testShortestPath() {
        String[] vertices = {"North Gate", "South Gate", "Classroom", "Square", "Toilet", "Canteen"};
        String[][] edges = {
            {"North Gate", "Classroom"},
            {"North Gate", "Square"},
            {"Classroom", "Toilet"},
            {"Square", "Toilet"},
            {"Square", "Canteen"},
            {"Toilet", "South Gate"}
        };
        
        Graph g = new Graph(new BFSAlgorithm());
        Arrays.stream(vertices).forEach(g::addVertex);
        for (String[] e : edges) g.addEdge(e[0], e[1]);
        
        g.execute();
        Stack path = g.findPathTo("Canteen");
        
        System.out.print("BFS: From [North Gate] to [Canteen]: ");
        while (!path.isEmpty()) System.out.print(path.pop() + " ");
        // 輸出: North Gate Square Canteen
    }
}

BFS vs DFS vs Dijkstra 選擇指南

演算法	適用圖類型	最短路徑定義	時間複雜度	空間
BFS	無權無向/有向	邊數最少	O(V+E)	O(V)
DFS	無權	非最短（任意路徑）	O(V+E)	O(V)
Dijkstra	帶權非負	權重和最小	O(E log V)	O(V)
Bellman-Ford	帶權含負權	權重和最小	O(VE)	O(V)
A*	帶權+啟發式	權重和最小	視啟發式	O(V)

優化與變體

雙向 BFS（大圖優化）


// 同時從起點和終點展開，相遇時結束
// 空間/時間約減半，適用於社交網絡六度分隔等大圖
Queue qStart = new LinkedList<>(), qEnd = new LinkedList<>();
Set vStart = new HashSet<>(), vEnd = new HashSet<>();
Map pStart = new HashMap<>(), pEnd = new HashMap<>();

qStart.offer(start); vStart.add(start);
qEnd.offer(end); vEnd.add(end);

while (!qStart.isEmpty() && !qEnd.isEmpty()) {
    // 總是展開較小的隊列
    if (expandOneLevel(qStart, vStart, vEnd, pStart, g)) return buildPath(pStart, pEnd, meetPoint);
    if (expandOneLevel(qEnd, vEnd, vStart, pEnd, g)) return buildPath(pStart, pEnd, meetPoint);
}