数据结构教程（Java语言描述）（第2版 微课视频版） 课件 第8章 图

第8章图8.1图的基本概念8.2图的存储结构CONTENTS提纲8.3图的遍历8.4生成树和最小生成树8.5最短路径8.6拓扑排序8.7AOE网与关键路径1/40图G（Graph）由两个集合V（Vertex）和E（Edge）组成，记为G=(V，E)。V是顶点的有限集合，记为V(G)。E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E(G)。8.1.1图的定义8.1图的基本概念2/40ADTGraph{

数据对象：

D={ai|0≤i≤n-1，n≥0，ai为int类型}//ai为每个顶点的唯一编号

数据关系：

R={r} r={<ai，aj>|ai，aj∈D，0≤i≤n-1，0≤j≤n-1，其中ai可以有零个

或多个前驱元素，可以有零个或多个后继元素}

基本运算： voidCreateGraph()：根据相关数据建立一个图。 voidDispGraph()：输出一个图。

…}抽象数据类型图的描述说明约定用i（0≤i≤n-1）表示第i个顶点的编号。3/40在图G中，如果代表边的顶点对（或序偶）是无序的，则称G为无向图。无向图中代表边的无序顶点对通常用圆括号括起来，用以表示一条无向边。如(i，j)表示顶点i与顶点j的一条无向边，显然，(i，j)和(j，i)所代表的是同一条边。如果表示边的顶点对（或序偶）是有序的，则称G为有向图。在有向图中代表边的顶点对通常用尖括号括起来，用以表示一条有向边（又称为弧），如<i，j>表示从顶点i到顶点j的一条边。无向图和有向图1302413024（a）一个无向图（b）一个有向图4/40数据结构中的图一般不重复出现一条边，如果允许重复边出现，这样的图称为多重图，如一个无向图中顶点1和2之间出现两条或两条以上的边。本书中讨论的图均指非多重图。10231023（a）多重无向图（b）多重有向图5/40在一个无向图中，若存在一条边(i，j)，则称顶点i和顶点j为该边的两个端点，并称它们互为邻接点，即顶点i是顶点j的一个邻接点，顶点j也是顶点i的一个邻接点。在一个有向图中，若存在一条边<i，j>，则称此边是顶点i的一条出边，同时也是顶点j的一条入边。i和j分别为此边的起始端点（简称为起点）和终止端点（简称终点）。并称顶点j是i的出边邻接点，顶点i是j的入边邻接点。8.1.2图的基本术语6/40在无向图中，顶点所具有的边的数目称为该顶点的度。在有向图中，顶点i的度又分为入度和出度，以顶点i为终点的入边的数目，称为该顶点的入度。以顶点i为起点的出边的数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。若一个图（无论有向图或无向图）中有n个顶点和e条边，每个顶点的度为di（0≤i≤n-1），则有：7/40

【例8.1】一个无向图中有16条边，度为4的顶点有3个，度为3的顶点有4个，其余顶点的度均小于3，则该图至少有多少个顶点？设该图有n个顶点，图中度为i的顶点数为ni（0≤i≤4）。n4=3，n3=4。要使顶点数最少，该图应是连通的，即n0=0。n=n4+n3+n2+n1+n0=7+n2+n1，即n2+n1=n-7。度之和=4×3+3×4+2×n2+n1=24+2n2+n1≤24+2(n2+n1)=24+2×(n-7)=10+2n。而度之和=2e=32，所以有10+2n≥32，即n≥11。即这样的无向图至少有11个顶点。8/40完全无向图中的每两个顶点之间都存在着一条边。含有n个顶点的完全无向图有n(n-1)/2条边。完全有向图中的每两个顶点之间都存在着方向相反的两条边。含有n个顶点的完全有向图包含有n(n-1)条边。10231023（a）一个完全无向图（b）一个完全有向图9/40当一个图接近完全图时，则称为稠密图。当一个图含有较少的边数（即无向图有e<<n(n-1)/2，有向图有e<<n(n-1)）时，则称为稀疏图。10/40设有两个图G=(V，E)和G'=(V'，E')，若V'是V的子集，即V'

