本文實(shí)例講述了Java實(shí)現(xiàn)利用廣度優(yōu)先遍歷(BFS)計(jì)算最短路徑的方法。分享給大家供大家參考。具體分析如下：
我們用字符串代表圖的頂點(diǎn)(vertax)，來模擬學(xué)校中Classroom, Square, Toilet, Canteen, South Gate, North Gate幾個(gè)地點(diǎn)，然后計(jì)算任意兩點(diǎn)之間的最短路徑。
如下圖所示：
如，我想從North Gate去Canteen, 程序的輸出結(jié)果應(yīng)為：
|
1
2
3
4
|
BFS: From [North Gate] to [Canteen]:North GateSquareCanteen |
首先定義一個(gè)算法接口Algorithm:
|
1
2
3
4
5
6
7
8
9
10
|
public interface Algorithm { /** * 執(zhí)行算法 */ 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
|
/** * (無(wú)向)圖 */public class Graph { // 圖的起點(diǎn) private String firstVertax; // 鄰接表 private Map<String, List<String>> adj = new HashMap<>(); // 遍歷算法 private Algorithm algorithm; public Graph(Algorithm algorithm) { this.algorithm = algorithm; } /** * 執(zhí)行算法 */ public void done() { algorithm.perform(this, firstVertax); } /** * 得到從起點(diǎn)到{@code vertex}點(diǎn)的最短路徑 * @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); } /** * 添加一個(gè)頂點(diǎn) */ public void addVertex(String vertex) { adj.put(vertex, new ArrayList<>()); } public Map<String, List<String>> getAdj() { return adj; }} |
這里我們使用策略設(shè)計(jì)模式，將算法與Graph類分離，通過在構(gòu)造Graph對(duì)象時(shí)傳入一個(gè)Algorithm接口的實(shí)現(xiàn)來為Graph選擇遍歷算法。
|
1
2
3
|
public Graph(Algorithm algorithm) { this.algorithm = algorithm; } |
無(wú)向圖的存儲(chǔ)結(jié)構(gòu)為鄰接表，這里用一個(gè)Map表示鄰接表，map的key是學(xué)校地點(diǎn)(String)，value是一個(gè)與該地點(diǎn)相連通的地點(diǎn)表(List<String>)。
|
1
2
|
// 鄰接表 private Map<String, List<String>> adj = new HashMap<>(); |
然后，編寫Algorithm接口的BFS實(shí)現(xiàn)：
|
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 { // 保存已經(jīng)訪問過的地點(diǎn) 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<>(); // 標(biāo)記起點(diǎn) visitedVertex.add(sourceVertex); // 起點(diǎn)入列 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. 將起點(diǎn)標(biāo)記為已訪問并放入隊(duì)列。
2. 從隊(duì)列中取出一個(gè)頂點(diǎn)，得到與該頂點(diǎn)相通的所有頂點(diǎn)。
3. 遍歷這些頂點(diǎn)，先判斷頂點(diǎn)是否已被訪問過，如果否，標(biāo)記該點(diǎn)為已訪問，記錄當(dāng)前路徑，并將當(dāng)前頂點(diǎn)入列。
4. 重復(fù)2、3，直到隊(duì)列為空。
測(cè)試用例：
|
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()); } } |
希望本文所述對(duì)大家的java程序設(shè)計(jì)有所幫助。
