本文實例講述了Java實現利用廣度優先遍歷(BFS)計算最短路徑的方法。分享給大家供大家參考。具體分析如下：
我們用字符串代表圖的頂點(vertax)，來模擬學校中Classroom, Square, Toilet, Canteen, South Gate, North Gate幾個地點，然后計算任意兩點之間的最短路徑。
如下圖所示：
如，我想從North Gate去Canteen, 程序的輸出結果應為：
|
1
2
3
4
|
BFS: From [North Gate] to [Canteen]:North GateSquareCanteen |
首先定義一個算法接口Algorithm:
|
1
2
3
4
5
6
7
8
9
10
|
public interface Algorithm { /** * 執行算法 */ void perform(Graph g, String sourceVertex); /** * 得到路徑 */ Map<String, String> getPath();} |
然后，定義圖:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
/** * (無向)圖 */public class Graph { // 圖的起點 private String firstVertax; // 鄰接表 private Map<String, List<String>> adj = new HashMap<>(); // 遍歷算法 private Algorithm algorithm; public Graph(Algorithm algorithm) { this.algorithm = algorithm; } /** * 執行算法 */ public void done() { algorithm.perform(this, firstVertax); } /** * 得到從起點到{@code vertex}點的最短路徑 * @param vertex * @return */ public Stack<String> findPathTo(String vertex) { Stack<String> stack = new Stack<>(); stack.add(vertex); Map<String, String> path = algorithm.getPath(); for (String location = path.get(vertex) ; false == location.equals(firstVertax) ; location = path.get(location)) { stack.push(location); } stack.push(firstVertax); return stack; } /** * 添加一條邊 */ public void addEdge(String fromVertex, String toVertex) { if (firstVertax == null) { firstVertax = fromVertex; } adj.get(fromVertex).add(toVertex); adj.get(toVertex).add(fromVertex); } /** * 添加一個頂點 */ public void addVertex(String vertex) { adj.put(vertex, new ArrayList<>()); } public Map<String, List<String>> getAdj() { return adj; }} |
這里我們使用策略設計模式，將算法與Graph類分離，通過在構造Graph對象時傳入一個Algorithm接口的實現來為Graph選擇遍歷算法。
|
1
2
3
|
public Graph(Algorithm algorithm) { this.algorithm = algorithm; } |
無向圖的存儲結構為鄰接表，這里用一個Map表示鄰接表，map的key是學校地點(String)，value是一個與該地點相連通的地點表(List<String>)。
|
1
2
|
// 鄰接表 private Map<String, List<String>> adj = new HashMap<>(); |
然后，編寫Algorithm接口的BFS實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
/** * 封裝BFS算法 */public class BroadFristSearchAlgorithm implements Algorithm { // 保存已經訪問過的地點 private List<String> visitedVertex; // 保存最短路徑 private Map<String, String> path; @Override public void perform(Graph g, String sourceVertex) { if (null == visitedVertex) { visitedVertex = new ArrayList<>(); } if (null == path) { path = new HashMap<>(); } BFS(g, sourceVertex); } @Override public Map<String, String> getPath() { return path; } private void BFS(Graph g, String sourceVertex) { Queue<String> queue = new LinkedList<>(); // 標記起點 visitedVertex.add(sourceVertex); // 起點入列 queue.add(sourceVertex); while (false == queue.isEmpty()) { String ver = queue.poll(); List<String> toBeVisitedVertex = g.getAdj().get(ver); for (String v : toBeVisitedVertex) { if (false == visitedVertex.contains(v)) { visitedVertex.add(v); path.put(v, ver); queue.add(v); } } } }} |
其中，path是Map類型，意為從 value 到 key 的一條路徑。
BFS算法描述：
1. 將起點標記為已訪問并放入隊列。
2. 從隊列中取出一個頂點，得到與該頂點相通的所有頂點。
3. 遍歷這些頂點，先判斷頂點是否已被訪問過，如果否，標記該點為已訪問，記錄當前路徑，并將當前頂點入列。
4. 重復2、3，直到隊列為空。
測試用例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
String[] vertex = {"North Gate", "South Gate", "Classroom", "Square", "Toilet", "Canteen"}; Edge[] edges = { new Edge("North Gate", "Classroom"), new Edge("North Gate", "Square"), new Edge("Classroom", "Toilet"), new Edge("Square", "Toilet"), new Edge("Square", "Canteen"), new Edge("Toilet", "South Gate"), new Edge("Toilet", "South Gate"), };@Test public void testBFS() { Graph g = new Graph(new BroadFristSearchAlgorithm()); addVertex(g); addEdge(g); g.done(); Stack<String> result = g.findPathTo("Canteen"); System.out.println("BFS: From [North Gate] to [Canteen]:"); while (!result.isEmpty()) { System.out.println(result.pop()); } } |
希望本文所述對大家的java程序設計有所幫助。