V，且E'是E的子集，即E'

E，则称G'是G的子图。子图013201320132不是子图11/40在一个图G=(V，E)中，从顶点i到顶点j的一条路径是一个顶点序列(i，i1，i2，…，im，j)，若此图G是无向图，则边(i，i1)，(i1，i2)，…，(im-1，im)，(im，j)属于E(G)；若此图是有向图，则<i，i1>，<i1，i2>，…，<im-1，im>，<im，j>属于E(G)。路径长度是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。1302413024（0,3,2,1）的简单路径长度为3（0,1,2）的简单路径长度为212/40若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环。开始点与结束点相同的简单路径被称为简单回路或简单环。1302413024（0,1,3,4,0）的简单回路长度为4（0,1,2,4,0）的简单回路长度为413/40在无向图G中，若从顶点i到顶点j有路径，则称顶点i和顶点j是连通的（顶点i和顶点j具有连通关系）。若图G中任意两个顶点都是连通的，则称G为连通图，否则称为非连通图。无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个即本身，而非连通图有多个连通分量。13024两个连通分量构成14/40在有向图G中，若从顶点i到顶点j有路径且从顶点j到顶点i也有路径，则称顶点i和顶点j是强连通的（顶点i和顶点j具有强连通关系）。若图G中的任意两个顶点i和j都是强连通的，则称图G是强连通图。有向图G中的极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量即本身，非强连通图有多个强连通分量。一般地单个顶点自身就是一个强连通分量。143021430215/40说明：顶点之间的连通关系和强连通关系都是等价关系！图中每一条边都可以附有一个对应的数值，这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图，也称作网。103249583616/408.2.1邻接矩阵8.2图的存储结构1.邻接矩阵存储方法

邻接矩阵是表示顶点之间邻接关系的矩阵。设G=(V，E)是含有n（设n>0）个顶点的图，各顶点的编号为0～n-1，则G的邻接矩阵数组A是n阶方阵。17/40（1）如果G是不带权图，则：A[i][j]=1若(i，j)∈E(G)或者<i，j>∈E(G)0其他（2）如果G是带权图，则：A[i][j]=wij

若i≠j并且(i，j)∈E(G)或者<i，j>∈E(G)0若i=j∞

其他

