数据基础教程15

从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图遍历。如果给定图是连通的无向图或者是强连通的有向图，则遍历一次就能完成，并可按访问的先后顺序得到由该图所有顶点组成的一个序列。8.3.1图遍历的概念8.3图的遍历1/84为了避免同一个顶点被重复访问，必须记住访问过的顶点。为此，可设置一个访问标志数组visited，初始时所有元素置为0，当顶点i访问过时，该数组元素visited[i]置为1。根据遍历方式的不同，图的遍历方法有两种：一种是深度优先遍历（DFS）方法；另一种是广度优先遍历（BFS）方法。012345DFS:014253BFS:0123452/84从图中某个起始点v出发进行深度优先搜索—DFS(v)，首先访问初始顶点v。然后选择一个与顶点v邻接且没被访问过的顶点w为初始顶点，再从w出发进行深度优先搜索—DFS(w)，直到图中与当前顶点v邻接的所有顶点都被访问过为止。8.3.2深度优先遍历递归过程3/84

图采用邻接表为存储结构，其深度优先遍历算法如下（其中，v是起始点编号，visited是类成员数组）：publicstaticvoidDFS(AdjGraphClassG,intv){intw;ArcNodep;System.out.print(v+""); //访问顶点vvisited[v]=1; //置已访问标记p=G.adjlist[v].firstarc; //p指向顶点v的第一个邻接点while(p!=null){w=p.adjvex;if(visited[w]==0)

DFS(G,w); //若w顶点未访问,递归访问它p=p.nextarc; //p置为下一个邻接点}}时间复杂度为O(n+e)。4/84

图采用邻接矩阵为存储结构，其深度优先遍历算法如下（其中，v是起始点编号，visited是类成员数组）：publicstaticvoidDFS(MatGraphClassg,intv){System.out.print(v+""); //访问顶点vvisited[v]=1; //置已访问标记for(intw=0;w<g.n;w++){if(g.edges[v][w]!=0&&g.edges[v][w]!=g.INF){if(visited[w]==0) //存在边<v,w>并且w没有访问过

DFS(g,w);

//若w顶点未访问,递归访问它}}}时间复杂度为O(n2)。5/841402351402350v011v15∧2v233v4∧2∧45∧5v5∧4v3∧3DFS:0152346/841402350v011v15∧2v233v4∧2∧45∧5v5∧4v3∧3理解深度优先遍历过程1302457/8400→10→1→50→20

→2→50→2→30→2→40→2→4

→3起始点0到图中其他顶点的路径长度：DFS:015234类似树的先根遍历。说明1302458/84首先访问起始点v。接着访问顶点v的所有未被访问过的邻接点v1、v2、…、vt。然后再按照v1、v2、…、vt的次序，访问每一个顶点的所有未被访问过的邻接点。依次类推，直到图中所有和初始点v有路径相通的顶点或者图中所有已访问顶点的邻接点都被访问过为止。8.3.3广度优先遍历相邻顶点：先访问先处理队列9/84图采用邻接表为存储结构，其广度优先遍历算法如下：publicstaticvoidBFS(AdjGraphClassG,intv){}ArcNodep;intw;

Queue<Integer>qu=newLinkedList<Integer>();

//定义一个队列System.out.print(v+""); //访问顶点vvisited[v]=1; //置已访问标记qu.offer(v); //v进队while(!qu.isEmpty()){ //队列不空循环v=qu.poll(); //出队顶点vp=G.adjlist[v].firstarc; //找顶点v的第一个邻接点while(p!=null){w=p.adjvex;if(visited[w]==0){ //若v的邻接点w未访问System.out.print(w+""); //访问顶点wvisited[w]=1; //置已访问标记qu.offer(w); //w进队}p=p.nextarc; //找下一个邻接顶点}}}时间复杂度为O(n+e)。10/84图采用邻接矩阵为存储结构，其广度优先遍历算法如下：publicstaticvoidBFS(MatGraphClassg,intv){

Queue<Integer>qu=newLinkedList<Integer>();

//定义一个队列System.out.print(v+""); //访问顶点vvisited[v]=1; //置已访问标记qu.offer(v); //v进队while(!qu.isEmpty()){ //队列不空循环v=qu.poll(); //出队顶点vfor(intw=0;w<g.n;w++){if(g.edges[v][w]!=0&&g.edges[v][w]!=g.INF){if(visited[w]==0) //存在边<v,w>并且w未访问System.out.print(w+""); //访问顶点wvisited[w]=1; //置已访问标记qu.offer(w); //w进队}}}}}时间复杂度为O(n2)。11/84140235（b）图G4的邻接表0v011v15∧2v233v4∧（a）一个有向图G42∧45∧5v5∧4v3∧3BFS:01253414023512/841402350v011v15∧2v233v4∧2∧45∧5v5∧4v3∧3理解广度优先遍历过程13024513/8400→10→20→1→50

→2→50→2→30→2→40→2→4

→3起始点0到图中其他顶点的路径长度：BFS:012534类似树的层次遍历。说明13024514/848.3.4非连通图的遍历连通图：一次遍历能够访问到图中的所有顶点。非连通图：一次遍历只能访问到起始点所在连通分量中的所有顶点，其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择起始点，分别进行遍历，才能够访问到图中的所有顶点。无向图135246015/84有向图，若从起始点到图中的其他每个顶点都有路径，则能够访问到图中的所有顶点。否则不能访问到所有顶点，为此同样需要再选起始点，继续进行遍历，直到图中的所有顶点都被访问过为止。有向图13024516/84publicstaticvoidDFSA(AdjGraphClassG){ //非连通图的DFSArrays.fill(visited,0); //visited数组元素均置为0for(inti=0;i<G.n;i++)if(visited[i]==0)DFS(G,i);

//从顶点i出发深度优先遍历}非连通图采用邻接表存储结构，其深度优先遍历算法如下：17/84publicstaticvoidBFSA(AdjGraphClassG){ //非连通图的BFSArrays.fill(visited,0); //visited数组元素均置为0for(inti=0;i<G.n;i++)if(visited[i]==0)BFS(G,i);

//从顶点i出发广度优先遍历}非连通图采用邻接表存储结构，其广度优先遍历算法如下：18/84

【例8.5】假设图采用邻接表存储，设计一个算法，判断一个无向图是否连通。若连通则返回true；否则返回false。publicstaticvoidDFS1(AdjGraphClassG,intv){//图G从v出发的深度优先遍历intw;ArcNodep;visited[v]=1; //置已访问标记p=G.adjlist[v].firstarc; //p指向顶点v的第一个邻接点while(p!=null){w=p.adjvex;if(visited[w]==0)

DFS1(G,w); //若w顶点未访问,递归访问它p=p.nextarc; //p置为下一个邻接点}}19/84publicstaticbooleanConnect(AdjGraphClassG){//判断无向图G的连通性booleanflag=true;Arrays.fill(visited,0); //visited数组元素均置为0

DFS1(G,0);

//调用DSF1算法,从0出发深度优先遍历for(inti=0;i<G.n;i++){if(visited[i]==0){flag=false; //存在没有访问的顶点，则不连通break;}}returnflag;}20/848.3.5图遍历算法的应用1.深度优先遍历算法的应用140235DFS(0)→

DFS(1)→

DFS(5)DFS(2)→DFS(3)DFS(4)再原路回退21/84

【例8.6】假设图G采用邻接表存储，设计一个算法判断顶点u到顶点v之间是否有路径。并对于以下有向图，判断从顶点0到顶点5、从顶点0到顶点2是否有路径。12340522/84f(G,u,v)置visited[u]=1f(G,u1,v)⁞f(G,un,v)置visited[u1]=1若un=v，返回true思路23/84importjava.util.*;publicclassExam8_6{staticfinalintMAXV=100; //表示最多顶点个数staticint[]visited=newint[MAXV]; //全局变量数组publicstaticbooleanHasPath(AdjGraphClassG,intu,intv){

//判断u到v是否有简单路径Arrays.fill(visited,0); //初始化returnHasPath1(G,u,v);}24/84privatestaticbooleanHasPath1(AdjGraphClassG,intu,intv){ArcNodep;intw;visited[u]=1;p=G.adjlist[u].firstarc; //p指向u的第一个相邻点while(p!=null){w=p.adjvex; //w是u的邻接点if(w==v)returntrue; //找到目标顶点后返回if(visited[w]==0)if(HasPath1(G,w,v))returntrue; p=p.nextarc; //p指向下一个相邻点}returnfalse;}uwvHasPath1(G,u,v)HasPath1(G,w,v)<u,w>25/84publicstaticvoidmain(String[]args){AdjGraphClassG=newAdjGraphClass();intn=6,e=9;int[][]a={{0,1,0,1,0,0},{0,0,0,0,0,1},{0,1,0,0,0,1}, {0,1,0,0,1,0},{0,1,0,0,0,1},{0,0,0,0,0,0}};G.CreateAdjGraph(a,n,e); //创建图的邻接表System.out.println("图G"); G.DispAdjGraph();intu=0,v=5;System.out.println("求解结果");System.out.printf("顶点%d到顶点%d路径情况:%s\n",u,v,(HasPath(G,u,v)?"有":"没有"));u=0;v=2;System.out.printf("顶点%d到顶点%d路径情况:%s\n",u,v,(HasPath(G,u,v)?"有":"没有"));}}26/84图G[0]->(1,1)->(3,1)->∧[1]->(5,1)->∧[2]->(1,1)->(5,1)->∧[3]->(1,1)->(4,1)->∧[4]->(1,1)->(5,1)->∧[5]->∧求解结果

顶点0到顶点5路径情况:有

顶点0到顶点2路径情况:没有12340527/84

【例8.7】假设图G采用邻接表存储，设计一个算法求顶点u到顶点v之间的一条简单路径（假设两顶点之间存在一条或多条简单路径）。并对于以下有向图，求从顶点0到顶点5的一条简单路径。12340528/84思路f(G,u,v,path,d)置visited[u]=1,将u添加的pathf(G,u1,v,path,d)⁞f(G,un,v,path,d)若un=v，path即为所求置visited[u1]=1,将u1添加的pathpath[0..d]存放一条路径29/84publicstaticvoidFindaPath1(AdjGraphClassG,intu,intv){int[]path=newint[MAXV];intd=-1;Arrays.fill(visited,0); //visited数组元素置初值0

FindaPath11(G,u,v,path,d);}30/84privatestaticvoidFindaPath11(AdjGraphClassG,intu,intv,int[]path,intd){ArcNodep;visited[u]=1;

d++;path[d]=u;

//顶点u加入到路径中if(u==v){ //找到一条路径后输出并返回for(inti=0;i<=d;i++)System.out.print(path[i]+"");System.out.println();return;}p=G.adjlist[u].firstarc; //p指向u的第一个邻接点while(p!=null){intw=p.adjvex; //w为邻接点if(visited[w]==0) //w没有访问过

FindaPath11(G,w,v,path,d);

//递归调用p=p.nextarc; //p指向下一个邻接点}}31/84顶点0到顶点5路径：01512340532/84?path和visited有什么不同？DFS(0)visited={0}path={0}u=0，v=5123405图改为：假设邻接表中边单链表按顶点编号递增排列DFS(1)DFS(2)DFS(5)visited={0,1,2}path={0,1,2}visited={0,1}path={0,1}语法：path[0..d]是方法的形参，visited是类变量，相当于全局变量visited={0,1,2}path={0,1}visited={0,1,2,5}path={0,1,5}结果路径：0→1→5visited保存搜索轨迹33/84Java中所有数组都是引用，应该与ArrayList相同啊实际上是将path[0..d]看成方法形参，由d控制path的内容，而d是基本数据类型，属于非引用变量！34/84那么能不能用ArrayList对象path存放路径呢？答案是完全可行的！publicstaticvoidFindaPath2(AdjGraphClassG,intu,intv){

//求u到v的一条简单路径ArrayList<Integer>path=newArrayList<Integer>();

FindaPath21(G,u,v,path);}35/84privatestaticvoidFindaPath21(AdjGraphClassG,intu,intv,

ArrayList<Integer>path){ArcNodep;visited[u]=1;path.add(u); //顶点u加入到路径中if(u==v){ //找到一条路径后输出并返回System.out.println(path);return;}p=G.adjlist[u].firstarc; //p指向u的第一个邻接点while(p!=null){intw=p.adjvex; //w为邻接点if(visited[w]==0) //w没有访问过

FindaPath21(G,w,v,path); //递归调用p=p.nextarc; //p指向下一个邻接点}}36/84顶点0到顶点4路径：01534123405由于ArrayListpath是引用类型，与类变量visited相同搜索轨迹！37/84如何让ArrayListpath保存的是路径

手工回退！privatestaticvoidFindaPath31(AdjGraphClassG,intu,intv, ArrayList<Integer>path){ArcNodep;visited[u]=1;path.add(u); //顶点u加入到路径中if(u==v){ //找到一条路径后输出并返回System.out.println(path);return;}p=G.adjlist[u].firstarc; //p指向u的第一个邻接点while(p!=null){intw=p.adjvex; //w为邻接点if(visited[w]==0) //w没有访问过

FindaPath31(G,w,v,path);

//递归调用p=p.nextarc; //p指向下一个邻接点}

path.remove(path.size()-1);

//增加的具有回退功能的代码}38/84

【例8.8】假设图G采用邻接表存储，设计一个算法求顶点u到顶点v之间的所有简单路径（假设两顶点之间存在一条或多条简单路径）。并对于以下有向图，求从顶点0到顶点5的所有简单路径。12340539/84用path[0..d]存放一条路径，每次找到终点就输出，这样得到所有的路径采用带回溯的深度优先遍历方法思路让path具有自动回退功能

采用path[0..d]实现让visited也具有自动回退功能

采用手工回退实现这样path和visited始终相同，仅仅采用visited即可！40/840visited={0}123405假设邻接表中边单链表按顶点编号递增排列u=0，v=51visited={0,1}5visited={0,1,5}5visited={0,3,4,1,5}3visited={0,3}5visited={0,3,1,5}1visited={0,3,1}4visited={0,3,4}visited={0,3,4,1}15visited={0,3,4,5}41/84publicstaticvoidFindallPath(AdjGraphClassG,intu,intv){Arrays.fill(visited,0); //visited数组元素置初值0FindallPath1(G,u,v);}42/84privatestaticvoidFindallPath1(AdjGraphClassG,intu,intv){ArcNodep;visited[u]=1;if(u==v){ //找到一条路径后输出for(inti=0;i<G.n;i++)if(visited[i]==1)System.out.print(i+"");System.out.println();}p=G.adjlist[u].firstarc; //p指向u的第一个邻接点while(p!=null){intw=p.adjvex; //w为邻接点if(visited[w]==0) //w没有访问过

FindallPath1(G,w,v);

//递归调用p=p.nextarc; //p指向下一个邻接点}

visited[u]=0;

//回溯,重置visited[u]为0}43/84privatestaticvoidFindallPath1(AdjGraphClassG,intu,intv){ArcNodep;visited[u]=1;if(u==v){ //找到一条路径后输出for(inti=0;i<G.n;i++)if(visited[i]==1)System.out.print(i+"");System.out.println();visited[u]=0;return;}p=G.adjlist[u].firstarc; //p指向u的第一个邻接点while(p!=null){intw=p.adjvex; //w为邻接点if(visited[w]==0) //w没有访问过

FindallPath1(G,w,v);

//递归调用p=p.nextarc; //p指向下一个邻接点}

visited[u]=0;

//回溯,重置visited[u]为0}更高效的算法（找到v后不再继续搜索下去）：44/84

实际上上述算法中输出的是visited值为1的顶点，如果希望输出是u到v的真正路径，还是需要增加path。publicstaticvoidFindallPath(AdjGraphClassG,intu,intv){//求u到v的所有简单路径int[]path=newint[MAXV];intd=-1; //path[0..d]存放一条路径Arrays.fill(visited,0); //visited数组元素置初值0FindallPath1(G,u,v,path,d);}45/84privatestaticvoidFindallPath1(AdjGraphClassG,intu,intv, int[]path,intd){ArcNodep;visited[u]=1;d++;path[d]=u; //顶点u加入到路径中if(u==v){ //找到一条路径后输出for(inti=0;i<=d;i++)System.out.print(path[i]+"");System.out.println(); //输出一条路径后不返回visited[u]=0;

return;}p=G.adjlist[u].firstarc; //p指向u的第一个邻接点while(p!=null){intw=p.adjvex; //w为邻接点if(visited[w]==0) //w没有访问过

FindallPath1(G,w,v,path,d);

//递归调用p=p.nextarc; //p指向下一个邻接点}

visited[u]=0;

//回溯,重置visited[u]为0}46/84

【例8.9】假设图G采用邻接表存储，设计一个算法，求图G中从顶点u到v的长度为l的所有简单路径（假设两顶点之间存在一条或多条简单路径）。

和上例相似，采用带回溯的深度优先遍历，只是增加一个找到一条简单路径的条件判断（路径长度是否为l）即可。思路47/84

【例8.10】假设无向图G采用邻接表存储，设计一个算法，判断图中是否包含任何简单回路。

注意若一个无向图只有两个顶点一条连接它们的边，不能认为存在回路，也就是说尽管无向图中边是对称的，单条边不能看成一个回路，回路的长度应大于1（至少包含两条边）。01没有回路48/84解法1：采用深度优先遍历方法判断无向图G中是否存在经过顶点v的回路。从图中顶点v出发遍历，对每个访问的顶点做标记（设置其visited元素为1），并用d表示对应路径的长度。当从顶点v出发访问到顶点u时，若有（u，w）且visited[w]=0，继续遍历下去。若visited[w]=1并且w=v，当d>1时表示从顶点v出发又回到顶点v，而且路径长度大于1，则说明存在一条经过顶点v的回路。v…u路径长度为du的邻接点w=vv…ud>1visited[v]=1visited[u]=1路径长度为d找到的回路一定包含起始搜索的顶点v。49/84如果从图中所有顶点出发遍历都没有返回true，说明没有经过顶点v的回路，则返回false。一旦从图中某个顶点出发遍历返回true就结束，表示存在回路。50/84privatestaticbooleanCycle11(AdjGraphClassG,intu,intv,intd){//经过顶点v的回路判断算法ArcNodep;visited[u]=1; //置已访问标记d++; //路径长度增加1p=G.adjlist[u].firstarc; //p指向顶点u的第一个邻接点while(p!=null){intw=p.adjvex;if(visited[w]==0){ //若顶点w未访问,递归调用if(Cycle11(G,w,v,d)) //从顶点w出发找到回路后返回truereturntrue;}elseif(w==v&&d>1) //搜索到顶点v并且环长度大于1returntrue;p=p.nextarc; //找下一个邻接点}returnfalse;}51/84publicstaticbooleanCycle1(AdjGraphClassG){//解法1：判断无向图G中是否有回路for(inti=0;i<G.n;i++){Arrays.fill(visited,0); //visited初始化if(Cycle11(G,i,i,-1)) //从顶点v出发搜索成功返回truereturntrue;}returnfalse;}52/84

解法2：在深度优先遍历时，visited记录的是搜索轨迹。当访问到顶点u时，如果找到顶点u的邻接点w：v…u…w路径长度至少为1回路？若w已经访问过，由于是无向图，说明从w到u一定有路径。而此时u到w有边，说明找到一个回路。53/84但需要排除将(w，u)一条边作为回路的情况。v…u…w路径长度至少为1回路？01没有回路54/84找到的回路不一定包含起始搜索的顶点v。v…uw≠pre…w路径长度至少为1pre回路！

为此增加一个pre参数，表示顶点u的前驱顶点，只要w≠pre才能够排除这种情况，从而确定找到一个长度大于1的回路。55/84privatestaticvoidCycle21(AdjGraphClassG,intu,intpre){

//从顶点u出发判断是否有回路（用has标识）的算法ArcNodep;visited[u]=1; //置已访问标记if(has)return; //找到回路后直接返回p=G.adjlist[u].firstarc; //p指向顶点u的第一个邻接点while(p!=null){intw=p.adjvex;if(visited[w]==0) //若顶点w未访问,递归调用

Cycle21(G,w,u); //从顶点w出发搜索elseif(w!=pre){ //搜索到已访问的顶点且不是whas=true; //说明有回路return;}p=p.nextarc; //找下一个邻接点}}起始顶点的pre置为-1搜索边<u,w>，u是w的前驱顶点！56/84staticbooleanhas; //是否有回路publicstaticbooleanCycle2(AdjGraphClassG){//判断无向图G中是否有回路for(inti=0;i<G.n;i++){Arrays.fill(visited,0); //visited初始化has=false;

Cycle21(G,i,-1); //从顶点i出发搜索是否有回路，i的前驱为-1if(has) //有回路返回truereturntrue;}returnfalse;}57/84

【例8.11】假设有向图G采用邻接表存储，设计一个算法，判断图中是否包含任何简单回路。注意若一个有向图只有两个顶点a和b，并且存在边<a，b>和<b，a>，则认为存在回路。ab有回路58/84找到的回路一定包含起始搜索的顶点v。解法1：上例中的解法1既适合无向图也适合有向图判断是否有回路。但针有向图需要删除d参数：v…u路径长度为du的邻接点w=vv…uvisited[v]=1visited[u]=1路径长度为d59/84但上例中的解法2仅适合无向图不适合有向图判断是否有回路。012对于无向图：在DFS中，先访问w，后访问u，则w

u一定有路径。v…uw≠pre…w路径长度至少为1pre对于有向图却不一定成立！访问0→访问1访问2有回路？没有：因为顶点1到2没有路径60/84用path保存从v到u的路径。若u的一个邻接点w是path中的一个顶点（w一定是已经访问过的顶点），则构成一个包含顶点u和w的回路。

解法2：对于有向图，可以进一步优化解法1，从顶点v出发深度优先遍历，当访问到顶点u时：w…upath[0..d]v…回路找到的回路不一定包含起始搜索的顶点v。61/84privatestaticbooleaninpath(int[]path,intd,intw){//判断w是否在path[0..d]中for(inti=0;i<=d;i++)if(path[i]==w)

returntrue;returnfalse;}62/84privatestaticbooleanCycle21(AdjGraphClassG,intu,int[]path,intd){//从顶点u出发搜索有向图G中是否存在回路的算法ArcNodep;visited[u]=1; //置已访问标记d++;path[d]=u; //将顶点u添加到路径中p=G.adjlist[u].firstarc; //p指向顶点u的第一个邻接点while(p!=null){intw=p.adjvex;if(visited[w]==0){ //若顶点w未访问if(Cycle21(G,w,path,d)) //从顶点w出发搜索存在回路returntrue;}elseif(inpath(path,d,w)) //顶点w没有访问但在路径中returntrue; //找到回路返回truep=p.nextarc; //找下一个邻接点}returnfalse;}63/84将路径path改为一个栈st。增加一个flag数组标记顶点w是否在栈中。

解法3：解法2中判断一个顶点w算法在路径path中，采用逐一比较方式，效率比较低，可以进一步改进：st与path的功能相同，都是用来记录路径的。但与前面路径path[0..d]不同，st为引用对象，不会自动回退，这里直接采用类成员变量表示，需要增加回退的代码。说明64/84staticStack<Integer>st=newStack<Integer>();//定义一个栈staticint[]flag=newint[MAXV]; //标记顶点是否在栈中publicstaticbooleanCycle3(AdjGraphClassG){//判断有向图G中是否有回路for(inti=0;i<G.n;i++){Arrays.fill(visited,0); //visited初始化if(Cycle31(G,i)) //从顶点v出发搜索returntrue;}returnfalse;}65/84privatestaticbooleanCycle31(AdjGraphClassG,intu){//从顶点u出发搜索是否存在回路的算法ArcNodep;visited[u]=1;st.push(u); //置已访问标记并且进栈flag[u]=1;

//表示顶点u在栈中p=G.adjlist[u].firstarc; //p指向顶点u的第一个邻接点while(p!=null){intw=p.adjvex;if(visited[w]==0){ //若顶点w未访问if(Cycle31(G,w)) //从顶点w出发搜索存在回路returntrue;else{ //从w回退,出栈w,置flag[w]=0st.pop();

flag[w]=0;}}elseif(flag[w]==1) //顶点v已访问且在栈中，返回truereturntrue;p=p.nextarc; //找下一个邻接点}returnfalse;}66/842.广度优先遍历算法的应用1402350：00→1：10→2：10→1→5：20→2→3：20→2→4：2起始点0到图中其他顶点的最短路径长度：14023567/84

【例8.12】假设图G采用邻接表存储，设计一个算法，求不带权图G中从顶点u到顶点v的一条最短路径（假设两顶点之间存在一条或多条简单路径）。并对于以下有向图，求从顶点0到顶点5的一条最短简单路径。12340568/841234050：00→1：10→3：10→1→5：20→3→4：2起始点0到图中其他顶点的最短路径长度：14035510反向：0→1→5parent69/84publicstaticvoidShortPath(AdjGraphClassG,intu,intv){classQNode{ //队列元素类型intno; //顶点编号QNodeparent; //前驱顶点}Queue<QNode>qu=newLinkedList<QNode>();//定义一个队列QNodee,e1;ArcNodep;e=newQNode();e.no=u;e.parent=null; //初始点对应队列元素的前驱为空qu.offer(e); //u进队visited[u]=1; //置已访问标记70/84while(!qu.isEmpty()){ //队列不空循环e=qu.poll(); //出队元素eif(e.no==v){ //找到v时输出路径之逆并退出int[]path=newint[MAXV]; //path[0..d]存放逆路径intd=-1;QNodef=e; //通过前驱关系求逆路径while(f!=null){d++;path[d]=f.no;

f=f.parent;}for(inti=d;i>=0;i--) //反向输出逆路径构成正向路径System.out.print(path[i]+"");System.out.println();return; //输出一条路径后返回}71/84p=G.adjlist[e.no].firstarc; //找e对应顶点的第一个邻接点while(p!=null){intw=p.adjvex;if(visited[w]==0) { //若u的邻接点w未访问e1=newQNode(); //建立队列元素

e1.no=w;e1.parent=e; //其前驱为evisited[w]=1; //置已访问标记qu.offer(e1); //e1进队}p=p.nextarc; //找下一个邻接顶点}}}uee1e1.parent=e72/84?为什么广度优先遍历找到的路径一定是最短路径呢？14035路径上的每个顶点均为不同层次的顶点，所以该路径一定是最短路径。73/848.3.6*求有向图中强连通分量的Tarjan算法Tarjan算法采用深度优先遍历过程求有向图的所有强连通分量，将每一个强连通分量作为搜索树上的一个子树。DFN[u]作为顶点u搜索的次序编号（时间戳），简单来说就是第几个被搜索到的，每个顶点的时间戳都不一样。LOW[u]作为顶点u在这棵树中的最小子树的根（也是指时间戳），每次保证最小的。在深度优先遍历中每次找到一个新顶点u，总是置LOW[u]=DFN[u]。01234DFN:1234574/84若顶点v没有访问过：就从顶点v继续下去。每次返回时根据顶点v的LOW[v]修改LOW[u]

LOW[u]=min(LOW[u],LOW[v])，保证LOW[u]存放最小子树的根。

为了存储整个强连通分量，采用一个栈st，每次新顶点出现就进栈。从顶点u出发搜索，若有出边<u，v>：相当于path，由于每次找当前顶点所在的强连通分量，找到后输出

后进先出…LOW[v]LOW[u]=min(LOW[u],LOW[v])vu75/84若顶点v访问过并且在栈中：因为v是在u之后搜索的顶点（则存在从u到v的路径），如果顶点v能够回溯到的已经在栈中的顶点，则顶点u也一定能够回溯到（v能够到达的顶点u也一定能够到达）。

更新LOW[u]=min(LOW[u]，DFN[v])，uvLOW[u]=min(LOW[u]，DFN[v])看成子树的根或者…回路v在st中01234修改LOW[3]01234修改LOW[2]子树的根76/84若顶点u满