《数据结构——图.ppt》由会员分享，可在线阅读，更多相关《数据结构——图.ppt（133页珍藏版）》请在课桌文档上搜索。
1、第章图,图的基本概念,图的基本运算,生成树与最小生成树,拓扑排序,图的基本存储结构,最短路径,关键路径,图的遍历,8.1 图的基本概念,一、图的定义,图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，它可以形式化地表示为：图（V，E）其中V=x|x某个数据对象集，它是顶点的有穷非空集合；E=（x，y）|x，yV或E=|x，yV且P（x，y），它是顶点之间关系的有穷集合，也叫做边集合，P（x，y）表示从x到y的一条单向通路。,图的应用举例例1 交通图（公路、铁路）顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示；,例2 电路
2、图 顶点：元件 边：连接元件之间的线路,例3 通讯线路图 顶点：地点 边：地点间的连线,例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系,通常，也将图G的顶点集和边集分别记为V（G）和E（G）。E（G）可以是空集，若E（G）为空，则图G只有顶点而没有边。,若图G中的每条边都是有方向的，则称G为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对表示一条由vi到vj的有向边。有向边又称为弧，弧的始点称为弧尾，弧的终点称为弧头。若图G中的每条边都是没有方向的，则称G为无向图。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。,
3、图8-1,图8.1（a）表示的是有向图G1，该图的顶点集和边集分别为：V（G1）=v1，v2，v3，v4E（G1）=，,例,有序对：用以为vi起点、以vj为终点的有向线段表示，称为有向边或弧；,例：图8-1,图8.1（b）表示的是无向图G2，该图的顶点集和边集分别为：V（G2）=v1，v2，v3，v4，v5E（G2）=（vl，v2），（v1，v3），（v1，v4），（v2，v3），（v2，v5），（v4，v5）,无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；,在以后的讨论中，我们约定：（1）一条边中涉及的两个顶点必须不相同，即：若（vi，vj）或是E（G）中的一条边，则要求
4、vivj；（2）一对顶点间不能有相同方向的两条有向边；（3）一对顶点间不能有两条无向边，即只讨论简单的图。,若用n表示图中顶点的数目，用e表示图中边的数目，按照上述规定，容易得到下述结论：对于一个具有n个顶点的无向图，其边数e小于等于n（n-1）/2，边数恰好等于n（n-1）/2的无向图称为无向完全图；对于一个具有n个顶点的有向图，其边数e小于等于n（n-1），边数恰好等于n（n-1）的有向图称为有向完全图。也就是说完全图具有最多的边数，任意一对顶点间均有边相连。,二、完全图,例：图8-2,图8.2所示的G3与G4分别是具有4个顶点的无向完全图和有向完全图。图G3共有4个顶点6条边；图G4共有
5、4个顶点12条边。,若（vi，vj）是一条无向边，则称顶点vi和vj互为邻接点。,若是一条有向边，则称vi邻接到vj，vj邻接于vi，并称有向边关联于vi与vj，或称有向边与顶点vi和vj相关联。,三、度、入度、出度,在图中，一个顶点的度就是与该顶点相关联的边的数目，顶点v的度记为D（v）。例如在图8.2（a）所示的无向图G3中，各顶点的度均为3。若G为有向图，则把以顶点v为终点的边的数目称为顶点v的入度，记为ID（v）；把以顶点v为始点的边的数目称为v的出度，记为OD（v），有向图中顶点的度数等于顶点的入度与出度之和，即D（v）=ID（v）+OD（v）。,无论有向图还是无向图，图中的每条边均
6、关联于两个顶点，因此，顶点数n、边数e和度数之间有如下关系：,e=,.（式8-1）,四、子图,给定两个图Gi和Gj，其中Gi=（Vi，Ei），Gj=（Vj，Ej），若满足ViVj，EiEj，则称Gi是Gj的子图。,v1,v1,子图示例,（a）无向图G3的部分子图,（b）有向图G4的部分子图,五、路径,无向图G中若存在着一个顶点序列v、v1、v2、vm、u，且（v，v1）、（v1，v2）、（vm，u）均属于E（G），则称该顶点序列为顶点v到顶点u的一条路径，相应地，顶点序列u、vm、vm-1、v1、v是顶点u到顶点v的一条路径。如果G是有向图，路径也是有向的，它由E（G）中的有向边、组成。路径长
7、度是该路径上边或弧的数目。,如果一条路径上除了起点v和终点u相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同（v=u）的简单路径称为简单回路或简单环。,六、连通图与强连通图,在无向图G中，若从顶点vi到顶点vj有路径，则称vi与vj是连通的。若V（G）中任意两个不同的顶点vi和vj都连通（即有路径），则称G为连通图。例如，图8.1（b）所示的无向图G2、图8.2（a）所示的无向图G3是都是连通图。,无向图G的极大连通子图称为G的连通分量。根据连通分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。,例：非连通图及其连通分量示例,（a）非连通图G5（b）
8、G5的两个连通分量H1和H2,在有向图G中，若对于V（G）中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。,有向图的极大强连通子图称为G的强连通分量。根据强连通图的定义，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分量。例如，图8.2（b）所示的有向图G4是一个具有4个顶点的强连通图，图8.5（a）所示的有向图G6不是强连通图（v2、v3、v4没有到达v1的路径），它的两个强连通分量H3与H4如图8.5（b）所示。,七、网络,有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫权。,权可以表示两个顶点之间的距离、耗费等具有
9、某种意义的数。若将图的每条边都赋上一个权，则称这种带权图为网络。,作业：,8.1 对于无向图8.29，试给出（1）图中每个顶点的度；（2）该图的邻接矩阵；（4）该图的连通分量。,v0,v3,v4,v2,v1,v5,v6,图8.29 无向图,8.2 给定有向图8.30，试给出（1）顶点D的入度与出度；（2）该图的出边表与入边表；（3）该图的强连通分量。,A,B,C,D,E,图8.30 有向图,8.2 图的基本运算,图是一种复杂数据结构，由图的定义及图的一组基本操作构成了图的抽象数据类型。ADT Graph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=|v，wV且P（v
10、，w），P（v，w）定义了边（或弧）（v，w）的信息,图的基本操作如下：（1）creatgraph（&g）创建一个图的存储结构。（2）insertvertex（&g，v）在图g中增加一个顶点v。（3）deletevertex（&g，v）在图g中删除顶点v及所有和顶点v相关联的边或弧。（4）insertedge（&g，v，u）在图g中增加一条从顶点v到顶点u的边或弧。（5）deleteedge（&g，v，u）在图g中删除一条从顶点v到顶点u的边或弧。,（6）trave（g）遍历图g。（7）locatevertex（g，v）求顶点v在图g中的位序。（8）fiirstvertex（g，v）求图g中顶
11、点v的第一个邻接点。（9）degree（g，v）求图g中顶点v的度数。（10）nextvertex（g，v，w）求图g中与顶点v相邻接的顶点w的下一个邻接点。即求图g中顶点v的某个邻接点，它的存储顺序排在邻接点w的存储位置之后。ADT Graph,8.3图的基本存储结构,图的存储结构至少要保存两类信息：1)顶点的数据 2)顶点间的关系,约定:G=是图,V=v0,v1,v2,vn-1,设顶点的 角标为它的编号,8.3.1邻接矩阵及其实现,给定图G=（V，E），其中V（G）=v0，vi，vn-1，G的邻接矩阵（Adacency Matrix）是具有如下性质的n阶方阵：,无向图的邻接矩阵是对称的，有
12、向图的邻接矩阵可能是不对称的。,一、非网络的邻接矩阵,图的邻接矩阵示例,用邻接矩阵表示图，很容易判定任意两个顶点之间是否有边相连，并求得各个顶点的度数。对于无向图，顶点vi的度数是邻接矩阵中第i行或第i列值为1的元素个数，即：,D（vi）=（8-2）,对于有向图，邻接矩阵中第i行值为1的元素个数为顶点vi的出度，第i列值为1的元素的个数为顶点vi的入度，即：,OD（vi）=;ID（vi）=（8-3）,二、网络的邻接矩阵,当G=（V，E）是一个网络时，G的邻接矩阵是具有如下性质的n阶方阵：,其中Wij表示边上的权值；表示一个计算机允许的、大于所有边上权值的数。,网络的邻接矩阵示例,邻接矩阵存储结
13、构,#define FINITY 5000/*此处用5000代表无穷大*/#define m 20/*最大顶点数*/typedef char vertextype;/*顶点值类型*/typedef int edgetype;/*权值类型*/typedef struct vertextype vexsm;/*顶点信息域*/edgetype edgesmm;/*邻接矩阵*/int n,e;/*图中顶点总数与边数*/mgraph;/*邻接矩阵表示的图类型*/,文件名:mgraph.h,/*/*图的邻接矩阵创建算法*/*文件名：c_ljjz.c 函数名：creatmgraph1()*/*/#inclu
14、de#include mgraph.hvoid creatmgraph1(mgraph*g)int i,j,k,w;/*建立有向网络的邻接矩阵存储结构*/printf(please input n and e:n);scanf(%d%d,for(i=0;in;i+)/*输入图中的顶点值*/g-vexsi=getchar();for(i=0;in;i+)/*初始化邻接矩阵*/for(j=0;jn;j+)if(i=j)g-edgesij=0;else g-edgesij=FINITY;printf(please input edges:n);for(k=0;ke;k+)/*输入网络中的边*/sca
15、nf(%d%d%d,即可*/,说明:当建立有向网时，边信息以三元组（i，j，w）的形式输入，i、j分别表示两顶点的序号，w表示边上的权。对于每一条输入的边信息（i，j，w），只需将g-edgesij赋值为w。算法8.5中用到的creatmgraph2()是用于建立无向网络的函数，它与creatmgraph1()的区别在于对每一条输入的边信息（i，j，w），需同时将g-edgesij 和g-edgesji赋值为w。当建立非网络的存储结构时，所有的边信息只需按二元组（i，j）的形式输入。,8.3.2邻接表及其实现,用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。
16、一个含有n个顶点的图，如果其边数比n2少得多，那么它的邻接矩阵就会有很多空元素，浪费了存储空间。,无向图的邻接表 对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表。单链表中的每个结点至少包含两个域，一个为邻接点域（adjvex），它指示与顶点vi邻接的顶点在图中的位序，另一个为链域（next），它指示与顶点vi邻接的下一个结点。,为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结构。,表头结点结构,边结点结构,对于无向图，vi
17、的邻接表中每个表结点都对应于与vi相关联的一条边；对于有向图来说，如果每一顶点vi的邻接表中每个表结点都存储以vi的为始点射出的一条边，则称这种表为有向图的出边表（有向图的邻接表），反之，若每一顶点vi的邻接表中每个表结点都对应于以vi为终点的边（即射入vi的边），则称这种表为有向图的入边表（又称逆邻接表）。,在无向图的邻接表中，顶点vi的度为第i个链表中结点的个数；而在有向图的出边表中，第i个链表中的结点个数是顶点vi的出度；为了求入度，必须对整个邻接表扫描一遍，所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。,V0的度为3,V0的出度为1，入度为2,邻接表的存储结构,/*/*邻接
18、表存储结构 文件名：adjgraph.h*/*/#define m 20/*预定义图的最大顶点数*/typedef char datatype;/*顶点信息数据类型*/typedef struct node/*边表结点*/int adjvex;/*邻接点*/struct node*next;edgenode;,边结点结构,typedef struct vnode/*头结点类型*/datatype vertex;/*顶点信息*/edgenode*firstedge;/*邻接链表头指针*/vertexnode;typedef struct/*邻接表类型*/vertexnode adjlist m;
19、/*存放头结点的顺序表*/int n,e;/*图的顶点数与边数*/adjgraph;,头结点结构,/*/*无向图的邻接表创建算法*/*文件名c_ljb.c 函数名：createadjgraph()*/*/void createadjgraph(adjgraph*g)int i,j,k;edgenode*s;printf(Please input n and e:n);scanf(%d%d,for(i=0;in;i+)scanf(“%c”,/*将新结点*s插入顶点vi的边表头部*/,s=(edgenode*)malloc(sizeof(edgenode);s-adjvex=i;/*邻接点序号为i
20、*/s-next=g-adjlistj.firstedge;g-adjlistj.firstedge=s;/*将新结点*s插入顶点vj的边表头部*/算法8.2 建立无向图的邻接表算法,说明：一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为在邻接表结构中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。,4 5ABCD0 1 0 2 0 3 1 2 2 3,例:若需建立下图所示的无向图邻接表存储结构,则在执行程序c_ljb.c时如果输入的信息为：,则将建立如下的邻接表存储结构。A 3-2-1B 2-0C 3-1-0D 2-0,8.3.3邻接多重表,在邻接多重表中，每一条边
21、只有一个边结点。为有关边的处理提供了方便。边结点的结构,其中，mark 是记录是否处理过的标记；vexi和vexj是依附于该边的两顶点位置。lniki域是链接指针，指向下一条依附于顶点vexi的边；linkj也是链接指针，指向下一条依附于顶点vexj的边。需要时还可设置一个存放与该边相关的权值的域 cost。,顶点结点的结构 存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中，vertex 存放与该顶点相关的信息，firstedge 是指示第一条依附于该顶点的边的指针。在邻接多重表中,所有依附于同一个顶点的边都链接在同一个单链表中。从顶点 i 出发,可以循链找到所有依附于
22、该顶点的边，也可以找到它的所有邻接顶点。,无向网络的邻接多重表示例,其中边表结点增加了一个存储权值的数据域。,8.4 图的遍历,图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组 visitn作为对顶点的标记，当顶点vi未被访问，visiti值为0；当vi已被访问，则visiti值为1。,有两种遍历方法（它们对无向图，有向图都适用）深度优先遍历 广度优先遍历,8.4.1深度优先遍历,从图中某顶点v出发：1）访问顶点v；2）依次从v的未被访问的邻接
23、点出发，继续对图进行深度优先遍历；,对于给定的图G=（V，E），首先将V中每一个顶点都标记为未被访问，然后，选取一个源点vV，将v标记为已被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，如果从v出发有路的顶点都已被访问过，则从v的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，并从这个顶点开始做新的搜索。上述过程一直进行到V中所有顶点都已被访问过为止。,例,序列1：V0,V1,V3,V7,V4,V2,V5,V6,深度优先遍历过程：,由于没有规定访问邻接点的顺序
24、，深度优先序列不是唯一的,序列2：V0,V1,V4,V7,V3,V2,V5,V6,c0,c1,c3,c2,c4,c5,DFS序列：c0 c1 c3 c4 c5 c2,但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果将是确定的。,采用邻接表存储结构的深度优先遍历算法实现：,/*/*图的深度优先遍历算法*/*文件名：dfs.c 函数名：dfs()、dfstraverse()*/*/int visitedm;void dfs(adjgraph g,int i)/*以vi为出发点深度优先遍历顶点vi所在的连通分量*/edgenode*p;printf(visit vertex:%c n
25、,g.adjlisti.vertex);/*访问顶点i*/visitedi=1;,p=g.adjlisti.firstedge;while(p)/*从p的邻接点出发进行深度优先搜索*/if(!visitedp-adjvex)dfs(g,p-adjvex);/*递归*/p=p-next;,void dfstraverse(adjgraph g)/*深度优先遍历图g*/int i;for(i=0;ig.n;i+)visitedi=0;/*初始化标志数组*/for(i=0;ig.n;i+)if(!visitedi)/*vi未访问过*/dfs(g,i);算法8.3 图的深度优先遍历算法（邻接表表示法）
26、,算法分析：对于具有n个顶点和e条边的无向图或有向图，遍历算法dfstraverse对图中每个顶点至多调用一次dfs。从dfstraverse中调用dfs或dfs内部递归调用自己的最大次数为n。当访问某顶点vi时，dfs的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接表表示图时，需搜索第i个边表上的所有结点，因此，对所有n个顶点访问，在邻接表上需将边表中所有O（e）个结点检查一遍。所以，dfstraverse算法的时间复杂度为O（n+e）。,8.4.2广度优先遍历,图中某未访问过的顶点vi出发：1）访问顶点vi；2）访问 vi 的所有未被访问的邻接点w1,w2,wk；3）依次从这些邻接
27、点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；,求图G 的以V0起点的的广度优先序列,V0,V1,V2,V3,V4,V5,V6,V7,例,从C0出发的BFS序列为：,由于没有规定访问邻接点的顺序，广度优先序列不是唯一的,c0 c1 c2 c3 c4 c5,从图中某顶点vi出发：1）访问顶点vi；（容易实现）2）访问vi 的所有未被访问的邻接点w1,w2,wk；3）依次从这些邻接点（在步骤 2）访问的顶点）出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；为实现 3），需要保存在步骤(2）中访问的顶点，而且访问
28、这些顶点邻接点的顺序为：先保存的顶点，其邻接点先被访问。,广度优先算法：,在广度优先遍历算法中，需设置一队列Q，保存已访问的顶点，并控制遍历顶点的顺序。,QUEUE,V0,V1,V2,V3,V4,V5,V6,V7,V1,V2,V3,V0,V4,V5,V6,V7,数据结构：1）全局标志数组int visitedm;/*全局标志向量*/2）邻接表存储结构,/*/*图的广度优先遍历算法*/*程序名bfs.c 函数名bfs()、bfstraverse()*/*/,void bfs(adjgraph g,int i)int j;/*从顶点i出发广度优先遍历顶点i所在的连通分量*/edgenode*p;i
29、nt queue20,head,tail;/*FIFO队列*/head=-1;tail=-1;/*初始化空队列*/printf(%c,g.adjlisti.vertex);/*访问源点v*/visitedi=1;queue+tail=i;/*被访问结点进队*/,while(tailhead)/*当队列非空时，执行下列循环体*/j=queue+head;/*出队*/p=g.adjlistj.firstedge;while(p)/*广度优先搜索邻接表*/if(visitedp-adjvex=0)printf(%c,g.adjlistp-adjvex.vertex);queue+tail=p-adj
30、vex;visitedp-adjvex=1;p=p-next;,int bfstraverse(adjgraph g,datatype v)int i,count=0;/*广度优先遍历图g*/for(i=0;ig.n;i+)visitedi=0;/*初始化标志数组*/i=loc(g,v);/*寻找顶点v在邻接表中的位序*/if(i!=-1)count+;/*连通分量个数加1*/bfs(g,i);for(i=0;ig.n;i+)if(!visitedi)/*vi未访问过*/printf(n);count+;/*连通分量个数加1*/,bfs(g,i);/*从顶点i出发广度优先遍历图g*/retur
31、n count;/*返回无向图g中连通分量的个数*/算法8.4 图的广度优先遍历算法（邻接表表示法）,算法的时间复杂度与深度优先算法相同。,作业：,8.4 图8.31是某个无向图的邻接表，请（1）画出此图；（2）写出从顶点A开始的DFS遍历结果。（3）写出从顶点A开始的BFS遍历结果。,8.5生成树与最小生成树,对于一个无向的连通图G=（V，E），设G是它的一个子图，如果G中包含了G中所有的顶点（即V（G）=V（G）且G是无回路的连通图，则称G为G一棵的生成树。,深度优先生成树：按深度优先遍历生成的生成树广度优先生成树：按广度优先遍历生成的生成树,有向图的生成树,c0,c1,c3,c2,c4,
32、c5,c6,c0,c1,c3,c2,c4,c5,c6,c0,c1,c3,c2,c4,c5,c6,（a）以c0为根的有向图（b）DFS生成树（c）BFS生成树,非连通图的生成森林,V0,V1,V3,V4,V2,V6,V8,V7,V5,V9,V0,V1,V3,V4,V2,V6,V8,V7,V5,V9,V0,V1,V3,V4,V2,V8,V7,V9,V6,V5,（a）不连通的无向图G12（b）图G12的一个DFS生成森林,（c）图G12的一个BFS生成森林,8.5.1最小生成树的定义,若有一个连通的无向图 G，有 n 个顶点，并且它的边是有权值的。在 G 上构造生成树 G,使这n-1 条边的权值之和
33、在所有的生成树中最小。,例,要在 n 个城市间建立交通网，要考虑的问题如何在保证 n 点连通的前题下最节省经费?,上述问题即要使得生成树各边权值之各最小，即：,构造最小生成树的准则：必须只使用该网络中的边来构造最小生成树；必须使用且仅使用n-1条边来联接网络中的n个顶点；不能使用产生回路的边。,假设G=（V，E）是一个连通网，U是顶点集V的一个非空真子集，若（u，v）是满足uU，vV-U的边（称这种边为两栖边）且（u，v）在所有的两栖边中具有最小的权值（此时，称（u，v）为最小两栖边），则必存在一棵包含边（u，v）的最小生成树。,MST性质：,证明：,设（u,v）是连接U与（V-U）之间所有边
34、中的最小代价边（最小两栖边）。反证时假设G中的任何一棵最小生成树都不含此最小两栖边。设T是连通网上的一棵最小生成树，当将（u,v）加入到T中时，由生成树的定义，T中必存在一条包含（u,v）的回路。另一方面，由于T是生成树，则在T上必存在另一条边（u,v），其中u U,v V-,U,且u和u之间，v和v之间均有路径相通，删去边（u,v），便可消除上述回路，同时得到另一棵生成树T。因为（u,v）的代价不高于（u,v），则T的代价亦不高于T，T是包含（u,v）的一棵最小生成树。由此和假设矛盾。,普里姆算法的基本思想：,8.5.2最小生成树的普里姆算法,(Prim)算法和(Kruskal)算法是两个利
35、用MST性质构造最小生成树的算法。,从连通网络 G=V,E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。,Prim算法的基本步骤如下：（1）初始化：U=u0，TREE=;（2）如果U=V（G），则输出最小生成树T，并结束算法；（3）在所有两栖边中找一条权最小的边（u，v）（若候选两栖边中的最小边不止一条，可任选其中的一条），将边（u，v）加入到边集TREE中
36、，并将顶点v并入集合U中。（4）由于新顶点的加入，U的状态发生变化，需要对U与V-U之间的两栖边进行调整。（5）转步骤（2）,Prim算法实现：,1、连通图用邻接矩阵net表示：,2、边tree（生成树）edge treen-1,typedef struct edgedata int beg,en;/*beg,en是结点序号*/int length;/*边长*/edge;,(a)初始态,K=0 m=1,K=0,(b)最小两栖边（0，1）,Prim算法构造最小生成树的过程,K=1,(c)最小两栖边（0，3）,K=2,(d)最小两栖边（1，5）,K=3,(e)最小两栖边（1，2）,(f)tree中
37、存储了最小生成树的边,算法关键一步：求第k条轻边，将其加入tree中,1）求当前最小两栖边及应添加的点v,min=treek.length;s=k;for(j=k+1;j=g.n-2;j+)if(treej.lengthmin)min=treej.length;s=j;v=trees.en;/*入选顶点为v*/,2）通过交换，将当前轻边加入tree中,x=trees;trees=treek;treek=x;,3）调整各剩余点对应的最小两栖边（由v加入引起）,for(j=k+1;j=g.n-2;j+)d=g.edgesvtreej.en;if(dtreej.length)treej.length
38、=d;treej.beg=v;,算法总体控制：,1）初始化：建立初始入选点，并初始化生成树边集tree。,for(v=1;v=g.n-1;v+)treev-1.beg=0;/*此处从顶点v0开始求最小生成树*/treev-1.en=v;treev-1.length=g.edges0v;,2）依次求当前最小两栖边，并将其加入tree,for(k=0;k=g.n-3;k+)执行关键一步,一般来讲，由于普里姆算法的时间复杂度为O(n2)，则适于稠密图。,程序演示：prim.c,8.5.3最小生成树的克鲁斯卡尔算法,Kruskal算法基本思想：,为使生成树上边的权值之和最小，显然，其中每一条边的权值应
39、该尽可能地小。克鲁斯卡尔算法的做法就是：先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。,克鲁斯卡尔算法需对e条边按权值进行排序，其时间复杂度为O(eloge)，则适于稀疏图。,算法：,（1）初始化，TV=v0，v1，vn，TE=；（2）如果TE具有n-1条边，则输出最小生成树T，并结束算法。（3）在有序的E（G）边表序列中，从当前位置向后寻找满足下面条件的一条边（u，v）：使得u在一个连通分量上，v在另一个连通分量上，即（u，v）是满足此条件权值最小的边，将其加入到T中，合并u与v所在的两个连通分
40、量为一个连通分量。（4）转（2）,Kruskal算法动态演示：,1,5,4,2,3,Kruskal算法构造最小生成树的过程,/*/*kruskal求解最小生成树算法*/*文件名kruskal.c 函数名kruskal()*/*/void kruskal(edge adjlist,edge tree,int cnvx,int n)int v=0,j,k;for(j=0;jn;j+)cnvxj=j;/*设置每一个顶点的连通分量*/for(k=0;kn-1;k+)/*树中共有n-1条边*/while(cnvxadjlistv.beg=cnvxadjlistv.en)v+;/*找到属于两个连通分量权最
41、小的边*/,treek=adjlistv;/*将边v加入到生成树中*/for(j=0;jn;j+)/*两个连通分量合并为一个连通分量*/if(cnvxj=cnvxadjlistv.en)cnvxj=cnvxadjlistv.beg;v+;printf(最小生成树是：n);for(j=0;jn-1;j+)printf(%3d%3d%6dn,treej.beg,treej.en,treej.length);算法8.6 Kruskal求解最小生成树,8.6最短路径,问题的提出：交通咨询系统、通讯网、计算机网络常要寻找两结点间最短路径；交通咨询系统：A 到 B 最短路径；计算机网络：发送Email节省
42、费用 A到B沿最短路径传送；路径长度：路径上边数 路径上边的权值之和最短路径：两结点间权值之和最小的路径；,A,B,D,C,F,E,2,4,15,28,8,18,10,13,始点 终点 最短路径 路径长度A B（A，C，B）19 C（A，C）4 D（A，C，F，D）25 E（A，C，B，E）29 F（A，C，F）12,4,如何求从某源点到其余各点的最短路径？,本节介绍求最短路径的两个算法 求从某个源点到其他各顶点的最短路径（单源最短路径）。求每一对顶点之间的最短路径。,8.6.1单源最短路径,单源最短路径问题是指：对于给定的有向网G=（V，E），求源点v0到其它顶点的最短路径。,Dijkstr
43、a提出了一个按路径长度递增的顺序逐步产生最短路径的方法，称为Dijkstra算法。,Dijkstra算法的基本思想：把图中所有顶点分成两组，第一组包括已确定最短路径的顶点，初始时只含有一个源点，记为集合S；第二组包括尚未确定最短路径的顶点，记为V-S。按最短路径长度递增的顺序逐个把V-S中的顶点加到S中去，直至从v0出发可以到达的所有顶点都包括到S中。在这个过程中，总保持从v0到第一组（S）各顶点的最短路径都不大于从v0到第二组（V-S）的任何顶点的最短路径长度，第二组的顶点对应的距离值是从v0到此顶点的只包括第一组（S）的顶点为中间顶点的最短路径长度。对于S中任意一点j，v0到j的路径长度皆
44、小于v0到（V-S）中任意一点的路径长度。,引入一个辅助数组d。它的每一个分量di表示当前找到的从源点v0到顶点vi 的最短路径的长度。初始状态：若从源点v0到顶点vi有边，则di为该边上的权值若从源点v0到顶点vi 没有边，则di为+。一般情况下，假设 S 是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从v0 出发，中间只经过S中的顶点便可到达的那些顶点vx(vx V-S)的路径中的一条。每次求得一条最短路径之后，其终点vk 加入集合S，然后对所有的vi V-S，修改其di值。,Dijkstra算法可描述如下：,）初始化：把图中的所有顶点分成两组；初始化源点到各点的距离向量。
45、,S：已确定最短路径的点集，初始S v0;,dj g.edgesv0j,j=1,2,n-1;/n为图中顶点个数,v0,s,v,v0,s,v,di min di,dv+edgesvi,对于每一个 i V-S;,）判断：若S=V,则算法结束，否则转）。,i,Dijkstra算法中各辅助数组的变化,如何从表中读取源点0到终点v的最短路径？例如顶点A到D的最短距离是d3=25,根据p3=5 p5=2 p2=0，反过来排列，得到路径0,2,5,3（即A、C、F、D）。,算法实现如下：,/*/*单源最短路径算法 文件名:dijkstra.c*/*函数名:spath_dij()、print_gpd()*/*
46、/#include c_ljjz.c/*引入邻接矩阵创建程序*/typedef enumFALSE,TRUE boolean;/*false为0,true为1*/typedef int distm;/*距离向量类型*/typedef int pathm;/*路径向量类型*/void spath_dij(mgraph g,int v0,path p,dist d)boolean finalm;int i,k,j,v,min,x;,/*第1步 初始化集合S与距离向量d*/for(v=0;vg.n;v+)finalv=FALSE;dv=g.edgesv0v;if(dvFINITY+k)/*找最小边及
47、对应的入选顶点*/,if(!finalk/*end for*/,void print_gpd(mgraph g,path p,dist d)/*输出有向图的最短路径*/int st20,i,pre,top=-1;/*定义栈st并初始化空栈*/for(i=0;i0)printf(%2d,sttop-);,void main()/*主程序*/mgraph g;/*有向图*/path p;/*路径向量*/dist d;/*最短路径向量*/int v0;creatmgraph1(/*输出V0到其它各点的路径信息及距离*/,8.6.2所有顶点对的最短路径,问题的提法：已知一个各边权值均大于0的带权有向图
48、，对每一对顶点 vi vj，要求求出vi 与vj之间的最短路径和最短路径长度。,解决这个问题显然可以利用单源最短路径算法，具体做法是依次把有向网G中的每个顶点作为源点，重复执行Dijkstra算法n次，即执行循环体：总的时间复杂度为O(n3)。for（v=0；vg.n；v+）spath_dij（g，v，p，d）；print_gpd（g，p，d）；,下面将介绍用弗洛伊德(Floyd)算法来实现此功能,时间复杂度仍为O(n3),但该方法比调用n次迪杰斯特拉方法更直观一些。,2 弗洛伊德算法的基本思想,弗洛伊德算法仍然使用前面定义的图的邻接矩阵edgesNN来存储带权有向图。算法的基本思想是:设置一
49、个NxN的矩阵ANN，其中除对角线的元素都等于0外，其它元素Aij的值表示顶点i到顶点j的最短路径长度，运算步骤为：开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为，此时,A ij=edgesij,以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：第一步，让所有边上加入中间顶点0，取Aij与Ai0+A0j中较小的值作Aij的值.,第二步，让所有边上加入中间顶点1，取Aij与Ai1+A1j中较小的值，完成后得到Aij，如此进行下去，当第n步完成后，得到 Aij,即为
50、我们所求结果,A ij表示顶点i到顶点j的最短距离。,下面给出Floyd的算法实现。/*/*Floyd 所有顶点对最短路径算法*/*文件名：floyd.c 函数名：floyd1()*/*/typedef int distmm;/*距离向量*/typedef int pathmm;/*路径向量*/void floyd1(mgraph g,path p,dist d)int i,j,k;for(i=0;ig.n;i+)/*初始化*/for(j=0;jg.n;j+)dij=g.edgesij;,if(i!=j 算法8.8 求网络中每一对顶点之间的最短路径,2,0,3,1,6,8,3,5,9,1,4,
