算法与数据结构课件DSC7

第七章.图〔Chapter7.Graph)§7.1图的定义及根本操作

图型结构是一种非常重要的、比线性和树型结构更复杂的非线性数据结构，可广泛用于描述自然界各种关系。右图所示即为一图型结构：ABCEFDGraph=（V,R）其中：V={ai|ai∈D0,i=1,2,…,n,n≥0}R={E}E={<x,y>|P(x,y)∧（x,y∈V)}其中D0为某一数据对象，V为顶点集，E为边集。图的一些根本术语：顶点〔vertex〕数据元素所构成的结点通常称为顶点。弧〔arc〕假设两个顶点间有关系<x,y>∈E，那么称<x,y>为一条弧。弧头〔head--又称终端点terminalnode〕假设<x,y>为一条弧，那么顶点y称为弧头。弧尾〔tail--又称初始点initialnode〕假设<x,y>为一条弧，那么顶点x称为弧尾。有向图〔directedgraph〕假设<x,y>∈E，并不总有<y,x>∈E，那么称此图为有向图。无向图〔undirectedgraph〕假设<x,y>∈E，总有<y,x>∈E，那么称此图为无向图。边〔edge〕无向图中两条弧<x,y>和<y,x>可用一条边〔x,y〕来表示。完全图〔completedgraph〕具有n*(n-1)/2条边的无向图称为完全图。有向完全图〔completeddirectedgraph〕具有n*(n-1)条弧的有向图称为有向完全图。稀疏图〔sparsegraph〕边数很少的图称为稀疏图。权〔weight〕有些图的边或弧具有一定的大小，称之为权。网〔network〕带权值的图又称为网或网络。子图〔subgraph〕由图的局部顶点和边组成的新图称为原图的子图。生成子图〔spanningsubgraph〕由图的全部顶点和局部边组成的子图称为原图的生成子图。稠密图〔densegraph〕边数很多的图称为稠密图。邻接点〔adjacent〕假设边〔vi,vj〕∈E，那么vi与vj互为邻接点。依附〔incident〕假设边〔vi,vj〕∈E，那么称边〔vi,vj〕依附于顶点vi和vj。相关联〔correlative〕假设边〔vi,vj〕∈E，又称边〔vi,vj〕与顶点vi和vj相关联。顶点的度〔degree〕与顶点相关联的边数称为该顶点的度，又分为入度和出度。顶点的入度〔indegree〕以顶点为头的弧数称为该顶点的入度。顶点的出度〔outdegree〕以顶点为尾的弧数称为该顶点的出度。路径〔path〕由顶点vi经过一系列边和顶点到达顶点vj所得到的顶点序列。回路〔loop--又称环cycle〕起点和终点为同一顶点的路径称为回路。连通〔connected〕无向图中顶点vi到vj间有路径存在，那么称vi和vj是连通的。连通图〔connectedgraph〕无向图中任意两顶点间均存在路径，那么称该图为连通图。连通分量〔connectedcomponent〕无向图中的极大连通子图称为原图的连通分量。强连通图〔stronglyconnectedgraph〕有向图中任意两顶点间均存在路径，那么称该图为强连通图。强连通分量〔stronglyconnectedcomponent〕有向图中的极大强连通子图称为原图的强连通分量。生成树〔spanningtree〕连通图的极小连通生成子图称为原图的生成树。有向树〔directedtree〕恰有一个顶点入度为0，其余顶点入度均为1的有向图。生成森林〔spanningforest〕由多棵有向树构成的有向图的生成子图称为生成森林。最小代价生成树〔minimumcostspanningtree〕连通网中由最小权值的边构成的生成树。图的根本操作：InitiateGetvertexFirstadjNextadjInsvertexTraverseInsarcDelvertexDelarc§7.2图的存储结构顺序存储结构：ABCEFD1、邻接矩阵〔adjacencymatrix)ABCDEF000001101000000100000010010000000010ABCDEFAij={0(vi,vj)∈E1(vi,vj)∈E√#definemaxvtxnumuser_supplytypedefintadjmatrix[maxvtxnum][maxvtxnum];typedefstruct{adjmatrixarcs;intvtxnum,arcnum;}graph;

2、关联矩阵〔correlatedmatrix)Bij={1vi是ej的弧头0vi与ej不相关联-1vi是ej的弧尾ABCEFDe1e2e3e4e5e6e7e1e2e3e4e5e6e7100000-1-1-100

10001-1

0

000001-1

0000001-11000000-11ABCDEF#definemaxvtxnumuser_supply#definemaxedgenumuser_supplytypedefintcormatrix[maxvtxnum][maxedgenum];typedefstruct{cormatrixarcs;intvtxnum,arcnum;}graph;

链式存储结构：1、邻接表〔adjacencylist)ABCEFD6∧A12∧E51∧B234∧C35∧D4F65∧firstarcvexdata头结点adjvexinfonextarc弧结点按结点出度建立：#definemaxvtxnumuser_supplytypedefstructarcnode{intadjvex;edgetypeinfo;structarcnode*nextarc;}arcnode;typedefstruct{vextypevexdata;structarcnode*firstarc;}vexnode;typedefvexnodeadjlist[maxvtxnum];√2、逆邻接表〔inverseadjacencylist)firstarcvexdata头结点adjvexinfonextarc弧结点按结点入度建立：√ABCEFD2312341E5B2C3D4F6∧312∧A122∧A12∧53∧23∧1142∧64定义同邻接表ABCEFD3、十字链表〔orthogonallist)按结点入度和出度建立：firstoutdata头结点firstintailvexheadvexhlink弧结点tlinkD44∧5A116∧∧B2212∧3∧∧E55∧2∧F66∧5∧C33∧4∧#definemaxvtxnumuser_supplytypedefstructanode{inttailvex,headvex;structanode*hlink,*tlink;}anode;typedefstruct{vextypedata;structanode*firstin,*firstout;}vnode;typedefvnodeortlist[maxvtxnum];ABCEFD4、邻接多重表〔adjacencymultilist)邻接多重表是无向图的一种存储结构：#definemaxvtxnumuser_supplytypedefstructenode{intmark,ivex,jvex;structenode*ilink,*jlink;}enode;typedefstruct{vextypedata;structanode*firstedge;}vnode;typedefvnodeadmlist[maxvtxnum];data头结点firstedgemarkivex边结点ilinkjvexjlinkD4A1B26∧1E5F6C312∧2334∧4556∧25∧23∧ABCEFDGH§7.3图的遍历深度优先遍历〔depth_firstsearch〕即按某种搜索顺序对图中每个结点访问且仅访问一次。从图中某一顶点v0出发，访问该顶点，并依次从v0的所有未被访问过的邻接点中任意选取一个顶点作为新的出发点，用同样的方法访问其它所有顶点，直到所有与v0连通的顶点均被访问到为止；假设此时仍有顶点尚未被访问，那么从未被访问过的顶点中任意选取一个顶点作为新的出发点，反复此过程，直至图中所有顶点均被访问过一遍为止。ABCDGFEHABFEHCDGvoidDfstraverse(graphg){for(v=0;v<g.vtxnum;v++)visited[v]=FALSE;for(v=0;v<g.vtxnum;v++)if(!visited[v])dfs(g,v);}voiddfs(graphg,intv){visit(v);visited[v]=TRUE;for(w=Firstadj(g,v);w>=0;w=Nextadj(g,v,w))if(!visited[w])dfs(g,w);}ABCEFDGH广度优先遍历〔breadth_firstsearch〕从图中某一顶点v0出发，访问该顶点，并依次访问v0的所有未被访问过的邻接点，然后将所有这些邻接点作为新的出发点，用同样的方法访问其它所有顶点，直到所有与v0连通的顶点均被访问到为止；假设此时仍有顶点尚未被访问，那么从未被访问过的顶点中任意选取一个顶点作为新的出发点，反复此过程，直至图中所有顶点均被访问过一遍为止。ABCDGFEHABCFHDGEvoidBfstraverse(graphg){for(v=0;v<g.vtxnum;v++)visited[v]=FALSE;for(v=0;v<g.vtxnum;v++)if(!visited[v])bfs(g,v);}voidbfs(graphg,intv){Iniqueue(Q);Enqueue(Q,v);while(!Empty(Q)){v=Dequeue(Q);visit(v);visited[v]=TRUE;for(w=Firstadj(g,v);

