图--02---图的搜索、路径查找

文章目录图的搜索深度优先搜索先找子结点然后找兄弟结点API设计代码图----Graph深度优先搜索----DepthFirstSearch测试广度优先搜索先找兄弟结点然后找子结点API设计思路分析和 二叉树的层序遍历----广度优先思路一样树--05---二叉树--02---二叉搜索树(BST)遍历实现步骤创建辅助队列做排序代码测试:案例-畅通工程续1需求解题思路代码:路径查找需求:从s顶点到v顶点是否存在一条路径如果存在请找出这条路径。查找API设计思路分析:代码测试代码图的搜索在很多情况下我们需要遍历图得到图的一些性质例如找出图中与指定的顶点相连的所有顶点或者判定某个顶点与指定顶点是否相通是非常常见的需求。有关图的搜索最经典的算法有深度优先搜索和广度优先搜索接下来我们分别讲解这两种搜索算法。深度优先搜索广度优先搜索深度优先搜索先找子结点然后找兄弟结点所谓的深度优先搜索指的是在搜索时如果遇到一个结点既有子结点又有兄弟结点那么先找子结点然后找兄弟结点。很明显在由于边是没有方向的所以如果4和5顶点相连那么4会出现在5的相邻链表中5也会出现在4的相邻链表中那么为了不对顶点进行重复搜索应该要有相应的标记来表示当前顶点有没有搜索过可以使用一个布尔类型的数组 boolean[V] marked,索引代表顶点值代表当前顶点是否已经搜索如果已经搜索标记为true如果没有搜索标记为falseAPI设计代码图----Graphpackagegraph;importjava.util.Queue;importjava.util.concurrent.ConcurrentLinkedDeque;publicclassGraph{//顶点数目privatefinalintV;//边的数目privateintE;//邻接表privateQueueInteger[]adj;publicGraph(intV){//初始化顶点数量this.VV;//初始化边的数量this.E0;//初始化邻接表this.adjnewQueue[V];for(inti0;iadj.length;i){adj[i]newConcurrentLinkedDeque();}}//获取顶点数目publicintV(){returnV;}//获取边的数目publicintE(){returnE;}//向图中添加一条边 v-wpublicvoidaddEdge(intv,intw){//在无向图中边是没有方向的所以该边既可以说是从v到w的边又可以说是从w到v的边因此需要让w出现在v的邻接表中并且还要让v出现在w的邻接表中adj[v].offer(w);adj[w].offer(v);//边的数量1E;}//获取和顶点v相邻的所有顶点publicQueueIntegeradj(intv){returnadj[v];}}深度优先搜索----DepthFirstSearchpackagegraph;publicclassDepthFirstSearch{//索引代表顶点值表示当前顶点是否已经被搜索privateboolean[]marked;//记录有多少个顶点与s顶点相通privateintcount;//构造深度优先搜索对象使用深度优先搜索找出G图中s顶点的所有相邻顶点publicDepthFirstSearch(GraphG,ints){//初始化marked数组this.markednewboolean[G.V()];//初始化跟顶点s相通的顶点的数量this.count0;dfs(G,s);}//使用深度优先搜索找出G图中v顶点的所有相通顶点privatevoiddfs(GraphG,intv){//把v顶点标识为已搜索marked[v]true;for(Integerw:G.adj(v)){//判断当前w顶点有没有被搜索过如果没有被搜索过则递归调用dfs方法进行深度搜索if(!marked[w]){dfs(G,w);}}//相通顶点数量1count;}//判断w顶点与s顶点是否相通publicbooleanmarked(intw){returnmarked[w];}//获取与顶点s相通的所有顶点的总数publicintcount(){returncount;}}测试publicclassDepthFirstSearchTest{publicstaticvoidmain(String[]args){//准备Graph对象GraphGnewGraph(13);G.addEdge(0,5);G.addEdge(0,1);G.addEdge(0,2);G.addEdge(0,6);G.addEdge(5,3);G.addEdge(5,4);G.addEdge(3,4);G.addEdge(4,6);G.addEdge(7,8);G.addEdge(9,11);G.addEdge(9,10);G.addEdge(9,12);G.addEdge(11,12);//准备深度优先搜索对象DepthFirstSearchsearchnewDepthFirstSearch(G,0);//测试与某个顶点相通的顶点数量intcountsearch.count();System.out.println(与起点0相通的顶点的数量为:count);//测试某个顶点与起点是否相同booleanmarked1search.marked(5);System.out.println(顶点5和顶点0是否相通marked1);booleanmarked2search.marked(7);System.out.println(顶点7和顶点0是否相通marked2);}}广度优先搜索先找兄弟结点然后找子结点所谓的深度优先搜索指的是在搜索时如果遇到一个结点既有子结点又有兄弟结点那么先找兄弟结点然后找子结点。API设计思路分析和 二叉树的层序遍历----广度优先思路一样树–05—二叉树–02—二叉搜索树(BST)遍历实现步骤创建队列存储每一层的结点使用循环从队列中弹出一个结点获取当前结点的key如果当前结点的左子结点不为空则把左子结点放入到队列中如果当前结点的右子结点不为空则把右子结点放入到队列中创建辅助队列做排序代码packagegraph;importjava.util.Queue;importjava.util.concurrent.ConcurrentLinkedDeque;publicclassBreadthFirstSearch{//索引代表顶点值表示当前顶点是否已经被搜索privateboolean[]marked;//记录有多少个顶点与s顶点相通privateintcount;//用来存储待搜索邻接表的点privateQueueIntegerwaitSearch;//构造广度优先搜索对象使用广度优先搜索找出G图中s顶点的所有相邻顶点publicBreadthFirstSearch(GraphG,ints){this.markednewboolean[G.V()];this.count0;this.waitSearchnewConcurrentLinkedDequeInteger();bfs(G,s);}//使用广度优先搜索找出G图中v顶点的所有相邻顶点privatevoidbfs(Graphgraph,intv){//把当前顶点v标识为已搜索marked[v]true;//让顶点v进入队列待搜索waitSearch.offer(v);System.out.print(节点v广度遍历顺序为v);//通过循环如果队列不为空则从队列中弹出一个待搜索的顶点进行搜索while(!waitSearch.isEmpty()){//弹出一个待搜索的顶点IntegerwaitwaitSearch.poll();//遍历wait顶点的邻接表for(Integerw:graph.adj(wait)){// 该顶点还没被搜索过 对其进行搜索if(!marked(w)){marked[w]true;// 将节点放入堆栈中用于后续的获取该节点的子节点waitSearch.offer(w);//让相通的顶点1count;System.out.print(w);}}}System.out.println();}//判断w顶点与s顶点是否相通publicbooleanmarked(intw){returnmarked[w];}//获取与顶点s相通的所有顶点的总数publicintcount(){returncount;}}测试:packagegraph;publicclassBreadthFirstSearchTest{publicstaticvoidmain(String[]args){//准备Graph对象GraphGnewGraph(13);G.addEdge(0,5);G.addEdge(0,1);G.addEdge(0,2);G.addEdge(0,6);G.addEdge(5,3);G.addEdge(5,4);G.addEdge(3,4);G.addEdge(4,6);G.addEdge(7,8);G.addEdge(9,11);G.addEdge(9,10);G.addEdge(9,12);G.addEdge(11,12);//准备广度优先搜索对象BreadthFirstSearchsearchnewBreadthFirstSearch(G,0);//测试与某个顶点相通的顶点数量intcountsearch.count();System.out.println(与起点0相通的顶点的数量为:count);//测试某个顶点与起点是否相同booleanmarked1search.marked(5);System.out.println(顶点5和顶点0是否相通marked1);booleanmarked2search.marked(7);System.out.println(顶点7和顶点0是否相通marked2);}}案例-畅通工程续1某省调查城镇交通状况得到现有城镇道路统计表表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通但不一定有直接的道路相连只要互相间接通过道路可达即可。目前的道路状况9号城市和10号城市是否相通9号城市和8号城市是否相通在我们的测试数据文件夹中有一个trffic_project.txt文件它就是诚征道路统计表下面是对数据的解释需求总共有20个城市目前已经修改好了7条道路问9号城市和10号城市是否相通9号城市和8号城市是否相通解题思路创建一个图Graph对象表示城市分别调用addEdge(0,1),addEdge(6,9),addEdge(3,8),addEdge(5,11),addEdge(2,12),addEdge(6,10),addEdge(4,8)表示已经修建好的道路把对应的城市连接起来通过Graph对象和顶点9构建DepthFirstSearch对象或BreadthFirstSearch对象调用搜索对象的marked(10)方法和marked(8)方法即可得到9和城市与10号城市以及9号城市与8号城市是否相通。代码:packagegraph;importjava.io.BufferedReader;importjava.io.InputStreamReader;publicclassTraffic_Project_Test2{publicstaticvoidmain(String[]args)throwsException{//构建一个缓冲读取流BufferedReaderBufferedReaderbrnewBufferedReader(newInputStreamReader(Traffic_Project_Test2.class.getClassLoader().getResourceAsStream(traffic_project.txt)));//读取第一行数据20inttotalNumberInteger.parseInt(br.readLine());//构建一个Graph对象GraphGnewGraph(totalNumber);//读取第二行数据7introadNumberInteger.parseInt(br.readLine());//循环读取有限次(7)读取已经修建好的道路for(inti1;iroadNumber;i){Stringroadbr.readLine();//0 1String[]strroad.split( );intvInteger.parseInt(str[0]);intwInteger.parseInt(str[1]);//调用图的addEdge方法把边添加到图中表示已经修建好的道路G.addEdge(v,w);}//构建一个深度优先搜索对象起点设置为顶点9DepthFirstSearchsearchnewDepthFirstSearch(G,9);//调用marked方法判断8顶点和10顶点是否与起点9相通System.out.println(顶点8和顶点9是否相通search.marked(8));System.out.println(顶点10和顶点9是否相通search.marked(10));}}路径查找在实际生活中地图是我们经常使用的一种工具通常我们会用它进行导航输入一个出发城市输入一个目的地城市就可以把路线规划好而在规划好的这个路线上会路过很多中间的城市。这类问题翻译成专业问题就是需求:从s顶点到v顶点是否存在一条路径如果存在请找出这条路径。例如在上图上查找顶点0到顶点4的路径用红色标识出来,那么我们可以把该路径表示为 0-2-3-4。查找API设计思路分析:我们实现路径查找最基本的操作还是得遍历并搜索图所以我们的实现暂且基于深度优先搜索来完成。其搜索的过程是比较简单的。我们添加了edgeTo[]整型数组这个整型数组会记录从每个顶点回到起点s的路径。如果我们把顶点设定为0那么它的搜索可以表示为下图根据最终edgeTo的结果我们很容易能够找到从起点0到任意顶点的路径代码DepthFirstPathsimportjava.util.Stack;publicclassDepthFirstPaths{//索引代表顶点值表示当前顶点是否已经被搜索privateboolean[]marked;//起点privateints;//索引代表顶点值代表从起点s到当前顶点路径上的最后一个顶点privateint[]edgeTo;//构造深度优先搜索对象使用深度优先搜索找出G图中起点为s的所有路径publicDepthFirstPaths(GraphG,ints){//初始化marked数组this.markednewboolean[G.V()];//初始化起点this.ss;//初始化edgeTo数组this.edgeTonewint[G.V()];dfs(G,s);}//使用深度优先搜索找出G图中v顶点的所有相邻顶点privatevoiddfs(GraphG,intv){//把v表示为已搜索marked[v]true;//遍历顶点v的邻接表拿到每一个相邻的顶点继续递归搜索for(Integerw:G.adj(v)){//如果顶点w没有被搜索则继续递归搜索if(!marked[w]){edgeTo[w]v;//到达顶点w的路径上的最后一个顶点是vdfs(G,w);}}}//判断w顶点与s顶点是否存在路径publicbooleanhasPathTo(intv){returnmarked[v];}//找出从起点s到顶点v的路径(就是该路径经过的顶点)publicStackIntegerpathTo(intv){if(!hasPathTo(v)){returnnull;}//创建栈对象保存路径中的所有顶点StackIntegerpathnewStack();//通过循环从顶点v开始一直往前找到找到起点为止for(intxv;x!s;xedgeTo[x]){path.push(x);}//把起点s放到栈中path.push(s);returnpath;}}测试代码packagegraph;importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.util.Stack;publicclassDepthFirstPathsTest{publicstaticvoidmain(String[]args)throwsException{//构建缓冲读取流BufferedReaderBufferedReaderbrnewBufferedReader(newInputStreamReader(DepthFirstPathsTest.class.getClassLoader().getResourceAsStream(main/resources/road_find.txt)));//读取第一行数据6inttotalInteger.parseInt(br.readLine());//根据第一行数据构建一副图GraphGraphGnewGraph(total);//读取第二行数据8intedgeNumbersInteger.parseInt(br.readLine());//继续通过循环读取每一条边关联的两个顶点调用addEdge方法添加边for(inti1;iedgeNumbers;i){Stringedgebr.readLine();//0 1String[]stredge.split( );intvInteger.parseInt(str[0]);intwInteger.parseInt(str[1]);G.addEdge(v,w);}//构建路径查找对象并设置起点为0graph.DepthFirstPathspathsnewgraph.DepthFirstPaths(G,0);//调用 pathTo(4)找到从起点0到终点4的路径返回StackStackIntegerpathpaths.pathTo(4);StringBuildersbnewStringBuilder();//遍历栈对象for(Integerv:path){sb.append(v-);}sb.deleteCharAt(sb.length()-1);System.out.println(sb);}}