我们用字符串代表图的顶点(vertax)，来模拟学校中Classroom, Square, Toilet, Canteen, South Gate, North Gate几个地点，然后计算任意两点之间的最短路径。
如，我想从North Gate去Canteen, 程序的输出结果应为：
:
首先定义一个算法接口Algorithm:
{/*** 执行算法*/void perform(Graph g, String sourceVertex);/*** 得到路径*/Map<String, String> getPath();}
然后，定义图:
/** * (无向)图 */{// 图的起点private String firstVertax;// 邻接表private Map<String, List<String>> adj = new HashMap<>();// 遍历算法private Algorithm algorithm;public Graph(Algorithm algorithm) {this.algorithm = algorithm;}/*** 执行算法*/() {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;}/*** 添加一条边*/(String fromVertex, String toVertex) {if (firstVertax == null) {firstVertax = fromVertex;}adj.get(fromVertex).add(toVertex);adj.get(toVertex).add(fromVertex);}/*** 添加一个顶点*/(String vertex) {adj.put(vertex, new ArrayList<>());}public Map<String, List<String>> getAdj() {return adj;}}
这里我们使用策略设计模式，将算法与Graph类分离，通过在构造Graph对象时传入一个Algorithm接口的实现来为Graph选择遍历算法。
public Graph(Algorithm algorithm) {this.algorithm = algorithm;}
无向图的存储结构为邻接表，，这里用一个Map表示邻接表，map的key是学校地点(String)，value是一个与该地点相连通的地点表(List<String>)。
, adj = new HashMap<>();
然后，编写Algorithm接口的BFS实现：
/** * 封装BFS算法 */{// 保存已经访问过的地点private List<String> visitedVertex;// 保存最短路径private Map<String, String> path;(Graph g, String sourceVertex) {if (null == visitedVertex) {visitedVertex = new ArrayList<>();}if (null == path) {path = new HashMap<>();}BFS(g, sourceVertex);}@Overridepublic Map<String, String> getPath() {return path;}(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，直到队列为空。
测试用例：
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() {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());}}
而这些目标凝结成希望的萌芽，在汗水与泪水浇灌下，绽放成功之花。