w>=0;w=Nextadj(g,v,w))if(!visited[w])Enqueue(Q,w);}}作业20.自选存储结构，编写一算法判断无向图中任意给定的两个顶点间是否存在一条长度为k的简单路径〔即不含回路的路径〕。21.自选存储结构，试给出求有向图中所有简单回路〔即其中不再含有回路的回路〕的算法。§7.4图的连通性及最小代价生成树无向图的连通分量：一次调用深度或广度优先搜索〔dfs、bfs〕所得到的顶点集即为连通分量的顶点集。有向图的强连通分量：利用深度优先搜索遍历，从有向图中任意一个顶点出发遍历该图，记录每次递归退出dfs过程时的当前顶点序列；再按该序列逆序去逆向遍历该图〔从弧头至弧尾〕，每调用一次dfs过程所得到的顶点集即为强连通分量的顶点集。ABCEFDBAFECDEFADCB从B顶点出发正向遍历：BFAC从B顶点出发逆向遍历：DEBFACDE最小生成树：一、Prim算法：1、将图中顶点分为两个集合，其中集合X包含图的一个顶点v0，集合Y包含除v0外的其它所有顶点；2、将跨接这两个集合的权值最小的边参加图中，并将其依附在集合Y中的顶点v1从Y中移入集合X中；3、反复过程2，直到集合Y为空，所得生成子图即为最小生成树。ABCEFD2313221ABCEFD21321二、Kruskal算法：1、将图中所有边按权值从小到大排序；2、取权值最小的边，参加图中，判断是否形成了回路，假设无，那么保存此边，否那么去掉该边，重取权值较小的边；3、反复过程2，直到全部顶点均连通为止。ABCEFD2313221ABCEFD213211AF1CD2AB2BE2FE3ED3BC2三、破圈法：1、在图中找到一个回路；2、去掉该回路中权值最大的边；3、反复此过程，直到图中不存在回路为止。ABCEFD2313221ABCEFD21321232212221132312332四、去边法：1、将图中所有边按权值从大到小排序；2、去掉权值最大的边，假设图不再连通那么保存此边，再选取下一权值较大的边去掉；3、反复此过程，直到图中只剩下n-1条边为止。作业22.给出下面无向网的邻接矩阵，并按普里姆算法求其最小代价生成树；给出其邻接表，再按克鲁斯卡尔算法求其最小代价生成树。abcefd2314221gh2312第四次上机作业输入无向图的邻接矩阵，使用前面讲过的任意三种方法求该图的最小代价生成树，并分析各自的时间复杂度。程序设计常用方法之三：贪心法〔Greedy〕贪心法的特点是一步一步进行，根据某个优化测度〔可能是目标函数〕，每一步都要保证获得局部最优解；每一步只考虑一个输入，它的选取应满足局部优化条件；假设下一个输入与局部最优解一起不再是可行的解，那么不把该输入加到局部解中。反复此过程，直到得到问题的解或把所有输入枚举完为止。背包问题的求解：有n个物体和一个背包，物体i的重量为wi，价值为pi，背包能装物体的重量为M。若物体i的xi部分（1≤i≤n，0≤xi≤1）装入背包中，则具有价值pixi，问应怎样选取物体，使得背包装满且总的价值最高？例：我们可以先将单位价值最大的物体装入背包中，即将物体按pi/wi从大到小排序，有p2/w2≥p3/w3≥p1/w1，那么先将物体2全部装入，空余局部再装物体3，即得到最优解。由此可见，贪心法是一种很直接的算法设计方法，用贪心法求问题的次优解效率是很高的。设n=3，M=20，pi=(25,24,15)，wi=(20,15,10)，那么：1、xi=(1/2,1/3,1/2)时有∑pixi=28；2、xi=(1/5,1,1/10)时有∑pixi=30·5；3、xi=(0,1,1/2)时有∑pixi=31·5；显然第三个解较好〔其实是最优解〕，但它是如何得到的呢？4、xi=(1,0,0)时有∑pixi=25；voidPack(intn,intM,intarrayW,intarrayX){//W按pi/wi

从大到小排序for(i=0;i<n;i++)X[i]=0;for(i=0;(W[i]<=M)&&(i<=n);i++){X[i]=1;M=M-W[i];}if(i<=n)X[i]=M/W[i];}