18/4013024（a）一个无向图13024（b）一个有向图1032495836（c）一个带权有向图19/40publicclassMatGraphClass{

//图邻接矩阵类finalintMAXV=100; //表示最多顶点个数finalintINF=0x3f3f3f3f; //表示∞int[][]edges; //邻接矩阵数组，元素为int类型intn,e; //顶点数，边数String[]vexs; //存放顶点信息publicMatGraphClass(){ //构造方法edges=newint[MAXV][MAXV];vexs=newString[MAXV];}

//图的基本运算算法}图的邻接矩阵类MatGraphClass邻接矩阵数组？20/40邻接矩阵的特点图的邻接矩阵表示是唯一的。对于含有n个顶点的图，采用邻接矩阵存储时，无论是有向图还是无向图，也无论边的数目是多少，其存储空间均为O(n2)，所以邻接矩阵适合于存储边数较多的稠密图。…用邻接矩阵方法存储图，确定任意两个顶点之间是否有边相连的时间为O(1)，找一个顶点的所有相邻点的时间为O(n)。21/40（1）创建图的邻接矩阵2.图基本运算在邻接矩阵中的实现邻接矩阵数组a顶点数n边数e邻接矩阵gpublicvoidCreateMatGraph(int[][]a,intn,inte){ this.n=n;this.e=e; //置顶点数和边数for(inti=0;i<n;i++){edges[i]=newint[n];for(intj=0;j<n;j++)edges[i][j]=a[i][j];}}22/40（2）输出图publicvoidDispMatGraph(){ //输出图for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(edges[i][j]==INF)System.out.printf("%4s","∞");elseSystem.out.printf("%5d",edges[i][j]);}System.out.println();}}23/40publicstaticintDegree1(MatGraphClassg,intv){ //无向图邻接矩阵中求顶点v的度intd=0;for(intj=0;j<g.n;j++){ //统计第v行的非0非∞元素个数if(g.edges[v][j]!=0&&g.edges[v][j]!=g.INF)d++;}returnd;}【例8.3】一个含有n个顶点e条边的图采用邻接矩阵g存储，设计以下算法：（1）该图为无向图，求其中顶点v的度。（2）该图为有向图，求该图中顶点v的出度和入度。无向图，求其中顶点v的度24/40publicstaticint[]Degree2(MatGraphClassg,intv){//有向图邻接矩阵中求顶点v的出度和入度int[]ans=newint[2];ans[0]=0; //累计出度for(intj=0;j<g.n;j++){ //统计第v行的非0非∞元素个数为出度if(g.edges[v][j]!=0&&g.edges[v][j]!=g.INF)ans[0]++;}ans[1]=0; //累计入度for(inti=0;i<g.n;i++){ //统计第v列的非0非∞元素个数为入度if(g.edges[i][v]!=0&&g.edges[i][v]!=g.INF)ans[1]++;;}returnans; //返回出度和入度}有向图，求该图中顶点v的出度和入度25/401.邻接表存储方法8.2.2邻接表每个顶点建立一个单链表，第i（0≤i≤n-1）个单链表中的结点表示依附于顶点i的边（有向图是顶点i出边）。每个单链表上附设一个表头结点，将所有表头结点构成一个头结点数组。26/40边结点结构头结点结构adjvexweightnextarcdatafirstarci数组下标i与顶点编号对应！27/4013024（a）一个无向图0v011v102v213v304v40datafirstarcadjvexnextarc34∧23∧34∧23∧124∧1032495836（c）一个带权有向图0v0181v12v23v34v4∧23∧46∧29∧35∧weight28/40图的邻接表存储类AdjGraphClassclassArcNode{

//边结点类intadjvex; //该边的终点编号ArcNodenextarc; //指向下一条边的指针intweight; //该边的相关信息,如边的权值}classVNode{

//头结点类String[]data; //顶点信息

ArcNodefirstarc; //指向第一条边的邻接顶点}publicclassAdjGraphClass{

//图邻接表类finalintMAXV=100; //表示最多顶点个数finalintINF=0x3f3f3f3f; //表示∞VNode[]adjlist; //邻接表头数组intn,e; //图中顶点数n和边数epublicAdjGraphClass(){ //构造方法adjlist=newVNode[MAXV];for(inti=0;i<MAXV;i++)adjlist[i]=newVNode();}//图的基本运算算法}29/40邻接表的特点邻接表表示不唯一。对于有n个顶点和e条边的无向图，其邻接表有n个表头结点和2e个边结点；对于有n个顶点和e条边的有向图，其邻接表有n个表头结点和e个边结点。显然，对于边数目较少的稀疏图，邻接表比邻接矩阵要节省空间。…用邻接表存储图时，确定任意两个顶点之间是否有边相连的时间为O(m)，找一个顶点的所有相邻点的时间也是O(m)（m为最大顶点出度，m<n）。30/40逆邻接表0v0∧1v1082v23v34v4∧1305∧26∧39∧1032495836（c）一个带权有向图扩展

方便查找每个顶点的入边31/402.图基本运算在邻接表中的实现（1）创建图的邻接表邻接矩阵数组a顶点数n边数e邻接表GpublicvoidCreateAdjGraph(int[][]a,intn,inte){this.n=n;this.e=e; //置顶点数和边数ArcNodep;for(inti=0;i<n;i++) //所有头结点的指针置初值adjlist[i].firstarc=null;for(inti=0;i<n;i++){ //检查边数组a中每个元素for(intj=n-1;j>=0;j--){if(a[i][j]!=0&&a[i][j]!=INF){ //存在一条边p=newArcNode(); //创建一个边结点pp.adjvex=j;p.weight=a[i][j];p.nextarc=adjlist[i].firstarc;//采用头插法插入padjlist[i].firstarc=p;}}}}jpi32/40（2）输出图publicvoidDispAdjGraph(){ //输出图的邻接表ArcNodep;for(inti=0;i<n;i++){System.out.printf("[%d]",i);p=adjlist[i].firstarc; //p指向第一个邻接点while(p!=null){System.out.printf("->(%d,%d)",p.adjvex,p.weight);p=p.nextarc; //p移向下一个邻接点}System.out.println("->∧");}}33/40【例8.4】一个含有n个顶点e条边的图采用邻接表存储，设计以下算法：（1）该图为无向图，求其中顶点v的度。（2）该图为有向图，求该图中顶点v的出度和入度。publicstaticintDegree1(AdjGraphClassG,intv){intd=0;ArcNodep;p=G.adjlist[v].firstarc;while(p!=null){d++;p=p.nextarc;}returnd;}无向图，求其中顶点v的度34/40publicstaticint[]Degree2(AdjGraphClassG,intv){int[]ans=newint[2];ArcNodep;ans[0]=0; //累计出度p=G.adjlist[v].firstarc;while(p!=null){ //统计第v个单链表中的边结点个数ans[0]++;p=p.nextarc;}ans[1]=0; //累计入度for(inti=0;i<G.n;i++){ //遍历所有的头结点p=G.adjlist[i].firstarc; //遍历第i个单链表while(p!=null){if(p.adjvex==v){ans[1]++;break; //至多只有一个这样的边结点}elsep=p.nextarc;}}returnans; //返回出度和入度}有向图，求该图中顶点v的出度和入度35/403.简化的邻接表011223344-1head数组18-1v0350123-1246-1329-14wnextedge数组1032495836（c）一个带权有向图36/40classENode{

//边结点类

intv; //邻接点intw; //边权值intnext; //下一条边publicENode(intv,intw){ //构造方法this.v=v;this.w=w;}}37/40publicclassAdjGraphClass1{

//图简化邻接表类finalintMAXV=100; //表示最多顶点个数finalintMAXE=300; //表示最多边数finalintINF=0x3f3f3f3f; //表示∞int[]head; //邻接表头结点数组ENode[]edge; //边结点数组intn,e; //图中顶点数n和边数einttoll; //边数组下标publicAdjGraphClass1(){ //构造方法head=newint[MAXV]; //创建头结点数组Arrays.fill(head,-1); //head所有元素初始化为-1edge=newENode[MAXE]; //创建边结点数组

toll=0;

//edge数组下标从0开始}38/40publicvoidaddEdge(intu,intv,intw){ //图中增加边<u,v,w>edge[toll]=newENode(v,w);edge[toll].next=head[u];head[u]=toll++;}publicvoidCreateAdjGraph(int[][]a){//通过边数组a建立图简化邻接表n=a.length;e=0; //初始化顶点数和边数for(inti=0;i<n;i++){ //检查边数组a中每个元素for(intj=1;j<n;j++){if(a[i][j]!=0&&a[i][j]!=INF){ //存在一条边addEdge(i,j,a[i][j]);e++; //边数增1}}}}39/40publicvoidDispAdjGraph() //输出图的邻接表{for(inti=0;i<n;i++){System.out.printf("[%d]",i);for(inte=head[i];e!=-1;e=edge[e].next)System.out.printf("->(%d,%d)",edge[e].v,edge[e].w);System.out.println("->∧");}}}40/40从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图遍历。如果给定图是连通的无向图或者是强连通的有向图，则遍历一次就能完成，并可按访问的先后顺序得到由该图所有顶点组成的一个序列。8.3.1图遍历的概念8.3图的遍历41/84为了避免同一个顶点被重复访问，必须记住访问过的顶点。为此，可设置一个访问标志数组visited，初始时所有元素置为0，当顶点i访问过时，该数组元素visited[i]置为1。根据遍历方式的不同，图的遍历方法有两种：一种是深度优先遍历（DFS）方法；另一种是广度优先遍历（BFS）方法。012345DFS:014253BFS:01234542/84从图中某个起始点v出发进行深度优先搜索—DFS(v)，首先访问初始顶点v。然后选择一个与顶点v邻接且没被访问过的顶点w为初始顶点，再从w出发进行深度优先搜索—DFS(w)，直到图中与当前顶点v邻接的所有顶点都被访问过为止。8.3.2深度优先遍历递归过程43/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)。44/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)。45/841402351402350v011v15∧2v233v4∧2∧45∧5v5∧4v3∧3DFS:01523446/841402350v011v15∧2v233v4∧2∧45∧5v5∧4v3∧3理解深度优先遍历过程13024547/8400→10→1→50→20

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

→3起始点0到图中其他顶点的路径长度：DFS:015234类似树的先根遍历。说明13024548/84首先访问起始点v。接着访问顶点v的所有未被访问过的邻接点v1、v2、…、vt。然后再按照v1、v2、…、vt的次序，访问每一个顶点的所有未被访问过的邻接点。依次类推，直到图中所有和初始点v有路径相通的顶点或者图中所有已访问顶点的邻接点都被访问过为止。8.3.3广度优先遍历相邻顶点：先访问先处理队列49/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)。50/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)。51/84140235（b）图G4的邻接表0v011v15∧2v233v4∧（a）一个有向图G42∧45∧5v5∧4v3∧3BFS:01253414023552/841402350v011v15∧2v233v4∧2∧45∧5v5∧4v3∧3理解广度优先遍历过程13024553/8400→10→20→1→50

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

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

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

