数据结构课件chap7图

1、7.1图的定义和术7.2图结图7.1图的定义和术7.2图结图的遍图的连通性问7.4.3最小生成有向无环图及其应最短路1图的结构定义图是由一个顶点集V 图的结构定义图是由一个顶点集V 和一个弧集据结构Graph=(V,R其中，Vx|x的R=/数据VR|v,wV表示vw弧v弧尾， w为弧头。P(v,w)定义了弧的意义或信息2的图为有向图G1=(V1,的图为有向图G1=(V1,V1=A,C,D,E VR1=, ,3ABECD,由顶点集和集的,由顶点集和集的图则称 (v,w)为顶点v和顶w边作无向图,V2=A,B,C,D,E,VR2=(A,B),(B,E),(C,D),(D,F), (B,F),(C,

2、F)BCADFE4名词和术名词和术5A9弧（或边）带的图分别称作网（或无向网）A9弧（或边）带的图分别称作网（或无向网）BE73CF2AA设图G=(V,VR)且VVG 为G子图BECF6假设图中有假设图中有n 个顶点，e 条边，含有e=n(n-1)/2 条边的无向图称完全图含有 e=n(n-1)条弧的有向图有向完全图若边或弧的个数 enlogn，则称稀疏图，否则称作稠密图7假若顶点v 和顶点w 之间存在一条边假若顶点v 和顶点w 之间存在一条边则称顶点和互为邻接点边(v,w) 和顶点v和相关联和顶点v 关联的边的数目定义为顶点的度BCID(B)=ID(A)=DAEF8A顶点的出度: 以顶点BE

3、CF顶点的入度A顶点的出度: 以顶点BECF顶点的入度以顶点为弧头的弧的数目OD(B) = ID(B)=TD(B)=顶点的度出度(OD)+入度9设图G=(,VR) u=vi,0设图G=(,VR) u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm,则称从顶点u 到顶点w 之间存在一条路径。如:长度为3A不重复出现的路10 BECF若图G点之间都有路径相通CBD则称此图为连通图AEFCB若图G点之间都有路径相通CBD则称此图为连通图AEFCB子图称作此图的DAEF分量一条有向路径，则称此有向图为强连通图否则，其各个强连通子图强连通分量AABEBECF一条有向路径

4、，则称此有向图为强连通图否则，其各个强连通子图强连通分量AABEBECFCFBC,通图有 ne条边其中 n-1条边n通图有 ne条边其中 n-1条边n的生成树CBDAEF的生成森林基本操基本操结构的建CreatGraph(&G,结构的建CreatGraph(&G,按定义(,VR构造销毁对顶点LocateVex(G,操/对顶点LocateVex(G,操/G中存在顶点u，则返回该顶/图中“位置否则返回其它信息返回v的值PutVex(&G, v, / 对v赋值value对邻接点AdjVex(G,对邻接点AdjVex(G,/ 返回v的“第一个邻接点。若该顶/在G中没有邻接点，则返回“空”NextAdj

5、Vex(G,v, / 返回v的（相对于w的）下一个邻/点”。若w 是v的最后一个邻接点，/返回“空”或删InsertVex(&G, 或删InsertVex(&G, /在图G中增添新顶点vDeleteVex(&G, / 删除G中顶点v及其相关的弧和删除InsertArc(&G,v,和删除InsertArc(&G,v,在G中增添弧，若G/则还增添对称弧w,vDeleteArc(&G, v, /在G中删除弧，若G/则还删除对称弧=0;ifDS(,对v的尚/ 递归调用的邻接顶点/ void DFSTraverse(GraphSus(*void DFSTraverse(GraphSus(*isit)(v

6、)/ 对图G 作深度优先遍isitFuncisit;for (v=0;vG.vexnum;+v) visitedv=ALSE;/for (v=0;vw1V-w2二、广度优先搜索遍历对连通图，从起始点V其中，V-w1V-w2VV的路径长度为-的路径长度为-w8w4的路径长度为3从图中的某个顶点V0此V0的所有未顶点之后邻接点，之后它们的邻接点和V0从图中的某个顶点V0此V0的所有未顶点之后邻接点，之后它们的邻接点和V0void BFSTraverse(GraphSus*for(v=0;vG.vvoid BFSTraverse(GraphSus*for(v=0;vG.vexn;visitedv=/

7、初始nu置空的辅助队列for(vv+vif(!visitedv)v尚/ visitedv = EnQueue(Q, isit(v);vv入visitedv = EnQueue(Q, isit(v);vv入队whileDeQueue(Q,队头元素出队并置为AdjVex(G,u);if(!EnQueue(Q,w);/ /的顶点w的的7.1判断下图是否强连通图。如果不是，则给出7.1判断下图是否强连通图。如果不是，则给出强连通分ABDC7.2 写出下图从顶点1出发的一种广度优123674589连通：顶点v至之间有路径存连通图：G则称G是连通图。连通分量：ABAB连通：顶点v至之间有路径存连通图：G则

8、称G是连通图。连通分量：ABABFGEEFGHHIJIJKLMMKLCDCD无向图G的三个连通分无向图通；也可通过对算法BFSTraverse()如何设计算法以求出无向图G中的所有n一棵树的n-1条边ABABABABEHEHEHEH无向图MMMMCDCDCDC中的所有n一棵树的n-1条边ABABABABEHEHEHEH无向图MMMMCDCDCDCD一棵有n个顶点的生成树有且仅有n-1图。如果它多于n-1 条边，则一定有环。DFS生成树和BFS生成一个子图，该子图称为生成树。因此有DFS生成树aBFS生成树BFS生成acdefacdeDFS生成树和BFS生成一个子图，该子图称为生成树。因此有DF

9、S生成树aBFS生成树BFS生成acdefacdefhkcdefhkDFS生成h无向图(连通网(连通网的)最小生成假设要在n联络网，则连通n e条带权的边中选取n-1条边（回路），使“权值之和”为最小1e条带权的边中选取n-1条边（回路），使“权值之和”为最小1615234344325656左图的最小代价生成MST性通图，U是结点集合VG=V,E。若(u,v)是一条代价最小的边，且u属于U,v属于V - U,存在一棵包括边(u,v)设其为T。将边(u,v)添加到树 T,则形成一条包含(u v)。因此，必定MST性通图，U是结点集合VG=V,E。若(u,v)是一条代价最小的边，且u属于U,v属于

10、V - U,存在一棵包括边(u,v)设其为T。将边(u,v)添加到树 T,则形成一条包含(u v)。因此，必定存在另一条边(u，v),且u属于,v属于- 。删去边(u,v)，得到另一棵生成树因为边(u,v)小于边(u，v)的代价，所以新的生成树T将是代价最小的U。vV-uT算法一：（普里姆算法算法二：（克鲁斯卡尔算法算法一：（普里姆算法算法二：（克鲁斯卡尔算法:普里:普里之后往生成树上添加新的顶点 w。在添加的顶点w和已经在生成树上的顶点v之间连通顶点v 和 w 之间的边中取值最小。之上含有n-1个顶点为止ab5cegdfab5cegdf=14+8+3+5+16+2162 条件在生成树的构造过

11、程中，图中条件在生成树的构造过程中，图中nU 和尚未落在生成树上的顶点集 V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边设置一个辅助数组，对当前VU设置一个辅助数组，对当前VU和顶点集U中顶structU集中的顶点边的权wcosedgeMAX_EE_N;abec37d8gfabcdefg0123456cdeadews53 abec37d8gfabcdefg0123456cdeadews53 /用普里姆算法从顶点u出发构造网G的最小生for(j=0;jexnu;+jif/辅助数组初始closedgej=u,G.arcskj.adjclosedgek.lowcost=/ 初始f

12、or (i=0;iG.vexnum;+i)继续向生成树上添加顶点;k=ik=il)/ 求出加入生成树的下一个顶点f(closedgek.adjvex,输出生成树上一closedgek.lowcost=/k顶点并入Ufor (j=0;jexnu;/修改其它顶点的最小if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ;：考虑问题的出发点: 为使生成树上值之和达到最小具体做法：考虑问题的出发点: 为使生成树上值之和达到最小具体做法先构造一个只含nSG加不使SGSG条边，如此重复，直至加上 n-1 条边为。ab5

13、cegdfab5cegdf算法描述构造非连通图算法描述构造非连通图ST=,k=i=k计选中的边while(kn-1)E第 i条权值最小的边若(u,v)加入ST后不使ST中产生回路输出边则且当前形成的集合树一个无环的有向图称为一个无环的有向图称为有向无环图(directedacycline DAG7.5.1问题7.5.1问题课课程代课程名先修程序设计基离散数计算机原编译原操作系高等数线性代普通物数值分C1,79,C10何谓“何谓“拓扑排序BADCABADCABCACB或BADC因为图中存BADC因为图中存在一个回路,C,如何进行拓扑排序如何进行拓扑排序有以它为尾的弧abhcdgfe没有前驱的顶点

14、 入度为零的顶删除顶点及以它为尾的弧 弧头顶点的入79减abhcdgfe没有前驱的顶点 入度为零的顶删除顶点及以它为尾的弧 弧头顶点的入79减取入度为零的顶点while (v0)取入度为零的顶点while (v0)while (w0)inDegreew-取下一个入度为零的顶点iff(“图中有回路述”for (i=0;iexnu;ifPush(S,/入度为零的顶点入/对输出顶点计while (!EmptyStack(S)Pop(S,for/对输出顶点计while (!EmptyStack(S)Pop(S,forAdj(v);-弧头顶点的入度减ifPush(S,/新产生的入度为零的顶点入if (c

15、ountG.vexnum)f(“图中有回路)问题问题AOEOnEdge)带权的AOEAOEOnEdge)带权的AOE向无环图，其中顶点表示事件，弧表整个工程完成的时间为：从有向图的源点到的最长路径bg26整个工程完成的时间为：从有向图的源点到的最长路径bg2618aek47145ch42df“关键活动”指的是：该弧上的权值增加 有向图上的最长路径的长度增加“事件(顶点)” “事件(顶点)” 的最早发生时间“事件(顶点)” 的最迟发生时间假设第i条弧为j,假设第i条弧为V1再下一条路径长度次短的最短路径的特点它可能有三种情况：或者是再下一条路径长度次短的最短路径的特点它可能有三种情况：或者是该点

16、(只含一条弧或者是从源点经过顶点 从源点经过顶点v2它或者是直接从源点到该点(只含一或者是从源点经过已求得最短路的顶点，再到达该顶点设置辅助数组Dist，其中设置辅助数组Dist，其中每个分量当前所求得的从源点到其余各顶点的最短路径。Distk源点到顶点k的弧上的权值或者= + 其它顶点到顶点k 的弧上的权值1）Distk1）DistkG.arcsv0kV0和k之间存在V0和k其中的最小值即为最短路径的长度2）修改其它各顶点的Distk值若 Distu+G.arcsukDistk则将Distk改为Distu+G.arcsuk4设一个集合U，存放以产生的最短路径的顶点。初始，U含源点52dist

17、第二条路：1到2、5、84设一个集合U，存放以产生的最短路径的顶点。初始，U含源点52dist第二条路：1到2、5、8中后，某些顶点的值应调整471945336x的中间点必定都在U属于U，如左Ux则必定有disuu, dist按算法，原点到u106 路径应已产生，即u属于u678dist54976. Dijkr算法描5932867g6. Dijkr算法描5932867g123458123445566778111123182345672357234567467652345672图用邻接矩阵表示，设置集合U与辅助数源点vo图的顶点数为ngi,j代表上的权(1) disti=gv0,i(2) U=v0;(3) 下面步骤重复n-1选择v使得满足 distv=mindistu|uU v加到集合U中 6. Dijkr算法描1826. Dijkr算法描182375466257. Dijk7. Dijkr 算法的C由于C/C+的下标从0开始，所以算法中作相应的改动，用NUM图的顶点间分析#definevoid shortpath_dij(gNUM,v0) /v0为源点，值为1到setv0-/用1表示源点属于U集 if(setw= =0 & distwmin) v=w; min=d