第6章-图-.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第6章 图 Graph,第6章,图 Graph,6.1,图的基本概念,6.2 图的存储结构,6.3 图的遍历,6.4 生成树和最小生成树,6.5 最短路径,6.6 拓扑排序,6.7 AOV网与关键路径,本章小结,2,第6章 图 Graph,6.1,图的基本概念,6.1.1,图的定义,6.1.2 图的基本术语,1.1.2,逻辑结构类型,4.图形结构,结点之间的关系：,多对多,特点,：每个结点的直接前驱和直接后继的个数都可以是任意的。可能没有开始结点和终端节点，也可能有多个开始结点和终端节点。,树形结构和图形结构统称为非线性结构。,4,第6章 图 Graph,6.1.1,图的定义,图,（Graph）G由两个集合V（Vertex）和E（Edge）组成，记为G=（V,E），其中V是顶点的有限集合，记为V(G)，E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E(G)。,5,第6章 图 Graph,6.1.1,图的定义,通常用字母或自然数（顶点编号）来表示图中的顶点。约定第i（0,i,n）个顶点，即编号为i的顶点用V,i,表示；E(G)表示图G中边的集合。,在图G中，如果代表边的顶点对是无序的，则称G为,无向图,，无向图中代表边的无序顶点对通常用圆括号括起来，用以表示一条无向边。如（,V,i,V,j,）表示顶点,V,i,与,V,j,的一条无向边。（,V,i,V,j,）和（,V,j,V,i,）代表同一条边。,6,第6章 图 Graph,如果表示边的顶点对是有序的，则称G为,有向图,，在有向图中代表边的顶点对通常用尖括号括起来。如 表示从顶点,V,i,到,V,j,的一条弧，顶点,V,i,称为 的尾，顶点,V,j,称为的头。,1,3,0,2,4,(a),1,3,0,2,4,(b),6.1.1,图的定义,9,第6章 图 Graph,6.1.2,图的基本术语,1.端点和邻接点,在一个无向图中，若存在一条边(v,i,v,j,)，则称v,i,和v,j,为此边的两个,端点,，并称它们互为,邻接点,。,在一个有向图中，若存在一条边，则称此边是顶点v,i,的一条出边，同时也是顶点v,j,的一条入边；称v,i,和v,j,分别为此边的起始端点(简称为起点)和终止端点(简称终点)；称v,i,和v,j,互为,邻接点,。,10,第6章 图 Graph,6.1.2,图的基本术语,2.顶点的度、入度和出度,在无向图中，顶点所具有的边的数目称为该,顶点的度,。,在有向图中，以顶点v,i,为终点的入边的数目，称为该顶点的,入度,。以顶点v,i,为始点的出边的数目，称为该顶点的,出度,。一个顶点的入度与出度的和为该顶点的度。,若一个图中有n个顶点和e条边，每个顶点的度为d,i,(1in)，则有：,11,第6章 图 Graph,6.1.2,图的基本术语,3.完全图,若,无向图,中的每两个顶点之间都存在着一条边，,有向图,中的每两个顶点之间都存在着方向相反的两条边，则称此图为,完全图,。,显然，完全无向图包含有 n(n-1)/2 条边，完全有向图包含有n(n-1)条边。例如，图(a)所示的图是一个具有4个顶点的完全无向图，共有6条边。图(b)所示的图是一个具有4个顶点的完全有向图，共有12条边。,12,第6章 图 Graph,6.1.2,图的基本术语,4.稠密图、稀疏图,当一个图接近完全图时，则称为稠密图。相反，当一个图含有较少的边数(即当en(n-1)时，则称为,稀疏图,。,5.子图,设有两个图G=(V,E)和G=(V,E)，若V是V的子集，即V,V，且E是E的子集，即E,E，则称G是G的,子图,。例如图(b)是图(a)的子图，而图(c)不是图(a)的子图。,13,第6章 图 Graph,6.1.2,图的基本术语,6.路径和路径长度,在一个图G=(V,E)中，从顶点v,i,到顶点v,j,的一条,路径,是一个顶点序列(v,i,v,i,1,v,i2,v,im,v,j,)，若此图G是无向图，则边(v,i,v,i,1,),(v,i,1,v,i2,),(v,im-,1,v,im,),(v,im,v,j,)属于E(G)；若此图是有向图，则,属于E(G)。,路径长度,是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。例如，右图中，(v,0,v,2,v,1,)就是一条简单路径，其长度为2。,14,第6章 图 Graph,6.1.2,图的基本术语,7.回路或环,若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环。开始点与结束点相同的简单路径被称为简单回路或简单环。,例如，右图中，(v,0,v,2,v,1,v,0,)就是一条简单回路，其长度为3。,15,第6章 图 Graph,6.1.2,图的基本术语,8.连通、连通图和连通分量,在无向图G中，若从顶点v,i,到顶点v,j,有路径，则称v,i,和v,j,是连通的。,若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。,无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。,16,第6章 图 Graph,6.1.2,图的基本术语,9.强连通图和强连通分量,在有向图G中，若从顶点v,i,到顶点v,j,有路径，则称从v,i,到v,j,是连通的。,若图G中的任意两个顶点v,i,和v,j,都连通,即从v,i,到v,j,和从v,j,到v,i,都存在路径，则称图G是强连通图。例如，右边两个图都是强连通图。,有向图G中的极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。,17,第6章 图 Graph,6.1.2,图的基本术语,10.权和网,图中每一条边都可以附有一个对应的数值,这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图，也称作网。,18,第6章 图 Graph,6.1.2,图的基本术语,例9.1 有n个顶点的有向强连通图最多需要多少条边？最少需要多 少条边？,答：有n个顶点的有向强连通图最多有n(n-1)条边(构成一个有向完全图的情况)；最少有n条边(n个顶点依次首尾相接构成一个环的情况)。,19,第6章 图 Graph,6.2,图的存储结构,6.2.1,邻接矩阵存储方法,6.2.2 邻接表存储方法,20,第6章 图 Graph,6.2.1,邻接矩阵存储方法,邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n(n0)个顶点的图，顶点的顺序依次为(v,0,v,1,v,n-1,)，则G的邻接矩阵,A,是n阶方阵，其定义如下：,(1)如果G是无向图，则：,Aij=1:若(v,i,v,j,)E(G),0:其他,(2)如果G是有向图,则：,Aij=1:若E(G),0:其他,21,第6章 图 Graph,6.2.1,邻接矩阵存储方法,(3)如果G是带权无向图，则：,Aij=,w,ij,:若v,i,v,j,且(v,i,v,j,)E(G),:其他,(4)如果G是带权有向图，则：,Aij=w,ij,:若v,i,v,j,且E(G),:其他,22,第6章 图 Graph,6.2.1,邻接矩阵存储方法,23,第6章 图 Graph,6.2.1,邻接矩阵存储方法,邻接矩阵的特点如下：,(1)图的邻接矩阵表示是惟一的。,(2)无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储的思想，在具体存放邻接矩阵时只需存放上(或下)三角形阵的元素即可。,(3)不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵，因此，当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。,(4)对于无向图，邻接矩阵的第i行(或第i列)非零元素(或非元素)的个数正好是第i个顶点v,i,的度。,24,第6章 图 Graph,6.2.1,邻接矩阵存储方法,(5)对于有向图，邻接矩阵的第i行(或第i列)非零元素(或非元素)的个数正好是第i个顶点v,i,的出度(或入度)。,(6)用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。,25,第6章 图 Graph,6.2.1,邻接矩阵存储方法,邻接矩阵的数据类型定义如下：,#define MAXV ,typedef struct,int no;/*顶点编号*/,InfoType info;/*顶点其他信息*/,VertexType;/*顶点类型*/,typedef struct /*图的定义*/,int edgesMAXVMAXV;/*邻接矩阵*/,int n,e;/*顶点数,弧数*/,VertexType vexsMAXV;/*存放顶点信息*/,MGraph;,26,第6章 图 Graph,6.2.2,邻接表存储方法,图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点v,i,的边(对有向图是以顶点v,i,为尾的弧)。每个单链表上附设一个表头结点。表结点和表头结点的结构如下：,表结点 表头结点,advex,nextarc,info,data,firstarc,27,第6章 图 Graph,6.2.2,邻接表存储方法,表结点 表头结点,adjvex,nextarc,info,data,firstarc,其中，表结点由三个域组成，adjvex指示与顶点v,i,邻接的点在图中的位置，nextarc指示下一条边或弧的结点，info存储与边或弧相关的信息，如权值等。表头结点由两个域组成，data存储顶点v,i,的名称或其他信息，firstarc指向链表中第一个结点。,28,第6章 图 Graph,6.2.2,邻接表存储方法,29,第6章 图 Graph,6.2.2,邻接表存储方法,邻接表的特点如下：,(1)邻接表表示不惟一。这是因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。,(2)对于有n个顶点和e条边的无向图，其邻接表有n个顶点结点和2e个边结点。显然，在总的边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间。,(3)对于无向图，邻接表的顶点v,i,对应的第i个链表的边结点数目正好是顶点v,i,的度。,(4)对于有向图，邻接表的顶点v,i,对应的第i个链表的边结点数目仅仅是v,i,的出度。其入度为邻接表中所有adjvex域值为i的边结点数目。,30,第6章 图 Graph,6.2.2,邻接表存储方法,邻接表存储结构的定义如下：,typedef struct ANode /*弧的结点结构类型*/,int adjvex;/*该弧的终点位置*/,struct ANode*nextarc;/*指向下一条弧的指针*/,InfoType info;/*该弧的相关信息*/,ArcNode;,typedef struct Vnode /*邻接表头结点的类型*/,Vertex data;/*顶点信息*/,ArcNode*firstarc;/*指向第一条弧*/,VNode;,typedef VNode AdjListMAXV;/*AdjList是邻接表类型*/,typedef struct,AdjList adjlist;/*邻接表*/,int n,e;/*图中顶点数n和边数e*/,ALGraph;/*图的类型*/,31,第6章 图 Graph,6.2.2,邻接表存储方法,0,1,2,3,4,1,0,1,0,0,3,2,3,1,2,4,3,4,2,3,4,v,0,v,1,v,2,v,3,v,4,Adjlist 类型,邻接表数组,ArcNode 类型或Anode类型,VNode类型,*firstarc指针，指向一个ArcNode类型的结点,*nextarc指针，指向一个Anode类型的结点,ALGraph类型,32,第6章 图 Graph,6.2.2,邻接表存储方法,例9.2 给定一个具有n个结点的无向图的邻接矩阵和邻接表。,(1)设计一个将邻接矩阵转换为邻接表的算法；,(2)设计一个将邻接表转换为邻接矩阵的算法；,(3)分析上述两个算法的时间复杂度。,解：(1)在邻接矩阵上查找值不为0的元素，找到这样的元素后创建一个表结点并在邻接表对应的单链表中采用前插法插入该结点。算法如下：,33,第6章 图 Graph,void MatToList(MGraph g,ALGraph*&G),/*将邻接矩阵g转换成邻接表G*/,int i,j,n=g.vexnum;ArcNode*p;/*n为顶点数*/,G=(ALGraph*)malloc(sizeof(ALGraph);,for(i=0;iadjlisti.firstarc=NULL;,for(i=0;i=0;j-),if(g.edgesij!=0),p=(ArcNode*)malloc(sizeof(ArcNode);/*创建结点*p*/,p-adjvex=j;,p-nextarc=G-adjlisti.firstarc;/*将*p链到链表后*/,G-adjlisti.firstarc=p;,G-n=n;G-e=g.arcnum;,34,第6章 图 Graph,6.2.2,邻接表存储方法,(2)在邻接表上查找相邻结点，找到后修改相应邻接矩阵元素的值。算法如下：,void ListToMat(ALGraph*G,MGraph&g),int i,j,n=G-n;ArcNode*p;,for(i=0;iadjlisti.firstarc;,while(p!=NULL),g.edgesip-adjvex=1;,p=p-nextarc;,g.vexnum=n;g.arcnum=G-e;,35,第6章 图 Graph,6.2.2,邻接表存储方法,(3)算法1的时间复杂度均为O(n,2,)。算法2的时间复杂度为O(n+e)，其中e为图的边数。,36,第6章 图 Graph,6.3,图的遍历,6.3.1,图的遍历的概念,6.3.2 深度优先搜索遍历,6.3.3 广度优先搜索遍历,6.3.4 非连通图的遍历,6.3.5 图的遍历应用,37,第6章 图 Graph,6.3.1,图的遍历的概念,从给定图中任意指定的顶点(称为初始点)出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。如果给定图是连通的无向图或者是强连通的有向图，则遍历过程一次就能完成，并可按访问的先后顺序得到由该图所有顶点组成的一个序列。,根据搜索方法的不同，图的遍历方法有两种：一种叫做深度优先搜索法(DFS)；另一种叫做广度优先搜索法(BFS)。,38,第6章 图 Graph,6.3.2,深度优先搜索遍历,深度优先搜索遍历的过程是：从图中某个初始顶点v出发，首先访问初始顶点v，然后选择一个与顶点v相邻且没被访问过的顶点w为初始顶点，再从w出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。显然，这个遍历过程是个递归过程。,以邻接表为存储结构的深度优先搜索遍历算法如下(其中，v是初始顶点编号，visited是一个全局数组，初始时所有元素均为0表示所有顶点尚未访问过)：,39,第6章 图 Graph,6.3.2,深度优先搜索遍历,void DFS(ALGraph*G,int v),ArcNode*p;,visitedv=1;/*置已访问标记*/,printf(%d ,v);/*输出被访问顶点的编号*/,p=G-adjlistv.firstarc;,/*p指向顶点v的第一条弧的弧头结点*/,while(p!=NULL),if(visitedp-adjvex=0)DFS(G,p-adjvex);,/*若p-adjvex顶点未访问,递归访问它*/,p=p-nextarc;,/*p指向顶点v的下一条弧的弧头结点*/,40,第6章 图 Graph,6.3.2,深度优先搜索遍历,例如，以上图的邻接表为例调用DFS()函数,假设初始顶点编号v=2，给出调用DFS()的执行过程，见教材。,41,第6章 图 Graph,6.3.3,广度优先搜索遍历,广度优先搜索遍历的过程是：首先访问初始点v,i,接着访问v,i,的所有未被访问过的邻接点v,i1,v,i2,v,it,然后再按照v,i1,v,i2,v,it,的次序，访问每一个顶点的所有未被访问过的邻接点，依次类推，直到图中所有和初始点v,i,有路径相通的顶点都被访问过为止。,以邻接表为存储结构，用广度优先搜索遍历图时,需要使用一个队列，以类似于按层次遍历二叉树遍历图。对应的算法如下(其中，v是初始顶点编号)：,42,第6章 图 Graph,6.3.3,广度优先搜索遍历,void BFS(ALGraph*G,int v),ArcNode*p;int w,i;,int queueMAXV,front=0,rear=0;/*定义循环队列*/,int visitedMAXV;/*定义存放结点的访问标志的数组*/,for(i=0;in;i+)visitedi=0;/*访问标志数组初始化*/,printf(%2d,v);/*输出被访问顶点的编号*/,visitedv=1;/*置已访问标记*/,rear=(rear+1)%MAXV;,queuerear=v;/*v进队*/,43,第6章 图 Graph,while(front!=rear)/*若队列不空时循环*/,front=(front+1)%MAXV;,w=queuefront;/*出队并赋给w*/,p=G-adjlistw.firstarc;/*找w的第一个的邻接点*/,while(p!=NULL),if(visitedp-adjvex=0),printf(“%2d”,p-adjvex);/*访问之*/,visitedp-adjvex=1;,rear=(rear+1)%MAXV;/*该顶点进队*/,queuerear=p-adjvex;,p=p-nextarc;/*找下一个邻接顶点*/,printf(n);,44,第6章 图 Graph,6.3.3,广度优先搜索遍历,例如，以上图的邻接表为例调用BFS()函数，假设初始顶点编号v=2，给出调用BFS()的执行过程，见教材。,45,第6章 图 Graph,6.3.4,非连通图的遍历,对于无向图来说，若无向图是连通图，则一次遍历能够访问到图中的所有顶点；,但若无向图是非连通图，则只能访问到初始点所在连通分量中的所有顶点，其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点，分别进行遍历，才能够访问到图中的所有顶点；,46,第6章 图 Graph,6.3.4,非连通图的遍历,对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点；否则不能访问到所有顶点，为此同样需要再选初始点，继续进行遍历，直到图中的所有顶点都被访问过为止。,47,第6章 图 Graph,6.3.4,非连通图的遍历,采用深度优先搜索遍历非连通无向图的算法如下：,DFS1(ALGraph*g),int i;,for(i=0;in;i+)/*遍历所有未访问过的顶点*/,if(visitedi=0),DFS(g,i);,48,第6章 图 Graph,6.3.4,非连通图的遍历,采用广度优先搜索遍历非连通无向图的算法如下,：,BFS1(ALGraph*g),int i;,for(i=0;in;i+)/*遍历所有未访问过的顶点*/,if(visitedi=0),BFS(g,i);,49,第6章 图 Graph,6.3.5,图的遍历应用,例 假设图G采用邻接表存储，设计一个算法，判断无向图G是否连通。若连通则返回1；否则返回0。,解：采用遍历方式判断无向图G是否连通。这里用深度优先遍历方法，先给visited数组（为全局变量）置初值0，然后从0顶点开始遍历该图。,在一次遍历之后，若所有顶点i的visitedi均为1，则该图是连通的；否则不连通。对应的算法如下：,50,第6章 图 Graph,6.3.5,图的遍历应用,int Connect(ALGraph*G)/*判断无向图G的连通性*/,int i,flag=1;,for(i=0;in;i+)/*visited数组置初值*/,visitedi=0;,DFS(G,0);/*调用DSF算法,从顶点0开始深度优先遍历*/,for(i=0;in;i+),if(visitedi=0),flag=0;,break;,return flag;,51,第6章 图 Graph,6.3.5,图的遍历应用,例 假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的长度为l的所有简单路径。,解：所谓简单路径是指路径上的顶点不重复。利用回溯的深度优先搜索方法。,从顶点u开始，进行深度优先搜索，在搜索过程中，需要把当前的搜索线路记录下来。为此设立一个数组path保存走过的路径，用d记录走过的路径长度。若当前扫描到的结点u等于v且路径长度为l时，表示找到了一条路径，则输出路径path。,对应的算法如下：,52,第6章 图 Graph,void PathAll(ALGraph*G,int u,int v,int l,int path,int d),/*d是到当前为止已走过的路径长度，调用时初值为-1*/,int m,i;ArcNode*p;visitedu=1;d+;/*路径长度增1*/,pathd=u;/*将当前顶点添加到路径中*/,if(u=v&d=l)/*输出一条路径*/,printf();,for(i=0;iadjlistu.firstarc;/*p指向u的第一条弧的弧头结点*/,while(p!=NULL),m=p-adjvex;/*m为u的邻接顶点*/,if(visitedm=0)/*若顶点未标记访问,则递归访问之*/,PathAll(G,m,v,l,path,d);,p=p-nextarc/*找u的下一个邻接顶点*/,visitedu=0;,/*恢复环境*/,53,第6章 图 Graph,void main(),int pathMAXV,u=1,v=4,d=3,i,j;,MGraph g;,ALGraph*G;,g.n=5;g.e=6;,int AMAXVMAXV=0,1,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,1,0,1,0,0,1,1,0 ;,for(i=0;ig.n;i+)/*建立邻接矩阵*/,for(j=0;jg.n;j+),g.edgesij=Aij;,MatToList(g,G);,for(i=0;ig.n;i+)visitedi=0;,printf(图G:n);DispAdj(G);/*输出邻接表*/,printf(从%d到%d的所有长度为%d路径:n,u,v,d);,PathAll(G,u,v,d,path,-1);,printf(n);,54,第6章 图 Graph,程序执行结果如下：,图G:,0:1 3,1:0 2,2:1 3 4,3:0 2 4,4:2 3,从1到4的所有长度为3路径:,1 0 3 4,1 2 3 4,1,3,2,4,0,55,第6章 图 Graph,6.4,生成树和最小生成树,6.4.1,生成树的概念,6.4.2 无向图的连通分量和生成树,6.4.3 普里姆（Prim）算法,6.4.4 克鲁斯卡尔(Kruskal)算法,56,第6章 图 Graph,6.4.1,生成树的概念,一个连通图的,生成树,是一个极小连通子图，它含有图中全部顶点，但只有构成一棵树的(n-1)条边。,如果在一棵生成树上添加一条边，必定构成一个环：因为这条边使得它依附的那两个顶点之间有了第二条路径。一棵有n个顶点的生成树(连通无回路图)有且仅有(n-1)条边，如果一个图有n个顶点和小于(n-1)条边，则是非连通图。如果它多于(n-1)条边，则一定有回路。但是，有(n-1)条边的图不一定都是生成树。,57,第6章 图 Graph,6.4.1,生成树的概念,对于一个带权(假定每条边上的权均为大于零的实数)连通无向图G中的不同生成树，其每棵树的所有边上的权值之和也可能不同；图的所有生成树中具有边上的权值之和最小的树称为图的,最小生成树,。,按照生成树的定义，n个顶点的连通图的生成树有n个顶点、n-1条边。因此，构造最小生成树的准则有三条：,(1)必须只使用该图中的边来构造最小生成树；,(2)必须使用且仅使用n-1条边来连接图中的n个顶点；,(3)不能使用产生回路的边。,58,第6章 图 Graph,6.4.2,无向图的连通分量和生成树,在对无向图进行遍历时，对于连通图，仅需调用遍历过程(DFS或BFS)一次，从图中任一顶点出发，便可以遍历图中的各个顶点。对非连通图，则需多次调用遍历过程，每次调用得到的顶点集连同相关的边就构成图的一个连通分量。,设G=(V,E)为连通图，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T和B，其中T是遍历图过程中走过的边的集合，B是剩余的边的集合：TB=,TB=E(G)。显然，G=(V,T)是G的极小连通子图，即G是G的一棵,生成树,。,59,第6章 图 Graph,6.4.2,无向图的连通分量和生成树,由深度优先遍历得到的生成树称为,深度优先生成树,；由广度优先遍历得到的生成树称为,广度优先生成树,。这样的生成树是由遍历时访问过的n个顶点和遍历时经历的n-1条边组成。,对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树，各个连通分量的生成树组成非连通图的生成森林。,60,第6章 图 Graph,V,0,V,1,V,2,V,3,V,4,V,5,V,6,V,7,V,8,V,9,V,10,3,2,1,5,4,0,3,6,5,7,2,0,1,1,2,7,9,8,10,6,3,6,6,7,0,2,61,第6章 图 Graph,6.4.3,普里姆（Prim）算法,普里姆(Prim)算法是一种构造性算法。,假设G=(V,E)是一个具有n个顶点的带权连通无向图，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造最小生成树T的步骤如下：,62,第6章 图 Graph,6.4.3,普里姆（Prim）算法,(1)初始化U=v,0,。v,0,到其他顶点的所有边为候选边；,(2)重复以下步骤n-1次，使得其他n-1个顶点被加入到U中：,从候选边中挑选权值最小的边输出，设该边在V-U中的顶点是v，将v加入U中，删除和v关联的边；,考察当前V-U中的所有顶点v,i,，修改候选边：若(v,v,i,)的权值小于原来和v,i,关联的候选边，则用(v,v,i,)取代后者作为候选边。,63,第6章 图 Graph,6.4.3,普里姆（Prim）算法,普里姆算法求解最小生成树的过程,64,第6章 图 Graph,6.4.4,克鲁斯卡尔（Kruskal）算法,克鲁斯卡尔(Kruskal)算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。假设G=(V,E)是一个具有n个顶点的带权连通无向图，T=(U,TE)是G的最小生成树，则构造最小生成树的步骤如下：,(1)置U的初值等于V(即包含有G中的全部顶点)，TE的初值为空集(即图T中每一个顶点都构成一个分量)。,(2)将图G中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T形成回路，则加入TE；否则舍弃，直到TE中包含(n-1)条边为止。,65,第6章 图 Graph,6.4.4,克鲁斯卡尔（Kruskal）算法,克鲁斯卡尔算法求解最小生成树的过程,66,第6章 图 Graph,6.5,最短路径,6.5.1,路径的概念,6.5.2 从一个顶点到其余各顶点的最短路径,6.5.3 每对顶点之间的最短路径,67,第6章 图 Graph,6.5.1,路径的概念,在一个无权的图中，若从一顶点到另一顶点存在着一条路径，则称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减1。,由于从一顶点到另一顶点可能存在着多条路径，一条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做,最短路径,，其路径长度叫做,最短路径长度,或,最短距离,。,68,第6章 图 Graph,6.5.1,路径的概念,对于带权的图，考虑路径上各边上的权值，则通常把一条路径上所经边的权值之和定义为该路径的,路径长度,或称,带权路径长度,。,从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为,最短路径,，其路径长度（权值之和）称为,最短路径长度,或者,最短距离,。,69,第6章 图 Graph,6.5.2,从一个顶点到其余各顶点的最短路径,问题：给定一个带权有向图G与源点v，求从v到G中其他顶点的最短路径，并限定各边上的权值大于或等于0。,70,第6章 图 Graph,6.5.2,从一个顶点到其余各顶点的最短路径,采用,狄克斯特拉(Dijkstra)算法,求解,基本思想是：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组：,第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径v,v,k,，就将v,k,加入到集合S中，直到全部顶点都加入到S中，算法就结束了）,第二组为其余未确定最短路径的顶点集合（用U表示）。,71,第6章 图 Graph,6.5.2,从一个顶点到其余各顶点的最短路径,按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。,此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。,72,第6章 图 Graph,6.5.2,从一个顶点到其余各顶点的最短路径,狄克斯特拉算法的具体步骤如下：,(1)初始时，S只包含源点，即S=v，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或（若u不是v的出边邻接点）。,(2)从U中选取一个距离v最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）。,(3)以k为新考虑的中间点，修改U中各顶点的距离：若从源点v到顶点u(uU)的距离(经过顶点k)比原来距离(不经过顶点k)短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。,(4)重复步骤(2)和(3)直到所有顶点都包含在S中。,73,第6章 图 Graph,6.5.2,从一个顶点到其余各顶点的最短路径,V到j的最小距离MIN(c,vk,+w,kj,c,vj,),74,第6章 图 Graph,6.5.2,从一个顶点到其余各顶点的最短路径,S U dist path,0 1 2 3 4 5 6,0 1 2 3 4 5 6,0 1,2,3,4,5,6 0,4,6,6,0,0,0,0,-1,-1,-1,0,1,2,3,4,5,6 0,4,5,6,11,0,0,1,0,1,-1,-1,0,1,2,3,4,5,6 0,4,5,6,11,9,0,0,1,0,1,2,-1,0,1,2,3,4,5,6 0,4,5,6,11,9,0,0,1,0,1,2,-1,0,1,2,3,5,4,6 0,4,5,6,10,9,17,0,0,1,0,5,2,5,0,1,2,3,5,4,6 0,4,5,6,10,9,16,0,0,1,0,5,2,4,0,1,2,3,5,4,6,0,4,5,6,10,9,16 0,0,1,0,5,2,4,75,第6章 图 Graph,狄克斯特拉算法如下(n为图G的顶点数,v0为源点编号)：,void Dijkstra(int costMAXV,int n,int v0),int distMAXV,pathMAXV;int sMAXV;int mindis,i,j,u;,for(i=0;in;i+),disti=costv0i;/*距离初始化*/,si=0;/*s置空*/,if(costv0iINF)/*路径初始化*/,pathi=v0;,else,pathi=-1;,sv0=1;pathv0=0;/*源点编号v0放入s中*/,76,第6章 图 Graph,for(i=0;in;i+)/*循环直到所有顶点的最短路径都求出*/,mindis=INF;,u=-1;,for(j=0;jn;j+)/*选取不在s中且具有最小距离的顶点u*/,if(sj=0&distjmindis),u=j;mindis=distj;,su=1;/*顶点u加入s中*/,for(j=0;jn;j+)/*修改不在s中的顶点的距离*/,if(sj=0),if(costujINF&distu+costujdistj),distj=distu+costuj;pathj=u;,Dispath(dist,path,s,n,v0);/*输出最短路径*/,77,第6章 图 Graph,void Ppath(int path,int i,int v0),/*前向递归查找路径上的顶点*/,int k;,k=pathi;,if(k=v0)return;/*找到了起点则返回*/,Ppath(path,k,v0);/*找k顶点的前一个顶点*/,printf(%d,k);/*输出k顶点*/,78,第6章 图 Graph,void Dispath(int dist,int path,int s,int n,int v0),int i;,for(i=0;in;i+),if(si=1),printf(“从%d到%d的最短路径长度为:,%dt路径为:,v0,i,disti);,printf(%d,v0);/*输出路径上的起点*/,Ppath(path,i,v0);/*输出路径上的中间点*/,printf(%dn,i);/*输出路径上的终点*/,else printf(从%d到%d不存在路径n,v0,i);,79,第6章 图 Graph,6.5.3,每对顶点之间的最短路径,问题：对于一个各边权值均大于零的有向图，对每一对顶点v,i,v,j,，求出v,i,与v,j,之间的最短路径和最短路径长度。,可以通过以每个顶点作为源点循环求出每对顶点之间的最短路径。除此之外，弗洛伊德(Floyd)算法也可用于求两顶点之间最短路径。,80,第6章 图 Graph,6.5.3,每对顶点之间的最短路径,假设有向图G=(V,E)采用邻接矩阵cost存储，另外设置一个二维数组A用于存放当前顶点之间的最短路径长度，分量Aij表示当前顶点v,i,到顶点v,j,的最短路径长度。,弗洛伊德算法的基本思想是递推产生一个矩阵序列A,0,A,1,A,k,A,n,，其中A,k,ij表示从顶点v,i,到顶点v,j,的路径上所经过的顶点编号不大于k的最短路径长度。,81,第6章 图 Graph,6.5.3,每对顶点之间的最短路径,初始时,有A,-1,ij=costij。当求从顶点v,i,到顶点v,j,的路径上所经过的顶点编号不大于k+1的最短路径长度时，要分两种情况考虑：,一种情况是该路径不经过顶点编号为k+1的顶点,此时该路径长度与从顶点v,i,到顶点v,j,的路径上所经过的顶点编号不大于k的最短路径长度相同；,另一种情况是从顶点v,i,到顶点v,j,的最短路径上经过编号为k+1的顶点。,82,第6章 图 Graph,6.5.3,每对顶点之间的最短路径,A,k+1,i,j=MIN(A,k,i,j,A,k,i,k+1+A,k,k+1,j,83,第6章 图 Graph,6.5.3,每对顶点之间的最短路径,那么，该路径可分为两段:,(1)从顶点v,i,到顶点v,k+1,的最短路径;,(2)从顶点v,k+1,到顶点v,j,的最短路径。,此时最短路径长度等于这两段路径长度之和。这两种情况中的较小值，就是所要求的从顶点v,i,到顶点v,j,的路径