《C语言数据结构第讲图.pptx》由会员分享，可在线阅读，更多相关《C语言数据结构第讲图.pptx（58页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、难难 点点图的遍历 最小生成树 最短路径要要 求求熟练掌握以下内容：图的存储结构 图的遍历算法了解以下内容：图的最小生成树和求最小生成树算法 带权有向图的最短路径问题第1页/共58页第7 7章 目录7-1 7-1 图的定义和术语7-2 7-2 图的存储表示7-3 7-3 图的遍历7-4 7-4 图的连通性7-5 7-5 最短路径小 结实验7 7 图子系统习题7 7第2页/共58页7-1 图的定义和术语 图（GraphGraph）是一种比树形结构更复杂的非线性结构。在图形结构中，每个结点都可以有多个直接前驱和多个直接后继。7-1 7-1 图的定义和术语7-1-1 7-1-1 图的定义 图（Gra
2、phGraph）是由非空的顶点（VerticesVertices）集合和一个描述顶点之间关系边（EdgesEdges）的有限集合组成的一种数据结构。可以用二元组定义为：G G（V V，E E）其中，G G表示一个图，V V是图G G中顶点的集合，E E是图G G中边的集合。第3页/共58页 图7-1 无向图G1图7-2有向图G G2 2 V1V3V2V4V5V1V3V2V4 G1=（V，E）Vv1,v2,v3,v4,v5；E(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)。(v(vi i,v,vj j)表示顶点v vi i和顶点v vj j之间有一
3、条无向直接连线，也称为边。G2=(V,E)V=v1,v2,v3,v4E=,表示顶点vi和顶点vj之间有一条有向直接连线，也称为弧。其中vi称为弧尾，vj称为弧头。第4页/共58页7-1-2 7-1-2 图的相关术语（1 1）无向图（UndigraphUndigraph）在一个图中，如果每条边都没有方向（如图7-17-1），则称该图为无向图。（2 2）有向图（DigraphDigraph）在一个图中，如果每条边都有方向（如图7-27-2），则称该图为有向图。（3 3）无向完全图 在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n n个顶点的无向完全图
4、中，有n n(n-1)/2(n-1)/2条边。第5页/共58页（4 4）有向完全图 在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n n个顶点的有向完全图中，有n(n-1)n(n-1)条弧。（5 5）稠密图、稀疏图 我们称边数很多的图为稠密图；称边数很少的图为稀疏图。（6 6）顶点的度 在无向图中：一个顶点拥有的边数，称为该顶点的度。记为TD(v)TD(v)。第6页/共58页在有向图中：在有向图中：(a)一个顶点拥有的弧头的数目，称为该顶点的入度，一个顶点拥有的弧头的数目，称为该顶点的入度，记为记为ID(v)；(b)一个顶点拥有的弧尾的数目，
5、称为该顶点的出度，一个顶点拥有的弧尾的数目，称为该顶点的出度，记为记为OD(v)；(c)一个顶点度等于顶点的入度一个顶点度等于顶点的入度+出度，出度，即：即：TD(v)=ID(v)OD(v)。在图在图7-1的的G1中有：中有：TD(v1)=2TD(v2)=3TD(v3)=3TD(v4)=2TD(v5)=2在图在图7-2的的G2中有：中有：ID(v1)=1OD(v1)=2TD(v1)=3ID(v2)=1OD(v2)=0TD(v2)=1ID(v3)=1OD(v3)=1TD(v3)=2ID(v4)=1OD(v4)=1TD(v4)=2第7页/共58页 可以证明，对于具有n n个顶点、e e条边的图，顶
6、点v vi i的度TD TD(v(vi i)与顶点的个数以及边的数目满足关系：（7 7）权 图的边或弧有时具有与它有关的数据信息，这个数据信息就称为权（WeightWeight）。ACBD58697（8 8）网边（或弧）上带权的图称为网（NetworkNetwork）。如图7-37-3所示，就是一个无向网。如果边是有方向的带权图，则就是一个有向网。图7-3一个无向网示意图7-3一个无向网示意第8页/共58页（9 9）路径、路径长度 顶点v vi i到顶点v vj j之间的路径是指顶点序列v vi i,v,vi1i1,v,vi2i2,v,vimim,v,vj.j.。其中，（v vi i,v,vi
7、1i1），(v(vi1i1,v,vi2i2)，,(v(vimim,.v,.vj j)分别为图中的边。路径上边的数目称为路径长度。在图7-17-1的无向图G1G1中，v v1 1vv4 4vv3 3vv5 5与v v1 1vv2 2vv5 5是从顶点v v1 1 到顶点v v5 5 的两条路径，路径长度分别为3 3和2 2。（1010）回路、简单路径、简单回路 在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路或者环。如果一条路径上所有顶点除起始点和终止点外彼此都是不同的，则称该路径为简单路径。在图7-17-1中，前面提到的v v1 1到v v5 5的两条路径都为简单路径。除起始点和终止
8、点外，其他顶点不重复出现的回路称为简单回路，或者简单环。如图7-27-2中的v v1 1vv3 3vv4 4vv1 1。第9页/共58页（1111）子图 对于图G=G=（V V，E E），G G=（V V，E E），若存在V V是V V的子集 ，E E是E E的子集 ，则称图G G是G G的一个子图。图7-47-4示出了G G1 1和G G2 2的子图。图7-4图G1和G2的两个子图示意(a)G1的子图(b)G2的子图V1V3V2V1V3V2V4V5V1V3V2V4V5 图7-1 无向图G1第10页/共58页（1212）连通图、连通分量 在无向图中，如果从一个顶点v vi i到另一个顶点v v
9、j j(ij)(ij)有路径，则称顶点v vi i和v vj j是连通的。任意两顶点都是连通的图称为连通图。无向图的极大连通子图称为连通分量。图7-5(7-5(a)a)中有两个连通分量，如图7-5(7-5(b)b)所示。AEBFCDAEBFCD(a)无向图G3(b)G3的两个连通分量图7-5无向图及连通分量示意第11页/共58页（13）强连通图、强连通分量对于有向图来说，若图中任意一对顶点vi和vj(ij)均有从一个顶点vi到另一个顶点vj有路径，也有从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。图7-2中有两个强连通分量，分别是v1,v2,v3和v4，如图
10、7-6所示。（14）生成树连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树（SpanningTree）。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。n个顶点的生成树具有n-1条边。V1V3V2V4图7-6有向图G2的两个强连通分量示意第12页/共58页7-1-3图的基本操作图的基本操作有：（1）CreatGraph（G）输入图G的顶点和边，建立图G的存储。（2）DFSTraverse（G，v）在图G中，从顶点v出发深度优先遍历图G。（3）BFSTtaverse（G
11、，v）在图G中，从顶点v出发广度优先遍历图G。图的存储结构比较多。对于图的存储结构的选择取决于具体的应用和需要进行的运算。下面介绍几种常用的图的存储结构。7-2 图的存储表示第13页/共58页邻接矩阵是表示顶点之间相邻关系的矩阵。假设图G（V，E）有n个顶点，即Vv0,v1,vn-1，则G的邻接矩阵是具有如下性质的n阶方阵：1若(vi,vj)或是E(G)中的边Aij=0若(vi,vj)或不是E(G)中的边若G是网，则邻接矩阵可定义为：wij若(vi,vj)或是E(G)中的边Aij=0或若(vi,vj)或不是E(G)中的边其中，wij表示边(vi,vj)或上的权值（如图7-3）；表示一个计算机允
12、许的、大于所有边上权值的数。第14页/共58页 用邻接矩阵表示法如图7-77-7所示；用邻接矩阵表示法如图7-87-8所示。第15页/共58页 图的邻接矩阵具有以下性质：（1 1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。（2 2）对于无向图，邻接矩阵的第i i行（或第i i列）非零元素（或非元素）的个数正好是第i i个顶点的度TD(vTD(vi i)。（3 3）对于有向图，邻接矩阵的第i i行（或第i i列）非零元素（或非元素）的个数正好是第i i个顶点的出度OD(vOD(vi i)（或入度ID(vID(vi i)）。（4 4）用邻接
13、矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。第16页/共58页图的邻接矩阵存储的描述如下：#defineMAXLEN10typedefstructcharvexsMAXLEN;intedgesMAXLENMAXLEN;intn,e;MGraph;第17页/共58页建立一个图的邻接矩阵存储的算法如下：voidCreateMGraph(MGraph*G)inti,j,k;charch1,ch2;printf(请输入顶点数和边数(输入格式为:顶点数,边数):n);sca
14、nf(%d,%d,&(G-n),&(G-e);printf(请输入顶点信息(顶点号)每个顶点以回车作为结束:n);for(i=0;in;i+)getchar();scanf(%c,&(G-vexsi);for(i=0;in;i+)for(j=0;jn;j+)G-edgesij=0;第18页/共58页printf(请输入每条边对应的两个顶点的序号(输入格式为:i,j):n);for(k=0;ke;k+)getchar();printf(请输入第%d条边的顶点序号：,k+1);scanf(%c,%c,&ch1,&ch2);for(i=0;ch1!=G-vexsi;i+);for(j=0;ch2!=
15、G-vexsj;j+);G-edgesij=1;第19页/共58页7-2-2 7-2-2 邻接表邻接表(AdjacencyList)是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，该方法将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表。再将所有点的邻接表表头放到数组中，就构成了图的邻接表。在邻接表表示中有两种结点结构，如图7-9所示。顶点域边表头指针邻接点域指针域顶点表边表图7-9邻接矩阵表示的结点结构vertexfirstedgeadjvexnext第20页/共58页 一种是顶点表的结点结构，它由顶点域
16、（vertex）和指向第一条邻接边的指针域（firstedge）构成，另一种是边表结点，它由邻接点域(adjvex)和指向下一条邻接边的指针域(next)构成。对于网的边表需再增设一个存储边上信息（如权值等）的域（info），网的边表结构如图7-10所示。邻接点域边上信息指针域图7-10网的边表结构adjvexinfonext第21页/共58页 图7-11给出无向图7-7对应的邻接表表示。邻接表表示形式描述如下：第22页/共58页defineMAXLEN10/最大顶点数为10typedefstructnode/边表结点intadjvex;/邻接点域structnode*next;/指向下一个邻
17、接点的指针域/若要表示边上信息，则应增加一个数据域infoEdgeNode;typedefstructvnode/顶点表结点VertexTypevertex;/顶点域EdgeNode*firstedge;/边表头指针VertexNode;typedefVertexNodeAdjListMAXLEN;/AdjList是邻接表类型typedefstructAdjListadjlist;/接表intn,e;/顶点数和边数ALGraph;/ALGraph是以邻接表方式存储的图类型第23页/共58页建立一个有向图的邻接表存储的算法如下：voidCreateGraphAL(ALGraph*G)inti,j
18、,k;EdgeNode*s;printf(“请输入顶点数和边数(输入格式为:顶点数,边数)：n);scanf(%d,%d,&(G-n),&(G-e);/读入顶点数和边数printf(请输入顶点(格式为:顶点号)以回车作为结束:n);for(i=0;in;i+)/立有n个顶点的顶点表scanf(n%c,&(G-adjlisti.vertex);/读入顶点信息G-adjlisti.firstedge=NULL;/点的边表头指针设为空printf(请输入边的信息(输入格式为:i,j)：n);for(k=0;ke;k+)/建立边表scanf(“n%d,%d”,&i,&j);/读入边的顶点对应序号 s=
19、newEdgeNode;/生成新边表结点ss-adjvex=j;/邻接点序号为js-next=G-adjlisti.firstedge;/新边表插入到顶点边表头部G-adjlisti.firstedge=s;第24页/共58页 若无向图中有若无向图中有n个顶点、个顶点、e条边，则它的邻接表需条边，则它的邻接表需n个头个头结点和结点和2e个表结点。显然，在边稀疏个表结点。显然，在边稀疏(en(n-1)/2)的情况下，的情况下，用邻接表表示图比邻接矩阵节省存储空间，当和边相关的信用邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息较多时更是如此。息较多时更是如此。在在无无向向图图的的邻邻接接表表
20、中中，顶顶点点vi的的度度恰恰为为第第i个个链链表表中中的的结结点点数数；但但在在有有向向图图中中，第第i个个链链表表中中的的结结点点个个数数只只是是顶顶点点vi的的出出度度。如如果果要要求求入入度度，则则必必须须遍遍历历整整个个邻邻接接表表才才能能得得到到结结果果。有有时时，为为了了便便于于确确定定顶顶点点的的入入度度或或以以顶顶点点vi为为头头的的弧弧，可可以以建建立立一一个个有有向向图图的的逆逆邻邻接接表表，即即对对每每个个顶顶点点vi建建立立一一个个链链接接，以以vi为为弧弧头头的的弧弧的的链链表表。例例如如图图7-12所所示示为为有有向向图图G2（图图7-2）的邻接表和逆邻接表。）的
21、邻接表和逆邻接表。第25页/共58页 在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立邻接表的复杂度为O（n+e），否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为O（n*e）。第26页/共58页7-3 图的遍历图的遍历（traversinggraph）是指从图中的某一顶点出发，对图中的所有顶点访问一次，而且仅访问一次。图的遍历是图的一种基本操作。由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：（1）在图结构中，每一个结点的地位都是相同的，没有一个“自然”的首结点，图中任意一个顶点都可作为访问的起始结点。（2）在非连通图中，从一个顶点出发，只能
22、够访问它所在的连通分量上的所有顶点，因此，还需考虑如何访问图中其余的连通分量。（3）在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。（4）在图中，一个顶点可以和其它多个顶点相连，当这个顶点访问过后，就要考虑如何选取下一个要访问的顶点。第27页/共58页7-3-1深度优先搜索深度优先搜索（Depth-FisrstSearch）遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点发v出发，首先访问此顶点，然后任选一个v的未被访问的邻接点w出发，继续进行深度优先搜索，直到图中所有和v路径相通的顶点都被访问到；
23、若此时图中还有顶点未被访问到，则另选一个未被访问的顶点作为起始点，重复上面的做法，直至图中所有的顶点都被访问。V1V5V2V4V8V3V6V7图7-13无向图G5 以图7-13的无向图G5为例，其深度优先搜索得到的顶点访问序列为：v1v2v4v8v5v3v6、v7第28页/共58页显然，以上方法是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited0:n-1,，其初值为FALSE，一旦某个顶点被访问，则其相应的分量置为TRUE。从图的某一点v出发，递归地进行深度优先遍历的过程如下面算法所示。voidDFSTraverseM(MGraph*G)inti;fo
24、r(i=0;in;i+)visitedi=FALSE;/FALSE在c语言中定义为0，以下同for(i=0;in;i+)if(!visitedi)DFSM(G,i);第29页/共58页voidDFSM(MGraph*G,inti)intj;printf(tt深度优先遍历结点:结点%cn,G-vexsi);visitedi=TRUE;/TRUE在c语言中定义为1，以下同for(j=0;jn;j+)if(G-edgesij=1&!visitedj)DFSM(G,j);在遍历时，对图中每个顶点至多调用一次DFSM函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上
25、是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为O(n2)，其中n为图中顶点数。第30页/共58页 当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。7-3-2广度优先搜索广度优先搜索遍历类似于树的按层次遍历。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接
26、点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程中以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1,2,的顶点。第31页/共58页对图7-13无向图G5进行广度优先搜索遍历，首先访问v1和v1的邻接点v2和v3，然后依次访问v2的邻接点v4和v5及v3的邻接点v6和v7，最后访问v4的邻接点v8。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由些完成了图的遍历。得到的顶点访问序列为：v1v2v3v4v5v6v7v8
27、和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、的顶点，需附设队列以存储已被访问的路径长度为1、2、的顶点。V1V5V2V4V8V3V6V7图7-13无向图G5 第32页/共58页 从图的某一点v出发，递归地进行广度优先遍历的过程如下面的算法所示。voidBFSTraverseM(MGraph*G)inti;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+)if(!visitedi)BFSM(G,i);第33页/共58页voidBFSM(MGraph*G,intk)inti,j;CirQueueQ;InitQue
28、ue(&Q);printf(广度优先遍历结点:结点%cn,G-vexsk);visitedk=TRUE;EnQueue(&Q,k);while(!QueueEmpty(&Q)i=DeQueue(&Q);for(j=0;jn;j+)if(G-edgesij=1&!visitedj)printf(广度优先遍历结点:%cn,G-vexsj);visitedj=TRUE;EnQueue(&Q,j);第34页/共58页图7-4 图的连通性 分析上述算法，每个顶点至多进一次队列。遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图和深度优先搜索遍历的时间复杂度是相同的，两者不同之处仅仅在于对
29、顶点访问的顺序不同。判定一个图的连通性是图的一个应用问题，我们可以利用图的遍历算法来求解这一问题。本节将讨论无向图的连通性问题，并讨论最小代价生成树等问题。第35页/共58页7-4-1 7-4-1 无向图的连通分量和生成树 在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。例如，图7-14(a)是一个非连通图G6，按照图7-14(b)所示G3的邻接表进行深度优先搜索遍历AEBFCD图7-14(a)非连通
30、图图7-14(b)G6的邻接表第36页/共58页两次调用DFS过程（即分别从顶点A和D出发），得到的顶点访问序列为：ABFECE这两个顶点集分别加上所有依附于这些顶点的边，便构成了非连通图G3的两个连通分量。因此，要想判定一个无向图是否为连通图，或有几个连通分量，就可设一个计数变量count，初始时取值为0，在深度优先搜索算法循环中，每调用一次DFS，就给count增1。这样，当整个算法结束时，依据count的值，就可确定图的连通性了。设E(G)E(G)为连通图G G中所有边的集合，则从图中任一顶点出发遍历图时，必定将E(G)E(G)分成两个集合T(G)T(G)和B(G)B(G)，其中T(G)
31、T(G)是遍历图过程中历经的边的集合；B(G)B(G)是剩余的边的集合。显然，T(G)T(G)和图G G中所有顶点一起构成连通图G G的极小连通子图。第37页/共58页 按照7-1-27-1-2节的定义，它是连通图的一棵生成树，并且由深度优先搜索得到的为深度优先生成树；由广度优先搜索得到的为广度优先生成树。例如，图7-15(a)7-15(a)和(b)(b)所示分别为图7-137-13连通图G5G5的深度优先生成树和广度优先生成树。图中虚线为集合B(G)B(G)中的边，实线为集合T(G)T(G)中的边。图7-15(a)G5的深度优先生成树图7-15(b)G5的广度优先生成树V1V5V2V4V8V
32、3V6V7V1V5V2V4V8V3V6V7第38页/共58页 对于非连通图，通过这样的遍历，将得到的是生成森林。例如，图7-16 7-16(b)(b)所示为图7-16 7-16(a)(a)的深度优先生成森林，它由三棵深度优先生成树组成。图7-16(a)非连通无向图G7图7-16(b)G7的深度优先生成树林JHKLMAICFGBDEJHKLMAICFGBDE第39页/共58页7-4-2 7-4-2 最小生成树1 1最小生成树的基本概念由生成树的定义可知，无向连通图的生成树不一定是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不
33、同的生成树。图7-17(a)、(b)和(c)所示的均为图7-13的无向连通图G5的生成树。V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7 图7-17 7-17 无向连通图G5G5的三棵生成树（a）（b）（c）第40页/共58页可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n-1条边。如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值之和为最小的生成树，简称为最小生成树。最小生成树的概念可以应用到许多实际问题中。例如有这样一个问题：以尽可能抵的总造价建造城市间的通讯网络，把十个城市联系在一起。在这
34、十个城市中，任意两个城市之间都可以建造通讯线路，通讯线路的造价依据城市间的距离不同而有不同的造价，可以构造一个通讯线路造价网络，在网络中，每个顶点表示城市，顶点之间的边表示城市之间可构造通讯线路，每条边的权值表示该条通讯线路的造价，要想使总的造价最低，实际上就是寻找该网络的最小生成树。第41页/共58页2常用的构造最小生成树的方法（1 1）构造最小生成树的PrimPrim算法假设G（V，E）为一连通网，顶点集V=v1，v2，vn，E为网中所有带权边的集合。设置两个新的集合U和T，其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为Uv1（假设构造最小生成树
35、时，从顶点v1出发），集合T的初值为T。Prim算法的基本思想：从所有u U，v VU的边中，选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u，v）加入集合T中，如此不断重复，直到UV时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。图7-18(a)所示的一个网，按照Prim方法，从顶点A出发，该网的最小生成树的产生过程如图7-18(b)、(c)、(d)、(e)、(f)所示。第42页/共58页图7-18Prim算法构造最小生成树的过程示意图 AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)6812141617
36、515666668888812121214145第43页/共58页（2 2）构造最小生成树的KruskalKruskal算法 KruskalKruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。其基本思想是：首先选取全部的n n个顶点，将其看成n n个连通分量；然后按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n n个结点的生成树，有n-1n-1条边，故反复上述过程，直到选取了n-1n-1条边为止，就构成了一棵最小生成树。第44页/共58页图7-19Kruskal算法构造最小生成树的过程示意图AEBFCDAEBFCDAEBFCDA
37、EBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)68121416175155666688885121255145返 回第45页/共58页7-5 最短路径 最短路径问题是图的又一个比较典型的应用问题。例如，某一地区的一个交通网，给定了该网内的n个城市以及这些城市之间的相通公路的距离，问题是如何在城市A和城市B之间找一条最近的通路。如果将城市用顶点表示，城市间的公路用边表示，公路的长度则作为边的权值，那么，这个问题就可归结为在网中，求点A到点B的所有路径中，边的权值之和最短的那一条路径。这条路径就称为两点之间的最短路径，并称路径上的第一个顶点为源点（Sourse），最后一个顶
38、点为终点（Destination）。在不带权的图中，最短路径是指两点之间经历的边数最少的路径。例如在图7-20中，设V1为源点，则从V1出发的路径有（括号里为路径长度）：第46页/共58页V V1 1到V V2 2的路径有条：V V1 1VV2 2(20)(20)V V1 1到V V3 3的路径有条：V V1 1VV3 3(15),V(15),V1 1VV2 2VV3 3(55)(55)V V1 1到V V4 4的路径有条：V V1 1VV2 2VV4 4(30),V(30),V1 1VV3 3VV4 4(45),V(45),V1 1VV2 2VV3 3VV4 4(85)(85)V V1 1到
39、V V5 5的路径有条：V V1 1VV2 2VV3 3VV5 5(65),V(65),V1 1VV3 3VV5 5(25)(25)选出V V1 1到其它各顶点的最短路径，并按路径长度递增顺序排列如下：V V1 1VV3 3(15)(15)，V V1 1VV2 2(20)(20)，V V1 1VV3 3VV5 5(25)(25)，V V1 1VV2 2VV4 4(30)(30)。图7-20V1出发的路径V1V5V2V4V3201035101530第47页/共58页 从上面的序列中，可以看出一个规律：按路径长度递增顺序生成从源点到其它各顶点的最短路径时，当前正生成的最短路径上除终点外，其它顶点的
40、最短路径已经生成。迪杰斯特拉算法正是根据此规律得到的。迪杰斯特拉（DijkstraDijkstra）算法的基本思想：设置两个顶点集S S和T T，S S中存放已确定最短路径的顶点，T T中存放待确定最短路径的顶点。初始时S S中仅有一个源点，T T中含除源点外其余顶点，此时各顶点的当前最短长度为源点到该顶点的弧上的权值。接着选取T T中当前最短路径长度最小的一个顶点v v加入S S，然后修改T T中剩余顶点的当前最短路径长度，修改原则是：当v v的最短路径长度与v v到T T中顶点之间的权值之和小于该顶点的当前最短路径长度时，用前者替换后者。重复以上过程，直到S S中包含所有顶点。第48页/共
41、58页图7-21 7-21 用迪杰斯特拉算法求有向图的最短路径过程 V1V5V2V4V3201035101530V1V5V2V4V32015V1V5V2V4V320101530V1V5V2V4V320101530V1V5V2V4V32010153010第49页/共58页小 结（1 1）图是一种复杂的数据结构，图中的每一个顶点都可以有多个直接前驱和多个直接后继，所以是一种非线性的数据结构。（2 2）因为图是由顶点的集合和顶点间边的集合组成，所以图的存储也包括顶点信息和边的信息两个方面。（3 3）图的存储结构常用的有：邻接矩阵和邻接表等要求掌握。（4 4）对于n n个顶点的图来说，它的邻接矩阵是一
42、个nnnn阶的方阵。邻接矩阵中的元素取值只能是0 0或1 1，若图为无向图，则矩阵一定是对称矩阵，所以可以采用压缩存储；若是网，则要存储的是权值。（5 5）对于由n n个顶点和e e 条边的图，它的邻接表由n n个单链表所组成。无向图的邻接表占用n+2en+2e个存储单元；有向图的邻接表占用n+en+e个存储单元。第50页/共58页（6 6）图的遍历就是从图的某一顶点出发，访问图中每个顶点一次且仅一次。遍历的基本方法有深度优先搜索遍历和广度优先搜索遍历两种。深度优先遍历类似于树的先序遍历；广度优先遍历类似于树的按层次遍历。（7 7）取一个无向连通图的全部顶点和一部分边构成一个子图，若其中所有顶
43、点仍是连通的，但各边不构成回路，这个子图称为原图的一个生成树，同一个图可以有多个不同的生成树。对于带权的图，其各条边权值之和为最小的生成树即最小生成树。求最小生成树的方法，得到最小生成树中边的次序也可能不同，但最小生成树的权值之和却相同。（8 8）对于带权的有向图，求从某一顶点出发到其余各顶点的最短路径（所经过的有向边权值总和最小的路径）或求每一顶点之间的最短路径称为最短路径问题。第51页/共58页1 1实验目的（1 1）掌握图邻接矩阵的存储方法；（2 2）掌握图深度优先编历的基本思想；（3 3）掌握图广度优先编历的基本思想。2 2实验内容（1 1）编写按键盘输入的数据建立图的邻接矩阵存储；（
44、2 2）编写图的深度优先编历程序；（3 3）编写图的广度优先编历程序；（4 4）设计一个选择式菜单形式如下：实验7 图子系统第52页/共58页图子系统图子系统 *1-1-更新邻接矩阵更新邻接矩阵 *2-2-深度优先遍历深度优先遍历 *3-3-广度优先遍历广度优先遍历 *0-0-退退 出出 *第53页/共58页3 3操作举例（1 1）按下图建立图的邻接矩阵存储；AEDCB（2 2）按提示输入：第54页/共58页建立一个有向图的邻接矩阵表示请输入顶点数和边数(输入格式为:顶点数,边数):):5,75,7请输入顶点信息(顶点号)每个顶点以回车作为结束:AA BB CC DD EE请输入每条边对应的两
45、个顶点的序号(输入格式为:i,j):i,j):请输入第1 1条边的顶点序号：A,BA,B 请输入第2 2条边的顶点序号：A,DA,D 请输入第3 3条边的顶点序号：B,CB,C 请输入第4 4条边的顶点序号：C,AC,A 请输入第5 5条边的顶点序号：D,BD,B 请输入第6 6条边的顶点序号：D,ED,E 请输入第7 7条边的顶点序号：E,CE,C第55页/共58页已建立一个图的邻矩阵存储 0 1 0 1 00 1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0（3 3）再进行图的其它操作。第56页/共58页习题7 参见习题解答返 回第57页/共58页感谢您的欣赏！第58页/共58页