//从顶点i出发广度优先遍历}非连通图采用邻接表存储结构，其广度优先遍历算法如下：58/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置为下一个邻接点}}59/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;}60/848.3.5图遍历算法的应用1.深度优先遍历算法的应用140235DFS(0)→

DFS(1)→

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

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

//判断u到v是否有简单路径Arrays.fill(visited,0); //初始化returnHasPath1(G,u,v);}64/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>65/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)?"有":"没有"));}}66/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路径情况:没有12340567/84

【例8.7】假设图G采用邻接表存储，设计一个算法求顶点u到顶点v之间的一条简单路径（假设两顶点之间存在一条或多条简单路径）。并对于以下有向图，求从顶点0到顶点5的一条简单路径。12340568/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]存放一条路径69/84publicstaticvoidFindaPath1(AdjGraphClassG,intu,intv){int[]path=newint[MAXV];intd=-1;Arrays.fill(visited,0); //visited数组元素置初值0

FindaPath11(G,u,v,path,d);}70/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指向下一个邻接点}}71/84顶点0到顶点5路径：01512340572/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保存搜索轨迹73/84Java中所有数组都是引用，应该与ArrayList相同啊实际上是将path[0..d]看成方法形参，由d控制path的内容，而d是基本数据类型，属于非引用变量！74/84那么能不能用ArrayList对象path存放路径呢？答案是完全可行的！publicstaticvoidFindaPath2(AdjGraphClassG,intu,intv){

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

FindaPath21(G,u,v,path);}75/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指向下一个邻接点}}76/84顶点0到顶点4路径：01534123405由于ArrayListpath是引用类型，与类变量visited相同搜索轨迹！77/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);

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

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

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

采用手工回退实现这样path和visited始终相同，仅仅采用visited即可！80/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}81/84publicstaticvoidFindallPath(AdjGraphClassG,intu,intv){Arrays.fill(visited,0); //visited数组元素置初值0FindallPath1(G,u,v);}82/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}83/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后不再继续搜索下去）：84/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);}85/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}86/84

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

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

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

注意若一个无向图只有两个顶点一条连接它们的边，不能认为存在回路，也就是说尽管无向图中边是对称的，单条边不能看成一个回路，回路的长度应大于1（至少包含两条边）。01没有回路88/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。89/84如果从图中所有顶点出发遍历都没有返回true，说明没有经过顶点v的回路，则返回false。一旦从图中某个顶点出发遍历返回true就结束，表示存在回路。90/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;}91/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;}92/84

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

为此增加一个pre参数，表示顶点u的前驱顶点，只要w≠pre才能够排除这种情况，从而确定找到一个长度大于1的回路。95/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的前驱顶点！96/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;}97/84

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

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

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

returntrue;returnfalse;}102/84privatestaticbooleanCycle21(AdjGraphClassG,intu,int[]path,intd){//从顶点u出发搜索有向图G中是