有很多问题均可用贪心法求解，如求最小代价生成树的Kruskal算法。上面的背包问题有时也描述成“0-1背包问题〞，即xi或者为0或者为1，它也可先按单位价值从大到小排序，再用上次作业的方法求解〔第一个解即为次优解〕即可。§7.5有向无环图及其应用无环的有向图称为有向无环图〔directedacyclinegraph〕。拓扑排序〔topologicalsort〕拓扑排序是指由集合上的一个偏序〔partialorder〕得到该集合上的一个全序〔totalorder〕的过程。由拓扑排序得到的全序又称为拓扑有序〔topologicalorder〕。一个表示偏序的有向图通常用来表示一个流程图。图中每条有向边分别表示两个子工程〔活动〕间的次序关系；而顶点那么分别表示各活动，因此，这类图又称为顶点活动图〔activityonvertexnetwork〕，简称AOV图。如用顶点表示课程，用弧表示某些课程是其它课程的先修课，那么拓扑排序就是求在同时只能学习一门课程时的学习次序。C1C2C3C6C4C5C7C8C9C10C1C2C3C4C5C6C7C8C9C10C2C1C3C4C5C6C7C8C9C10C1C2C4C3C5C6C7C8C9C10C2C1C4C3C5C6C7C8C9C10C1C2C5C4C3C6C7C8C10C9以下都是拓扑排序结果：拓扑排序步骤：1、扫描图中各顶点，将入度为零的顶点入队列；假设该有向图不是无环图，那么不存在拓扑排序，就不可能输出全部顶点。此特点可用来判断一个有向图是否存在回路。2、从队列中取出一个顶点输出，并将其所有邻接点的入度减一，假设入度减为零，那么将该邻接点入队列；3、反复执行步骤2，直至所有顶点的入度均为零。关键路径〔criticalpath〕关键路径是指影响整个工程进度的那些子工程〔活动〕所组成的路径。减少这些活动所需时间，整个工程就能提前完成。在这类有向无环图中，顶点一般用来表示事件〔event〕，弧用来表示活动，权值表示活动所需时间，因此，此类有向无环图又称为边活动图〔activityonedgenetwork〕，简称AOE图。V1V2V3V6V4V5V7V8V9V10a1=4a2=3a3=2a4=3a5=3a6=5a9=5a12=5a7=4a8=6a10=2a11=1a13=8a14=5如左图所示工程，其最后完工时间为21天。能否加快某些活动的进度，使整个工期缩短呢？活动的最早发生时间（ej）：定义为该活动aj的弧尾事件的最早发生时间。活动的最晚发生时间（lj）：定义为在不影响总工期的前提下，该活动所能发生的最晚时间。

