本文转载请联系Beta学习JAVA公众号。前言在前面两篇文章中，我们可以通过深度优先搜索在图中找到一条从顶点v到顶点w的路径，但是深度优先搜索与顶点的输入有很大关系，找到的路径不一定betheshortest是的，通常我们经常需要求图中的最短路径，比如：map函数。这里需要用到广度优先搜索算法广度优先搜索还是使用之前定义的APIpublicclassPaths{Paths(Graphgraph,ints);booleanhasPathTo(intv);>pathTo(intv);//如果有路径，则返回路径}在广度优先搜索中，为了找到最短路径，我们需要按照起点的顺序遍历所有的顶点，而不是使用递归来实现它；算法思想：用队列保存标记过但邻接表未遍历的顶点。取出队列中的下一个顶点v并标记它。将与v相邻的所有未标记顶点添加到队列中。在这个算法中，为了保存路径，我们还是需要用到一个边数组edgeTo[]，用一个父链树来表示从根节点到所有相连顶点的最短路径。publicclassBreadthFirstPaths{privatebooleanmarked[];privateint[]edgeTo;privateints;privateQueuequeue=newLinkedListQueue<>();publicBreadthFirstPaths(Graphgraph,ints){this.s=s;this.marked=newboolean[graph.V()];this.edgeTo=newint[graph.V()];bfs(graph,s);}privatevoidbfs(Graphgraph,ints){this.marked[s]=true;this.queue.enqueue(s);while(!this.queue.isEmpty()){Integerv=this.queue.dequeue();for(intw:graph.adj(v)){if(!this.marked[w]){this.marked[w]=true;this.edgeTo[w]=v;this.queue.enqueue(w);}}}}publicbooleanhasPathTo(intv){returnthis.marked[v];}publicIterablepathTo(intv){if(!hasPathTo(v)){thrownewIllegalStateException("s无法到达v");}Stackstack=newLinkedListStack<>();stack.push(v);while(edgeTo[v]!=s){stack.push(edgeTo[v]);v=edgeTo[v];}stack.push(s);returnstack;}}下图是一栏，我们来看看广度优先搜索跑道单元测试的代码:@Testpublicvoidtest(){Graphgraph=newGraph(8);graph.addEdge(0,1);graph.addEdge(0,2);graph.addEdge(0,5);图表h.addEdge(1,3);graph.addEdge(2,4);graph.addEdge(4,3);graph.addEdge(5,3);graph.addEdge(6,7);BreadthFirstPathspaths=newBreadthFirstPaths(图,0);System.out.println(paths.hasPathTo(5));System.out.println(paths.hasPathTo(2));System.out.println(paths.hasPathTo(6));paths.pathTo(5).forEach(System.out::print);System.out.println();paths.pathTo(4).forEach(System.out::print);System.out.println();paths.pathTo(2).forEach(System.out::print);System.out.println();paths.pathTo(3).forEach(System.out::print);}执行结果与运行轨迹一致我们分析了最近几篇文章学习的图算法都是用数字作为顶点的，因为用数字来实现这些算法非常简单方便，但是在实际场景中，通常都是用字符作为顶点，而不是数字，比如：上的位置地图，电影和演员之间的关系。为了满足实际场景，我们只需要在数字和字符串之间做一个映射即可。这时候我们就会想到上一篇文章实现的map（通过二叉树实现map，红黑树实现map，hash表实现map等，有兴趣的同学可以浏览一下），以及使用Map来维护字符串和数字之间的映射关系。publicinterfaceSymbolGraph{booleancontains(Stringkey);//判断是否存在顶点intindex(Stringkey);//通过名称返回对应的数字顶点Stringname(intv);//通过数字顶点返回对应的字符名称Graphgraph();}实现思路：用Map保存字符串-数字映射，key为字符串，value为数字。使用数组反向映射数字字符串。数组下标对应数字顶点，值对应字符串名称。假设构造图的顶点构造边用字符串表示，如：a,b,c,d\nb,a,h,l,p\ng,s,z使用每个的第一个字符串以\n分隔的线段表示顶点v，后者表示与顶点v相连的相邻顶点；实际过程可以根据具体情况确定，不一定是这样的字符串，可以来自数据库，也可以来自网络请求。代码实际如下：publicclassSymbolGraph{privateMapmap=newRedBlack23RedBlackTreeMap<>();privateString[]keys;privateGraphgraph;publicSymbolGraph(Stringtext){Arrays.stream(text.split("\n")).forEach(line->{String[]split=line.split(",");for(inti=0;i{this.keys[this.map.get(key)]=key;});this.graph=newGraph(this.keys.length);Arrays.stream(text.split("\n")).forEach(line->{String[]split=line.split(",");intv=this.map.get(split[0]);for(inti=1;i
