《第七章--图PPT课件》由会员分享，可在线阅读，更多相关《第七章--图PPT课件（100页珍藏版）》请在金锄头文库上搜索。
1、第七章 图2021/7/231v 图图G由两个集合由两个集合V和和E组成，记为组成，记为G=(V,E),其中其中V为顶点为顶点的的有穷非空集有穷非空集合，合，E为为V中中顶点偶对顶点偶对(即边即边)的集合。图的集合。图G的的顶点集和边集分别顶点集和边集分别记为记为V(G)和和E(G)。E(G)可以是空集，可以是空集，若若E(G)为空，则为空，则图图G只有顶点而没有边。只有顶点而没有边。7.1 7.1 图的概念图的概念2021/7/232一条边是由两个顶点组成的有一条边是由两个顶点组成的有序对，记为序对，记为 。一般地。一般地表示一条有向边，表示一条有向边，vi为为边的起点，边的起点，vj为边的
2、终点。有为边的终点。有向边又称为向边又称为弧弧，vi为为弧尾弧尾，vj为为弧头弧头.V(G)=v1,v2,v3,v4,v5E(G )=,7.1v 有向图有向图: :图图G G中的每一条边都是有方向的中的每一条边都是有方向的。v2v3v4v5v12021/7/233v无向图无向图: 图中的每一条边都是无方向的。图中的每一条边都是无方向的。一条边为两个顶点的无序对一条边为两个顶点的无序对,记为记为(v1,v4)。一般地。一般地(vi,vj)表表示一条无向边，并且示一条无向边，并且(vi,vj)和和(vj,vi)表示同一条边表示同一条边V(G)=v1,v2,v3,v4,v5E(G)= (v1,v2)
3、,(v1,v3),(v1,v4),(v2,v3),(v2,v5),(v4,v5)7.1v2v3v4v5v12021/7/2347.1v若若 (vi,vj) 是是一条无向边，则称顶点一条无向边，则称顶点 vi 和和 vj 互为互为邻接点邻接点(Adjacent)，(vi,vj) 与顶点与顶点 vi 和和 vj 相关联相关联(Incident)。v若若 是一条有向边，则称顶点是一条有向边，则称顶点 vi 邻接到邻接到 vj，顶点，顶点 vj 邻邻接于接于vi， 与顶点与顶点 vi 和和 vj 相关联。相关联。v无向完全图无向完全图任何两个顶点之间都有边的无向图。共有任何两个顶点之间都有边的无向图。
4、共有 n(n-1)/2 条边。条边。v有向完全图有向完全图任何两个顶点之对间都有弧的有向图。共有任何两个顶点之对间都有弧的有向图。共有n(n-1)条边。条边。无向完全图无向完全图有向完全图有向完全图2021/7/2357.1度、入度和出度的概念：度、入度和出度的概念： 无向图中无向图中顶点顶点v的度的度为关联于该顶点的边的数目，记为为关联于该顶点的边的数目，记为D(v)有向图中把以顶点有向图中把以顶点v为终点的边的数目称为为终点的边的数目称为v的的入度入度，记为，记为ID(v) 把以顶点把以顶点v为始点的边的数目称为为始点的边的数目称为v的的出度出度,记为记为OD(v) 顶点的度顶点的度定义为
5、入度与出度之和，即定义为入度与出度之和，即D(v)=ID(v)+OD(v)v2v3v4v5v1 e = D(Vi)/2ni=1D(v1)=D(v2)=3D(v3)=2 D(v4)=D(v5)=3ID(v2)=1,OD(v2)=2D(v2)=ID(V2)+OD(V2)=3v2v3v4v5v1无论有向图还是无向图，顶点数无论有向图还是无向图，顶点数 n 边数边数 e 和度之间的关系满足：和度之间的关系满足：D(v1)=D(v2)=3D(v3)=D(v4)=D(v5)= 22021/7/236v子图的概念子图的概念:设设G=(V,E)是一个图，若是一个图，若V是是V的子集，的子集，E是是E的子集且的
6、子集且E中的边所关联的顶点均在中的边所关联的顶点均在V中中，则则G=(V,E)也是一个图，并称其为也是一个图，并称其为G的的子图子图。若若V=v1,v2 , E=(v1,v3) ,G=(V,E)不是图不是图 , 也不可能是子图。也不可能是子图。7.1v2v3v4v5v12021/7/237路径路径：若存在一个顶点序列若存在一个顶点序列vp,vi1,vi2,vin,vq:无向图无向图G中中,使得使得(vp,vi1),(vi1,vi2),(vin,vq) 均属于均属于E(G),则则称顶点称顶点vp到到vq存在一条路径。存在一条路径。有向图有向图G中中,若若,均属于均属于E(G),则则从顶点从顶点v
7、p到到vq存在一条路径。存在一条路径。 7.1路径长度路径长度：路径长度为该路径上边的数目。：路径长度为该路径上边的数目。 v2v3v4v5v1该有向图中顶点该有向图中顶点v2到顶点到顶点v3、 v4和和v5存在路径，存在路径，到到v1不存在路径不存在路径2021/7/238例例1 从从V1 V5路径路径 V1 V2 V3 V4 V2 V5不是简单路径不是简单路径路径路径 V1 V2 V5是简单路径是简单路径V1 V2 V3 V4 V2 V5 V1是个回路，但不是个回路，但不是简单回路是简单回路而而V1 V2 V5 V1 是简单回路是简单回路7.1简单路径简单路径：除起点和终点外，其余顶点均不
8、相同的路径称：除起点和终点外，其余顶点均不相同的路径称为为简单路径简单路径。起点和终点相同的简单路径称为。起点和终点相同的简单路径称为简单回路简单回路。V1V2V3V4V52021/7/239有向图的根有向图的根有向图中，若存在一个顶点有向图中，若存在一个顶点v，从该顶点到图中其它各顶点，从该顶点到图中其它各顶点都存在路径，则称该有向图为都存在路径，则称该有向图为有根图有根图，v称为图的称为图的根根。V1为根为根7.1v2v3v4v5v12021/7/2310v有向图有向图G G中，任意两个不同的顶点中，任意两个不同的顶点vivi和和vjvj, ,都存在从都存在从vivi到到 vjvj以及以及
9、vjvj到到vivi的的 路径，则称路径，则称G G为为强连通图强连通图。v有向图有向图G G的极大强连通子图称为的极大强连通子图称为G G的的强连通分量强连通分量。7.1v无向图无向图G G中，若任意两个顶点间存在路径中，若任意两个顶点间存在路径( (即连通的即连通的),),则称则称G G为为连通图连通图。v无向图无向图G G的极大连通子图称为的极大连通子图称为G G的的连通分量连通分量。v1v2v3v4v5非连通图非连通图G的两个连通分量的两个连通分量强连通图只有强连通图只有一个一个强连通分量强连通分量非强连通图有非强连通图有多个多个强连通分量强连通分量2021/7/2311注意：注意：带
10、权图中权值的含义视具体问题而定带权图中权值的含义视具体问题而定(距离、耗费等距离、耗费等).v若将图中的每一条边赋上一个权值，则称该图为若将图中的每一条边赋上一个权值，则称该图为带权带权图图。带权图又称为。带权图又称为网络网络。381752带权图带权图v2v3v4v5v12021/7/2312 图的存储涉及到两方面：顶点内容的存储和边图的存储涉及到两方面：顶点内容的存储和边( (逻辑逻辑关系关系) )的存储。图的存储所采用的两种常用方法为：的存储。图的存储所采用的两种常用方法为：邻接邻接矩阵矩阵和和邻接表邻接表。7.2.1 7.2.1 邻接矩阵表示法邻接矩阵表示法7.2 7.2 图的存储结构图
11、的存储结构1.邻接矩阵定义邻接矩阵定义邻接矩阵邻接矩阵指的是表示图中顶点之间相邻关系的矩阵。指的是表示图中顶点之间相邻关系的矩阵。7.22021/7/2313设设G=(V,E)是具有是具有n个顶点的图，则个顶点的图，则G的邻接矩阵为具有如下性的邻接矩阵为具有如下性质的质的n阶方阵：阶方阵： 1：若：若 (vi+1,vj+1) 或或 是是E(G)中的边中的边 Ai,j= 0：若：若(vi+1,vj+1) 或或 不是不是E(G)中的边中的边v有向图（无向图）的有向图（无向图）的邻接矩阵邻接矩阵2021/7/2314A=0 1 1 1 00 0 1 0 10 0 0 0 00 0 0 0 10 0
12、0 1 0邻接矩阵邻接矩阵有向图的邻接矩阵通常是有向图的邻接矩阵通常是非对称非对称的的7.2邻接矩阵邻接矩阵A=0 1 1 1 01 0 1 0 11 1 0 0 01 0 0 0 10 1 0 1 0无向图的邻接矩阵是无向图的邻接矩阵是对称对称的的v2v3v4v5v1v2v3v4v5v12021/7/2315邻接矩阵邻接矩阵A=0 3 5 1 03 0 2 0 85 2 0 0 01 0 0 0 70 8 0 7 0网络的邻接矩阵定义为：网络的邻接矩阵定义为： wij:若若 (vi+1,vj+1) 或或 是是E(G)中的边中的边 Ai,j= 0或或 :若若 (vi+1,vj+1) 或或 不是
13、不是E(G)中的边中的边381752带权图带权图v2v3v4v5v12021/7/2316 2.邻接矩阵存储结构描述：邻接矩阵存储结构描述： #define n . /* 图中图中顶点个数顶点个数 */ #define e . /* 图中图中边边(弧弧)条数条数 */ typedef char vextype; /* 顶点数据类型顶点数据类型 */ typedef float adjtype; /* 权值类型权值类型 */ typedef struct vextype vexsn; /* 数组数组vexs 用于存储顶点数据用于存储顶点数据 */ adjtype arcsnn; /* arcs
14、为邻接矩阵为邻接矩阵 */ graph; 若图中顶点信息仅为编号若图中顶点信息仅为编号, 则仅需存储一个邻接矩阵即可表示图。则仅需存储一个邻接矩阵即可表示图。2021/7/2317 scanf(%d%d%f,&i,&j,&w); ga arcsi-1j-1=w; /*有向网有向网*/ scanf(%d%d%f,&i,&j,&w); ga arcsi-1j-1=1; /*有向图有向图*/ scanf(%d%d,&i,&j); ga arcsi-1j-1=1; /*若为无向图若为无向图*/ ga arcsj-1i-1=1; scanf(%d%d%f,&i,&j,&w); ga arcsi-1j-1
15、=w; /*因为是无向网因为是无向网*/ ga arcsj-1i-1=w; 建立一个采用邻接矩阵表示法实现存储的建立一个采用邻接矩阵表示法实现存储的无向网无向网的算法如下：的算法如下：creatgraph(ga)graph ga; int i,j,k; float w; for(i=0;in;i+) ga vexsi=getchar( ); for(i=0;in;i+) for(j=0;jn;j+) ga arcsij=0; /*初始化邻接矩阵初始化邻接矩阵*/ for(k=0;ke;k+)3.建立邻接矩阵建立邻接矩阵7.2该算法的时间复杂度为该算法的时间复杂度为 O(n+n2+e) , 因为
16、因为 en2 ,所以为所以为 O(n2)2021/7/2318 adjvex next7.2.2 7.2.2 邻接表表示法邻接表表示法 邻接表表示法类似于树的孩子链表表示法。对于图邻接表表示法类似于树的孩子链表表示法。对于图G G中的某一个顶点中的某一个顶点vivi，将邻接于它的所有顶点链成一个单，将邻接于它的所有顶点链成一个单链表，该单链表称为链表，该单链表称为顶点顶点vivi的邻接表的邻接表。邻接表中结点的结构如下：邻接表中结点的结构如下：邻接点域邻接点域:存放邻接于顶点存放邻接于顶点vi的结点的序号的结点的序号j链域链域:存放指向下一个存放指向下一个结点的指针结点的指针1、邻接表定义、邻
17、接表定义7.2每个邻接表均有一个表头结点，该结点有每个邻接表均有一个表头结点，该结点有两个域两个域，分别存，分别存放顶点放顶点vi的信息和邻接表中第一个结点的指针。的信息和邻接表中第一个结点的指针。vertexlink顶点域顶点域 指针域指针域存放顶点的信息存放顶点的信息存放指向存放指向Vi邻接表中邻接表中第一个结点的头指针，第一个结点的头指针，称为链的表头称为链的表头2021/7/2319将所有的表头结点顺序存储在一个向量中，图就可以用将所有的表头结点顺序存储在一个向量中，图就可以用这个表头向量来表示这个表头向量来表示.7.2v2v3v4v5v1v5v2v3v4v12343554v1v2v3
18、v4v5vertex link邻接表邻接表234135121524v1v2v3v4v5vertex link邻接表邻接表v将无向图的邻接表称为将无向图的邻接表称为边表边表,将有向图的邻接表称为将有向图的邻接表称为出边表出边表2021/7/2320有向图还有一种有向图还有一种逆邻接表逆邻接表为每个顶点为每个顶点vi建立一个建立一个入边表入边表 1 3 4 vertex link v1v2v3v4v512 3 2顶点表顶点表入边表入边表 5 逆邻逆邻接表接表7.2v3v1v2v4v52021/7/2321typedef strcutvextype vertex; edgenode *link; v
19、exnode; /*顶点表结点结构顶点表结点结构*/ 2.邻接表存储结构描述：邻接表存储结构描述： typedef struct node int adjvex; struct node *next edgenode; /*边表结点结构边表结点结构*/ adjvex nextvertexlink顶点域顶点域 指针域指针域7.2vexnode gan;2021/7/2322邻邻接接表表vexnode ga25；vexnode ga14；7.2v3v1v2v4v5v1v4v2v34 21 1 1332 2 v1v2v3v4vertexlink4 顶点表顶点表边表边表5 4 2 1vertex li
20、nkv1v2v3v4v51 2 1 4 顶点表顶点表出边表出边表2021/7/2323 scanf(%d%d,&i,&j); s=malloc(sizeof(edgenode); sadjvex=i;snext=gaj-1.link;gaj-1.link=s; 生成有向生成有向图的入边表图的入边表 scanf(%d%d,&i,&j); s=malloc(sizeof(edgenode); sadjvex=j;snext=gai-1.link;gai-1.link=s; 生成有向生成有向图的出边表图的出边表 scanf(“%d%d”,&i,&j); s=malloc(sizeof(edgenod
21、e); / 生成边表结点生成边表结点 sadjvex=j; snext=gai-1.link; gai-1.link=s; s=malloc(sizeof(edgenode); sadjvex=i; snext=gaj-1.link; gaj-1.link=s;生成无向生成无向图的边表图的边表7.23.建立邻接表的算法描述如下建立邻接表的算法描述如下：creatadjlist(ga)vexnode ga ; int i,j,k; edgenode *s; for(i=0;in;i+)/*读入顶点信息并初始化边表头指针读入顶点信息并初始化边表头指针*/ gai.vertex=getchar( )
22、;gai.link=NULL; for(k=0;ke;k+) 生成无向图的时间复杂度是生成无向图的时间复杂度是O(n+e)O(n+e) 生成有向图的时间复杂度是生成有向图的时间复杂度是O(n+e)O(n+e)2021/7/2324(1) 一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。一。因为邻接表表示中，各边表结点的链接次序取决于因为邻接表表示中，各边表结点的链接次序取决于建立邻接表的算法及边的输入次序。建立邻接表的算法及边的输入次序。4.4.邻接矩阵和邻接表的比较：邻接矩阵和邻接表的比较：7.2(2) 在在邻接表（或逆邻接表）邻接表（或逆
23、邻接表）表示中，每个边表对应于邻接表示中，每个边表对应于邻接矩阵矩阵一行（或一一行（或一 列）列）,边表中结点个数等于边表中结点个数等于一行（或一列）一行（或一列）中非零元素个数。中非零元素个数。(3) n个顶点个顶点 e条边的图条边的图 建立建立 邻接矩阵邻接矩阵 邻接表邻接表 无向图：无向图： O(n2) O(n+2e） 有向图：有向图： O(n2) O(n+e）2021/7/2325(4) 求顶点求顶点vi的度：的度： 邻接矩阵邻接矩阵 邻接表邻接表 无向图：无向图： 第第i行（列）上非零元素个数行（列）上非零元素个数 第第i个边表中结点数个边表中结点数 有向图有向图出度出度：第：第i行
24、上非零元素个数行上非零元素个数 第第i个出边表上的结点数个出边表上的结点数 入度入度： 第第i列上非零元素个数列上非零元素个数 较难，需遍历整个表较难，需遍历整个表 4.4.邻接矩阵和邻接表的比较：邻接矩阵和邻接表的比较：(5) 判断（判断（Vi，Vj）或）或Vi，Vj是否是图的一条边是否是图的一条边 邻接矩阵邻接矩阵：判矩阵中第：判矩阵中第i行行 第第j列的那个元素是否为零列的那个元素是否为零 邻接表中邻接表中：扫描第：扫描第i个边表个边表O(n)2021/7/2326(6) 求边数求边数e 邻接矩阵邻接矩阵：检测整个矩阵：检测整个矩阵 O(n2) 邻接表邻接表： 计算边表结点个数之和计算边
25、表结点个数之和 O(e+n)7.2稠密图稠密图：对：对n个顶点的图，若个顶点的图，若e接近于接近于n*(n-1) （有向图）或（有向图）或 e接近于接近于n*(n-1)/2(无向图无向图)则称该图为稠密图；则称该图为稠密图；稀疏图稀疏图：对：对n个顶点的图，若个顶点的图，若en*(n-1) (有向图有向图) 或或 e v2 - v4 - v8 - v5 - v3 - v6 - v7特点：遍历过程中尽可能地先对纵深方向进行搜索特点：遍历过程中尽可能地先对纵深方向进行搜索v1v2v4v5v6v3v7v82021/7/2334fffff 假设从假设从v1开始出发进行遍历开始出发进行遍历:v1DFS
26、(1)v2tv3tDFS (4)DFS (3)DFS (2)v5tv4tDFS (0)0 1 1 1 01 0 1 0 11 1 0 0 01 0 0 0 10 1 0 1 0int visitedn;graph g;DFS( i )int i;int j; printf(%c,g.vexsi); visitedi=true; for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj) DFS(j); i=0j=011j=211 1j=4111j=31 1i=1i=2i=1i=4i=3i=4i=1i=01 1 邻接矩阵邻接矩阵g.arcsnnprintf(%c,g.ve
27、xsi);visitedi=true; for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj)DFS(j);printf(%c,g.vexsi);visitedi=true; for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj)执行结果执行结果:tj=1j=0printf(%c,g.vexsi);visitedi=true; for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj)printf(%c,g.vexsi);visitedi=true; for(j=0;jn;j+) if(g.arcsij=1)&(!
28、visitedj)DFS(j);printf(%c,g.vexsi);visitedi=true; for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj) for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj)DFS(j);printf(%c,g.vexsi); for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj) for(j=0;jadjvex-1) /*从从vi的未曾访问过的邻接点出的未曾访问过的邻接点出 发进行深度优先搜索发进行深度优先搜索*/ DFSL(p-adjvex-1); p=p-next; /
29、*找找vi的下一邻接点的下一邻接点*/以邻接表为存储结构的深度优先算法以邻接表为存储结构的深度优先算法以邻接表为存储结构的深度优先算法以邻接表为存储结构的深度优先算法: : : :2021/7/23372021/7/2338 对图进行深度优先搜索得到的顶点序列称为对图进行深度优先搜索得到的顶点序列称为深度优先深度优先深度优先深度优先搜索序列，搜索序列，搜索序列，搜索序列，简称为简称为简称为简称为DFSDFS序列序列序列序列。注意注意7.3DFS序列序列不唯一，不唯一，它与遍历它与遍历算法，算法，图的图的存存储结构储结构以及以及初始出发点初始出发点有关有关。3.3.算法分析算法分析对于具有对于具
30、有n n个顶点、个顶点、e e条边的连通图条边的连通图： 算法的时间复杂度为算法的时间复杂度为: DFS-O(n2) DFSL-O(n+e) 算法的空间复杂度为算法的空间复杂度为O(n)2021/7/23397.3三、三、 连通图的广度优先搜索遍历连通图的广度优先搜索遍历(Breadth First Search)1. BFS基本思想基本思想 1）从图）从图G中任一顶点中任一顶点vi出发，访问顶点出发，访问顶点vi； 2）依次访问）依次访问vi的所有未曾过的邻接点；的所有未曾过的邻接点； 3）分别从这些邻接点出发广度优先搜索遍历图。）分别从这些邻接点出发广度优先搜索遍历图。2021/7/234
31、0v1v2v4v5v6v3v7v8v1 - v2 - v3 - v4 - v5 - v6 - v7 - v8特点：尽可能地先对横向进行搜索特点：尽可能地先对横向进行搜索。2021/7/2341 P2k2viP11 P12 P1k1P21 P22 p2i 一步一步能通达的坐标点能通达的坐标点二步二步能通达的坐标点能通达的坐标点R步步能通达的坐标点能通达的坐标点 2.2.算法实现算法实现: :BFS算法符合算法符合先进先出先进先出性质。在算法实现过程中，引入性质。在算法实现过程中，引入队列队列作为辅助存储结构，存储已被访问的顶点。作为辅助存储结构，存储已被访问的顶点。2021/7/2342n在广度
32、优先搜索遍历中，先被访问的顶点，在广度优先搜索遍历中，先被访问的顶点，其邻接点亦先被访问，所以在算法的实现中其邻接点亦先被访问，所以在算法的实现中需要使用一个需要使用一个队列队列，用来依次记住被访问过，用来依次记住被访问过的顶点。的顶点。n算法开始时，将初始点访问后插入队列中，算法开始时，将初始点访问后插入队列中，以后每从队列中删除一个元素，就依次访问以后每从队列中删除一个元素，就依次访问它的每一个未被访问过的邻接点，并令其进它的每一个未被访问过的邻接点，并令其进队，这样，当队列为空时，表明所有与初始队，这样，当队列为空时，表明所有与初始点有路径相通的顶点都以访问完毕，算法到点有路径相通的顶点
33、都以访问完毕，算法到此结束。此结束。2.2.算法实现算法实现: :2021/7/2343 BFS(int k) int i，j; InitQueue(Q); printf(%cn,g.vexsk); visitedk=true; enqueue(Q,k); while (!empty(Q) i=dequeue(Q); /vi出队出队 for(j=0;jn;j+) /依次搜索依次搜索vi的邻接点的邻接点 if(g.arcsij=1&!visitedj) printf(“%cn”,g.vexsj); visitedj=true; enqueue(Q,j); /访问过的访问过的vj入队入队 /* 从
34、从vk出发广度优先搜索图出发广度优先搜索图,以邻接矩阵作存储结构以邻接矩阵作存储结构*/2021/7/2344 BFSL(int k) /*以邻接表作存储结构以邻接表作存储结构*/ int i; edgenode *p; InitQueue(Q); printf(%cn,glk.vertex); visitedk=true; enqueue(Q,k); while (! empty(Q) i=dequeue(Q); p=gli.link; /取取vi的边表头指针的边表头指针 while(p!=null) if(!visitedpadjvex-1) /依次搜索依次搜索vi的的邻接点邻接点 pri
35、ntf(%cn,glpadjvex-1.vertex); visitedpadjvex-1=true; enqueue(Q, padjvex-1); p=pnext; v5v2v3v4v1234135121524v1v2v3v4v5vertex link2021/7/23452021/7/23467.3 对图进行广度优先搜索得到的顶点序列称为对图进行广度优先搜索得到的顶点序列称为广度优先搜索广度优先搜索广度优先搜索广度优先搜索序列，简称为序列，简称为序列，简称为序列，简称为 BFSBFS序列序列序列序列。两种遍历方法比较两种遍历方法比较两种遍历方法比较两种遍历方法比较：BFS序列序列不唯一不唯
36、一不唯一不唯一，BFS序列与遍历序列与遍历算法算法算法算法，图的图的存存存存储结构储结构储结构储结构以及以及初始出发点初始出发点初始出发点初始出发点有关有关。 二者对顶点的搜索次序不同二者对顶点的搜索次序不同 两种遍历方法实现的手段不同两种遍历方法实现的手段不同注意注意 两种遍历方法的时间复杂度相同两种遍历方法的时间复杂度相同2021/7/2347四四四四. . . .非连通图的遍历非连通图的遍历非连通图的遍历非连通图的遍历非连通图非连通图非连通图非连通图具有两个或两个以上的连通分量具有两个或两个以上的连通分量, , 当从某个顶点当从某个顶点vivi开开始对其进行深度或广度优先搜索只能遍历包含
37、顶点始对其进行深度或广度优先搜索只能遍历包含顶点vivi的连通分的连通分量。量。v1v2v3v4v5具有两个连通分量的非连通图具有两个连通分量的非连通图GC1C2非连通图的遍历须非连通图的遍历须多次调用多次调用深度或广度优先搜索算法深度或广度优先搜索算法.7.32021/7/2348非连通图遍历算法描述：非连通图遍历算法描述： TRAVER( ) int i; for (i=0;in;i+) visitedi=false; for (i=0;in;i+) if(!visitedi) DFS(i); 遍历各个遍历各个连通分量连通分量初始访问标初始访问标志志深度优先搜索深度优先搜索遍历非连通图算法
38、遍历非连通图算法BFSL(i);广度优先搜索广度优先搜索遍历非连通图算法遍历非连通图算法如果图是连通的如果图是连通的, ,则算法则算法TRAVERTRAVER只调用一次只调用一次DFS(DFS(或或BFS)BFS)；如果图包含如果图包含n n个连通分量个连通分量, ,则算法则算法TRAVERTRAVER调用调用n n次次DFS(DFS(或或BFS)BFS)；7.32021/7/2349特点：特点：a.无向连通图的生成树通常是不唯一的无向连通图的生成树通常是不唯一的b.生成树满足连通性且边数最小生成树满足连通性且边数最小一、生成树一、生成树：连通图连通图G的的一个极小连通子图，如果是一个极小连通
39、子图，如果是含有含有G的所有的顶点的树，的所有的顶点的树，则称该子图为生成树。则称该子图为生成树。v5v2v3v4v1v3v5v2v4v1v5v2v3v4v1v5v2v3v4v1 7.4 7.4 生成树和最小生成树生成树和最小生成树2021/7/2350无向非连通图无向非连通图没有生成树，但其各个连通分量有生成树，各个连通没有生成树，但其各个连通分量有生成树，各个连通分量的生成树形成一个森林，称为分量的生成树形成一个森林，称为无向非连通图的生成森林无向非连通图的生成森林。如何求无向连通图的生成树？如何求无向连通图的生成树？对左图深度遍历对左图深度遍历得到的生成树得到的生成树可由两种遍历算法求得
40、：可由两种遍历算法求得：若从图的某顶点出发，作一次深度优先搜索或广度优先若从图的某顶点出发，作一次深度优先搜索或广度优先搜索，可以访问到图中所有顶点，则搜索，可以访问到图中所有顶点，则遍历遍历时经过的边和时经过的边和图的所有顶点所构成的子图，称作该图的所有顶点所构成的子图，称作该图的生成树图的生成树。v5v2v3v4v1v5v2v3v4v12021/7/2351V1V2V4V5V8V3V6V7深度优先生成树V1V2V4V5V8V3V6V7广度优先生成树2021/7/2352二二. 最小生成树最小生成树(MST:Minimum Spanning Tree) 无向连通图无向连通图的生成树通常是不唯
41、一的，因此，的生成树通常是不唯一的，因此，无向连通网无向连通网的的生成树通常也是不唯一的。生成树通常也是不唯一的。 无向连通网生成树的权定义无向连通网生成树的权定义为生成树各边权值之和。为生成树各边权值之和。 无向连通网的所有生成树中权值最小的生成树称为该无向连通网的所有生成树中权值最小的生成树称为该 连通网的连通网的最小生成树，记为最小生成树，记为MST。7.42021/7/2353最小生成树的应用：最小生成树的应用：n网络的最小生成树在实际中有广泛应用。例如，网络的最小生成树在实际中有广泛应用。例如，在设计通信线路时，用图的顶点表示城市，用边在设计通信线路时，用图的顶点表示城市，用边(v,
42、w)的权的权cvw表示建立城市表示建立城市v和城市和城市w之间的之间的通信线路所需的费用，则最小生成树就给出了建通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。立通信网络的最经济的方案。 2021/7/235435v2v3v4v5v18172最小生成树最小生成树v5v2v3v4v1w=225872v5v2v3v4v1w=133172v3v5v2v4v1w=1658122021/7/2355如何求无向连通网的最小生成树？如何求无向连通网的最小生成树？两种常用的算法分别是：两种常用的算法分别是：Prim算法和算法和Kruskal算法。算法。1.最小生成树的最小生成树的MST性质
43、。性质。 设设G=(V,E)是一个连通网，是一个连通网，U是顶点集是顶点集V的真子集。若的真子集。若(u,v)是是G中所有一个顶点在中所有一个顶点在U中，另一个顶点在中，另一个顶点在V-U 中的中的所有边中权值最小的一条边，则必存在一棵包含边所有边中权值最小的一条边，则必存在一棵包含边(u,v)的最小生成树。的最小生成树。7.42021/7/23567.4Prim 算法和算法和 Kruskal 算法均用到了最小生成树的算法均用到了最小生成树的MST性质。性质。Prim算法思想算法思想:假设假设G=(V,E)为连通网络，生成的最小生成树为为连通网络，生成的最小生成树为T=（V，TE）。）。求求T
44、（实际上是求（实际上是求TE）的步骤为：）的步骤为：1）初始化：）初始化：U=u0(u0属于属于V)，TE= ；2）在所有）在所有u属于属于U，v属于属于V-U的边的边(u,v) 中找一条权值最小的边中找一条权值最小的边(u0,v0) 并入集合并入集合TE，同时，同时v0并入并入U；3）如果）如果U=V，则算法结束，否则重复，则算法结束，否则重复2）。）。2. prim算法算法2021/7/235712435665157352461243561532412435615324124356152451243561524512435615455124356186587.42021/7/2358Pri
45、m算法实现描述：算法实现描述：typedef structint fromvex,endvex; float length; edge;float distnn;edge tn-1;prim( )prim( )int j,k,m,v,min,max=10000; float d; edge e; for(j=1;jn;j+) /*构造初始边集构造初始边集T0Tn-2,为侯选边集为侯选边集*/ tj-1.fromvex=1; /*候选边的起点为第一个加入树中的顶点候选边的起点为第一个加入树中的顶点v1*/ tj-1.endvex=j+1; /*候选边的终点为候选边的终点为V-U中的点中的点*/
46、tj-1.length=dist0j; /*终点为终点为Vj的候选边长度的候选边长度*/生成树边的生成树边的存储结构存储结构dist和和t分别存储分别存储无向连通网的带权邻无向连通网的带权邻接矩阵和生成树的边接矩阵和生成树的边边的权值边的权值2021/7/2359 for(k=0;kn-1;k+) /*求求T中第中第k条边条边*/ min=max; for(j=k;jn-1;j+) /*扫描当前侯选边集扫描当前侯选边集Tk到到Tn-2,找最短边找最短边*/ if(tj.lengthmin)min=tj.length;m=j;/*记录当前最短候选边的位置记录当前最短候选边的位置*/ e=tm;t
47、m=tk;tk=e; v=tk.endvex; /*Tk和和Tm交换后交换后,生成的树边生成的树边:t0tk*/ for(j=k+1;jn-1;j+) /*调整候选边集边调整候选边集边tk+1tn-2*/ d=disttj.endvexv; if(dtj.length)tj.length=d;tj.fromvex=v; prim算法的时间复杂度为算法的时间复杂度为O(n2) 2021/7/2360Kruskal算法思想算法思想：n设设G= (V,E)是连通网，令最小生成树的初态为只有是连通网，令最小生成树的初态为只有n个个顶点而无边的非连通图顶点而无边的非连通图T=(V, )，图中每个顶点自成
48、一个图中每个顶点自成一个连通分量。连通分量。n在在E中选择权值最小的边，若该边依附的顶点落在中选择权值最小的边，若该边依附的顶点落在T中中不同的连通分量上，则将此边加入到不同的连通分量上，则将此边加入到T中，否则舍去此边中，否则舍去此边而选择下一条权值最小的边。而选择下一条权值最小的边。n依次类推，直到依次类推，直到T中所有顶点都在同一连通分量上为止。中所有顶点都在同一连通分量上为止。该连通分量即为最小生成树。该连通分量即为最小生成树。3. Kruskal算法算法2021/7/2361Kruskal算法产算法产生的最小生成树生的最小生成树 Kruskal算法的初略描述：算法的初略描述： T=(
49、V, ); while(T中所含边数中所含边数n-1) 从从E中选取当前权值最小边中选取当前权值最小边(u,v); 从从E中删去边中删去边(u,v); if (u,v)并入并入T之后不产生回路之后不产生回路) 将边将边(u,v)并入并入T中中; 35v2v3v4v5v18172v5v2v3v4v13(c)1(a)7(d)2(b)2021/7/23622021/7/2363 7.5 最最 短短 路路 径径两顶点之间路径的长度：两顶点之间路径的长度：定义为路径上各边权值之和。定义为路径上各边权值之和。两点间最短路径：两点间最短路径：指的是带权图中，两顶点之间所有路径中指的是带权图中，两顶点之间所有
50、路径中长度最小的路径。长度最小的路径。考虑到实际问题的有向性，将路径上的第一个顶点称为考虑到实际问题的有向性，将路径上的第一个顶点称为源点源点(source)(source)，最后一个顶点称为最后一个顶点称为终点终点(destination)(destination)。并为了叙并为了叙述方便，把源点述方便，把源点v v到终点到终点w w的最短路径简称为顶点的最短路径简称为顶点w w的路径。的路径。1、定义、定义7.52021/7/23647.5.1 7.5.1 单源最短路径单源最短路径一、定义：一、定义：对给定的有向网对给定的有向网G=(V,E)和源点和源点v，求源点，求源点v到到G中其余各顶
51、点的中其余各顶点的最短路径最短路径。首先直观地看一下如下有向网及源点首先直观地看一下如下有向网及源点v1的单源最短路径。的单源最短路径。7.5源点源点 中间点中间点 终点终点 路径长度路径长度 1 2 10 1 4 30 1 4 3 50 1 4,3 5 60路径长度是递增路径长度是递增结论：结论：当按长度增长的顺序当按长度增长的顺序求源点到各顶点的最短路径求源点到各顶点的最短路径时，中间点的最短路径在求时，中间点的最短路径在求该点最短路径之前已经求出。该点最短路径之前已经求出。110100503010602025342021/7/2365二、对给定的有向网二、对给定的有向网G=(V,E)和源
52、点和源点v，如何求单源最，如何求单源最短路径？短路径？Dijkstra算法算法1、Dijkstra算法思想：算法思想：从给定的源点开始，按路径长度递增的顺序，逐从给定的源点开始，按路径长度递增的顺序，逐步产生源点到其余各顶点的最短路径。步产生源点到其余各顶点的最短路径。7.52021/7/23661) 基本原理基本原理：设置一个顶点集合设置一个顶点集合S，S中的所有顶点其最短路径已经中的所有顶点其最短路径已经求出，求出，初始时初始时S=v，则尚未求出最短路径的顶点集为，则尚未求出最短路径的顶点集为V-S。另外，设。另外，设置一个置一个数组数组d ，若顶点，若顶点vi的最短路径已求出，则的最短路
53、径已求出，则di存放的是最短路径存放的是最短路径长度，否则长度，否则di存放的是从顶点存放的是从顶点v经经S 中的顶点到中的顶点到vi的所有路径中最短路的所有路径中最短路径的长度，径的长度，并称其为并称其为vi的距离的距离。初始时。初始时 wi 若若为为G中的边中的边 di= 若若不是不是G中的边中的边7.5设设 vj 为为 V-S 中距离最短的顶点，可以证明中距离最短的顶点，可以证明（1）dj为为vj的最短路径的长度；的最短路径的长度；（2）顶点）顶点vj为为V-S中最短路径长度最短的顶点。中最短路径长度最短的顶点。2、算法思想的具体实现、算法思想的具体实现：2021/7/2367udj为为
54、vj的最短路径的长度的最短路径的长度证明：证明：若若dj不是不是vj的最短路径长度，则从源点的最短路径长度，则从源点v到顶点到顶点vj必存在另外一条路径必存在另外一条路径P，其长度小于，其长度小于dj。由距离的定义可知路径。由距离的定义可知路径P必包含一个或多个属于必包含一个或多个属于V-S的中间顶的中间顶点，设第一个这样的顶点为点，设第一个这样的顶点为vk，v沿路径沿路径P到到vk的路径长度为的路径长度为d1， vk沿路径沿路径P到到vj的路径长度为的路径长度为d2,则则P的长度为的长度为d1+d2，d1+d2dj。因为因为dk=0，所以，所以dk=d1+d2dj，而，而dk=dj；2）若若
55、Pi除经过除经过S中的顶点外，还经过中的顶点外，还经过V-S中的中间顶点，设中的中间顶点，设vk为为V-S中第一中第一个这样的中间顶点，显然个这样的中间顶点，显然Pi的长度为的长度为dk加上加上vk至至vi这段路径的长度这段路径的长度d，因，因为为dk=dj，而，而vk至至vi这段路径的长度这段路径的长度d=0，所以，所以Pi的长度的长度=dj。由此。由此可知可知V-S中任一顶点的最短路径长度均大于等于中任一顶点的最短路径长度均大于等于vj的最短路径长度。的最短路径长度。结论：经上述两点的证明可知，在求单源最短路径的过程结论：经上述两点的证明可知，在求单源最短路径的过程中当顶点集中当顶点集S一
56、定时，可从一定时，可从V-S中选取距离最短的顶点，将中选取距离最短的顶点，将其扩充到其扩充到S中，且该顶点的距离即为其最短路径长度。中，且该顶点的距离即为其最短路径长度。2021/7/23692）提出问题：）提出问题：当从当从V-S中选取距离最短的顶点，将其扩充中选取距离最短的顶点，将其扩充到到S中之后，中之后，V-S中顶点的中顶点的d值可能会发生变化，因此需值可能会发生变化，因此需对对V-S中各顶点的中各顶点的d值进行调整。值进行调整。如何调整？如何调整？7.52、算法思想的具体实现、算法思想的具体实现：2021/7/2370证明：证明：设设V-S中任一顶点中任一顶点vj的距离因的距离因vk
57、加入到加入到S中而发生了变化，但其新的距中而发生了变化，但其新的距离不为离不为dk+，则必存在一条从，则必存在一条从v经顶点经顶点vk、vx到到vj的路径，其长度的路径，其长度dj小于小于vj的原来距离的原来距离dj。若。若vk到到vx 、vx到到vj的路径长度分别为的路径长度分别为d1和和d2,由由于于vx先于先于vk加入到加入到S中，所以中，所以dx=dk,则则dx+d2=dk+d1+d2=dj，而，而vj的原来距离的原来距离dj=dx+d2,因此因此dj=dk+d1+d2=dj，与假设矛盾。所，与假设矛盾。所以以vj的新的距离值的新的距离值dj 为为dk+。7.5vvkvxvj此段长度为
58、此段长度为d1此段长度为此段长度为d22021/7/2371结论：结论：由此得到了因新的顶点由此得到了因新的顶点vk加入到加入到S中之后对中之后对V-S中各顶点距离进中各顶点距离进行调整的方法，即：行调整的方法，即：对对V-S中任意顶点中任意顶点vj，若，若djdk+,则将则将dk+的值赋给的值赋给dj,否则，否则，dj的值不变。的值不变。3）Djkstra算法的粗略描述：算法的粗略描述： S=v; /*初始化初始化V-S中各顶点的距离值中各顶点的距离值*/ while(S中的顶点数中的顶点数n) 从从V-S中选取距离值最小的顶点中选取距离值最小的顶点vj; S=S+vj; 调整调整V-S中各
59、顶点的距离值；中各顶点的距离值； 2021/7/23724)Djkstra算法的详细描述：算法的详细描述： float dn;/*存放各顶点的距离值存放各顶点的距离值*/ int pn,sn;/*Pn为路径向量为路径向量,Pi记录从源点到达记录从源点到达i+1点的最短路径上点的最短路径上 该点的前趋顶点该点的前趋顶点,sn为最短路径均已求出的顶点集合为最短路径均已求出的顶点集合*/ djkstra(c,v) float c n;/*C为有向网络的带权邻接距阵为有向网络的带权邻接距阵*/ int v; int i,j,k,v1,pre; int min,max=200,inf=300; v1=v
60、-1; for(i=0;in;i+) di=cv1i; if (di!=max) pi=v else pi=0; for(i=0;in;i+) si=0; sv1=1;dv1=0; for(i=0;imax*/ for(j=0;jn;j+) /*在当前在当前V-S集中选距离值最小的顶点集中选距离值最小的顶点*/ 初始化距离数组初始化距离数组d和记录顶和记录顶点最短路径上该顶点直接前点最短路径上该顶点直接前趋顶点序号的数组。趋顶点序号的数组。S集合赋初值集合赋初值2021/7/2373 if (!sj &(djmin) min=dj;k=j; sk=1; for(j=0;jdk+ckj) dj=
61、dk+ckj;/*修改修改V-S集合中顶点集合中顶点j的距离的距离*/ pj=k+1;/*k+1是是j+1的前趋的前趋*/ for (i=0;in;i+) printf(“n%ft%d”,di,i+1); pre=pi;/*继续找前趋顶点继续找前趋顶点*/ while (pre!=0) printf(-%d,pre);pre=ppre-1; printf(“n”); 求求V-S中距离最短的顶点中距离最短的顶点并将该顶点放入集合并将该顶点放入集合S中中调整调整V-S顶点的距离顶点的距离输出各顶点最短输出各顶点最短路径长度和轨迹路径长度和轨迹Djkstra算法的时间复杂度为算法的时间复杂度为O(n
62、2)，空间复杂度为，空间复杂度为O(n)。2021/7/2374打印输出的结果为打印输出的结果为:max1max2203-404305-3-415234101003050106020循环循环S集合集合初始化初始化K+1D0.D4P0.P412344-max max 20 0 60max max 20 0 30max max 20 0 30max max 20 0 30max max 20 0 30 0 0 4 0 4 0 0 4 0 3 0 0 4 0 3 0 0 4 0 3 0 0 4 0 34,34,3,54,3,5,14,3,5,1,253212021/7/23752021/7/2376
63、7.5.2 7.5.2 所有顶点对之间的最短路径所有顶点对之间的最短路径1.定义：定义：所有顶点对之间的最短路径问题指的是：对给定的有所有顶点对之间的最短路径问题指的是：对给定的有向网向网G=(V,E)，求，求G中每一对顶点之间的最短路径。中每一对顶点之间的最短路径。2.解决方法：解决方法：方法一：方法一：每次以一个顶点为源点，重复执行每次以一个顶点为源点，重复执行DjkstraDjkstra算法算法n n次。这样可求得每一对顶点之间的最短路径。总的执行时次。这样可求得每一对顶点之间的最短路径。总的执行时间为间为O(nO(n3 3) )。方法二：方法二：是采用是采用FloydFloyd算法，该
64、算法的时间复杂度也是算法，该算法的时间复杂度也是O O(n(n3 3) ) ，但形式上简单些。，但形式上简单些。7.52021/7/2377 假设有向网采用邻接矩阵假设有向网采用邻接矩阵cnn存储。对该邻接矩阵，存储。对该邻接矩阵，若若不不存在，则存在，则cij=max;当当i=j时，时，cij=0。 1）Floyd算法的基本思想：算法的基本思想： 假设求从顶点假设求从顶点vi到到vj的最短路径。如果从的最短路径。如果从vi到到vj有弧，有弧，则从则从vi到到vj存在一条长度为存在一条长度为cij的路径，该路径不一定是从的路径，该路径不一定是从vi到到vj的最短路径，需进行的最短路径，需进行n
65、次试探。次试探。7.53.Floyd算法算法2021/7/2378 (1)首先考虑路径首先考虑路径(vi,v1,vj)是否存在，是否存在，即判断弧即判断弧,是否存在。是否存在。如果存在，则比较如果存在，则比较(vi,vj)和和(vi,v1,vj)的路径长度取长度较短者为从的路径长度取长度较短者为从vi到到vj的中间顶点的序号不大于的中间顶点的序号不大于1的最短路径。的最短路径。(2)其次，考虑从其次，考虑从vi到到vj是否包含是否包含v2为中间点的路径为中间点的路径(vi,v2,vj)。若没若没有，则从有，则从vi到到vj的当前最短路径仍然是第的当前最短路径仍然是第(1)步中求出的；步中求出的
66、； 若有，则若有，则(vi,v2,vj)可分解为两条路径可分解为两条路径(vi,v2)和和(v2,vj)，而这两条路径是，而这两条路径是前一次求出的中间顶点序号不大于前一次求出的中间顶点序号不大于1的最短路径，将这两条路径长度相加的最短路径，将这两条路径长度相加得到路径得到路径(vi,v2,vj)的长度，将该长度与前次求出的中间序号不大于的长度，将该长度与前次求出的中间序号不大于1的最短路径长度相比较，取其较短者作为当前求得的从的最短路径长度相比较，取其较短者作为当前求得的从vi到到vj的中间顶的中间顶点序号不大于点序号不大于2的最短路径。的最短路径。2021/7/23797.5(3)然后，再
67、选择顶点然后，再选择顶点v3加入当前求得的从加入当前求得的从vi到到vj中间顶点序号不大于中间顶点序号不大于3的的最短路径中，最短路径中，按上述步骤进行比较，从未加入顶点按上述步骤进行比较，从未加入顶点v3作中间点的最短路作中间点的最短路径和加入顶点径和加入顶点v3作中间点的新路径中选取较小者，作为当前求得的从作中间点的新路径中选取较小者，作为当前求得的从vi到到vj的中间顶点序号不大于的中间顶点序号不大于3的最短路径。的最短路径。 依此类推，直到考虑了顶点依此类推，直到考虑了顶点v n加入当前从加入当前从vi到到vj的最短路径后，选出从的最短路径后，选出从vi到到vj的中间顶点序号不大于的中
68、间顶点序号不大于n的最短路径为止，该最短路径就是从的最短路径为止，该最短路径就是从vi到到vj的最短路径。的最短路径。按上述思想方法，经过按上述思想方法，经过n次迭代后可以同时求出各顶点间的最短路径。次迭代后可以同时求出各顶点间的最短路径。2021/7/23807.5定义一个定义一个nn的方阵序列：的方阵序列：A(0)， A(1) ， A(2) ， A(k) ， A(n) 其中其中: A(0)ij=cij A(k+1) ij=MinA(k) ij, A(k) ik+ A(k) kj 0=k=n-1 2)实现原理：实现原理：3）具体实现：）具体实现： a) Floyd算法在具体实现时仅使用一个算
69、法在具体实现时仅使用一个nn的方阵的方阵A，初始时，初始时A= cij,通过在通过在A上进行上进行n次迭代求得次迭代求得A(n) 。 由于是在同一个矩阵由于是在同一个矩阵A中迭代，所以中迭代，所以A(k+1) ij A(k) ik+ A(k) kj是由是由Aij A ik+ A kj实现的。实现的。2021/7/2381b) 算法实现中，还设置了一个路径矩阵算法实现中，还设置了一个路径矩阵pathnn，用于存储各个顶点间用于存储各个顶点间最短路径的顶点轨迹。在求最短路径的顶点轨迹。在求A(k+1)迭代中求得的迭代中求得的pathij，是从，是从i+1到到j+1的的中间顶点序号不大于中间顶点序号
70、不大于k+1的最短路径上顶点的最短路径上顶点i的直接后继顶点的序号。的直接后继顶点的序号。算法结束时，由算法结束时，由pathij的值可得到从的值可得到从i+1到到j+1的最短路径上各个顶点。的最短路径上各个顶点。 4) Floyd算法的具体描述：算法的具体描述：int pathnn;floyd(a,c)float an,cn;int i,j,k,next; int max=160;2021/7/2382 for (i=0;in;i+) for (j=0;jn;j+) if (cij!=max) pathij=j else pathij=-1; aij=cij;for (k=0;kn;k+)
71、for (i=0;in;i+) for (j=0;j(aik+akj) aij=aik+akj; pathij=pathik;for (i=0;in;i+) for (j=0;j%d,next);next=pathnextj; printf(-%dn,j); 进行进行n次迭代次迭代输出各个顶点间输出各个顶点间最短路径的值最短路径的值输出各个顶点间最输出各个顶点间最短路径的顶点轨迹短路径的顶点轨迹2021/7/2383课程代号课程代号课程名称课程名称先修课程先修课程C1C2C3C4C5C6C7C8C9高等数学高等数学程序设计基础程序设计基础离散数学离散数学数据结构数据结构程序设计语言程序设计语言
72、编译技术编译技术操作系统操作系统普通物理普通物理计算机原理计算机原理无无无无C1,C2C3,C5C2C4,C5C4,C9C1C8C3C1C2C8图图GC9C7C4C6C5 7.6 7.6 拓拓 扑扑 排排 序序2021/7/23847.6 7.6 拓拓 扑扑 排排 序序1.什么是拓扑排序？什么是拓扑排序？顶点活动网顶点活动网(Activity On Vertex network):顶点表示活动，边表示活动间的先后关顶点表示活动，边表示活动间的先后关系的有向图。顶点活动网又简称为系的有向图。顶点活动网又简称为AOV网网。拓拓扑扑序序列列：对对于于一一个个AOV网网，常常常常将将其其所所有有顶顶点
73、点排排成成一一个个线线性性序序列列Vi1, Vi2, Vin,该该线线性性序序列列满满足足如如下下关关系系:若若在在AOV网网中中，从从顶顶点点Vii到到顶顶点点Vij有有一一条条路路径径，则则在在线性序列中顶点线性序列中顶点Vii必在顶点必在顶点Vij之前。这样的线性序列称为拓扑序列。之前。这样的线性序列称为拓扑序列。拓扑排序拓扑排序指的是基于指的是基于AOV 网构造拓扑序列的操作。网构造拓扑序列的操作。特点：特点：1）拓扑排序不唯一）拓扑排序不唯一2）任何无回路的）任何无回路的AOV网，其顶点可以排成一个拓扑序列网，其顶点可以排成一个拓扑序列拓扑序列拓扑序列序列序列1：v1 v2 v4 v
74、3序列序列2：v1 v4 v2 v3v1v2v3v42021/7/2385v2v5v6v4v3v1当存在有向环时，若将顶点排成一行，则无论如何安当存在有向环时，若将顶点排成一行，则无论如何安排，必定至少有一条边是与其余边反向的，即改图的排，必定至少有一条边是与其余边反向的，即改图的拓扑序列不存在。拓扑序列不存在。7.62021/7/23867.6二、如何构造拓扑排序？二、如何构造拓扑排序？1、基本思想：、基本思想： 1）从网中选择一个入度为零的顶点且输出之；）从网中选择一个入度为零的顶点且输出之； 2）从网中删除此顶点及其所有出边。）从网中删除此顶点及其所有出边。 反复执行这两步，直至所有顶点
75、都已输出，或者直反复执行这两步，直至所有顶点都已输出，或者直到余留在网中的顶点入度都不为零时为止。到余留在网中的顶点入度都不为零时为止。 2021/7/23872021/7/23887.6v2v1v4v6v5v32021/7/23897.6v2v4v6v5v3拓扑序列拓扑序列v12021/7/23907.6v2v4v5v3拓扑序列拓扑序列v1v62021/7/2391v2v5v3拓扑序列拓扑序列v1v6 v42021/7/2392v2v5拓扑序列拓扑序列v1 v6 v4 v32021/7/2393v5拓扑序列拓扑序列v1 v6 v4 v3 v22021/7/23947.6v2v1v4v6v5v
76、3拓扑序列拓扑序列v1 v6 v4 v3 v2 v52021/7/23957.62、拓扑排序算法的具体实现：、拓扑排序算法的具体实现：技巧技巧1：表的顶点表中增加一个入度域，用于存储各个顶点的当前入度值。：表的顶点表中增加一个入度域，用于存储各个顶点的当前入度值。技巧技巧2：为了避免每次寻找入度为：为了避免每次寻找入度为0的顶点时重复扫描顶点表，引入一个链的顶点时重复扫描顶点表，引入一个链栈栈(队列也可队列也可),将一次扫描找到的入度为将一次扫描找到的入度为0的顶点入栈。这样，以后选入度的顶点入栈。这样，以后选入度为为0的顶点时，可直接从栈顶取。的顶点时，可直接从栈顶取。并且，在排序过程中，一
77、旦出现新的入并且，在排序过程中，一旦出现新的入度为度为0的顶点，将其入栈。的顶点，将其入栈。技巧技巧3：算法在具体实现过程中，没有开辟额外的堆栈空间，而是利用顶：算法在具体实现过程中，没有开辟额外的堆栈空间，而是利用顶点表中入度为点表中入度为0的元素所占空间组成一个静态链栈，入度为的元素所占空间组成一个静态链栈，入度为0的元素的的元素的id域域为静态链栈结点的链域。为静态链栈结点的链域。2021/7/23967.62343554v1v2v3v4v5vertexlink0 1 2 2 0 idtop(top=4)2343554v1v2v3v4v5vertexlink-1 1 2 2 0 id20
78、21/7/23977.6 if (mn) printf(n the network has a cyclen);topsort(dig)vexnode dig ; int i,j,k,m=0,top=-1; edgenode *p;for (i=0;in;i+) if (digi.id=0) digi.id=top; top=i;while (top!=-1) j=top; top=digtop.id; printf(%dt,digj.vertex); m+; p=digj.link; while (p) k=p adjvex; digk.id-; if (digk.id=0) digk.id
79、=top; top=k; p=p next ;/*AOV网的邻接表网的邻接表*/ /*m为输出顶点个数计数器，为输出顶点个数计数器，top为栈指针为栈指针*/ /*建立入度为建立入度为0的顶点链栈的顶点链栈*/ /*栈非空栈非空*/ /*第第j个顶点退栈并输出，计数器加个顶点退栈并输出，计数器加1*/ /*p指向指向vj的出边表结点的指针的出边表结点的指针*/ /*删去所有以删去所有以vj为起点的出边为起点的出边*/ /*的终点的终点vk的入度减的入度减1*/ /*找以找以vj为起点的下一条边为起点的下一条边*/ 4、算法描述、算法描述2021/7/2398小结2021/7/2399个人观点供参考，欢迎讨论