答案是肯定的。问题的关键是要提高哪些活动的效率才能缩短整个工期？这些活动就是我们要求的关键路径。事件的最晚发生时间（vli）：定义为从Vi到事件Vn的最长路径。事件的最早发生时间（vei）：定义为从V1到事件Vi的最长路径。ve(j)=Max{ve(i)+dut(<i,j>)}，<i,j>∈T，2≤j≤n，T为所有以j为头的弧的集合，且ve(1)=0。i

vl(i)=Min{vl(j)-dut(<i,j>)}，<i,j>∈S，1≤i≤n-1，S为所有以i为尾的弧的集合，且vl(n)=ve(n)。j可用拓扑排序求的各事件〔顶点〕的最早发生时间，然后再用逆拓扑排序求的各事件的最晚发生时间，有：设活动ai=弧<Vj,Vk>的权定义为活动的持续时间dut(<j,k>)，那么有下式成立：e(i)=ve(j)，l(i)=vl(k)-dut(<j,k>)。假设e(i)=l(i)，那么活动ai就是关键路径上的关键活动。V1V2V3V4V5V6V7V8V9V10

(a1a2a3)(a4)(a5a6)(a7)(a8)

(a9a10)(a11a13)(a12)(a14)

ve：04327813101521l：(002)(4)(43)(4)(7)(89)(1513)(11)(16)vl：04347813111621√√√√√√√关键活动：a1、a2、a4、a6、a8、a9、a13；关键路径：V1V2V5V7V10和V1V3V6V7V10。21V1V2V3V6V4V5V7V8V9V10a1=4a2=3a3=2a4=3a5=3a6=5a9=5a12=5a7=4a8=6a10=2a11=1a13=8a14=5(e)§7.6最短路径我们经常需要求解从某点〔源点--source)出发到达另一点〔终点--destination)的最短路径。当然，我们可以先求出这两点间的所有简单路径，再从中选出最短路径，但这种方法未免太低效率了，有没有更好的方法呢？单源最短路径：从某源点到其它所有顶点间的最短路径。Dijkstra

算法从源点的所有邻接点中找出距源点最近的邻接点，这即是该点的最短路径；并以该邻接点为中间点，比较其它各顶点与源点的路径通过中间点后是否更短，若是则用新路径代替老路径，再从中找出其它各点距源点最近的顶点作为新的中间点，这也是该点的最短路径；反复此过程，直至全部顶点距源点的最短路径均找到为止。该算法是求解单源最短路径。顶点对间最短路径：各顶点到其它所有顶点间的最短路径。V1V2V3V4V532331621求以下图中v1到各顶点的最短路径：V1V2V3V4V56∞∞2V1V2V1V3V1V4

V1V5535V1V5V2

V1V5V3V1V5V44

5V1V5V3V2

V1V5V45V1V5V4V1到各点的最短距离为：4、3、5和2；V1到各点的最短路径为：V1V5V3V2、

V1V5V3、V1V5V4和V1V5。该方法的时间复杂度为O(n2)。其实，此法用的也是贪心法。Floyd算法设每个顶点都可以是中间顶点，通过该顶点都有可能使其它顶点间的距离缩短。因此，将所有顶点都作为中间顶点操作过一遍后，所得到的各顶点对间的距离即是最短距离，所得路径自然也就是最短路径了。该算法是求顶点间最短路径。我们可以通过调用n次Dijkstra算法求的每对顶点间的最短路径，时间复杂度为O(n3)。但还能有其它的求解方法吗？Floyd定义了n阶方阵序列A(0)、A(1)、…、A(k)、…、A(n)，其中A(0)为邻接矩阵，其它方阵A(