[精品]图的定义46

第七章 图,图的定义 图的存储结构 图的遍历 图的应用,7.1 图的定义和术语,1. 图 有向图（Digragh） 无向图（Undigraph）,7.1 图的定义和术语,有向图（Digragh） G=（V，A） 其中，V为顶点的有穷非空集合 A为顶点之间的关系集合,G1=（V，A） V=v1, v2, v3, v4A=, , , 其中表示从x到y的一条弧（arc），A为弧集合，x为弧尾（tail），y为弧头（head),7.1 图的定义和术语,无向图（Undigraph） G=(V,E) 其中，V同有向图，E为顶点之间的关系集合， E为边集合,G2=（V，A） V=v1, v2, v3, v4, v5E=(v1, v2), (v1, v4), (v2, v3), (v3, v4), (v2,v5), (v3,v5)其中，(x, y)表示x与y之间的一条连线，称为边（edge）,7.1 图的定义和术语,设n为顶点数，e为边或弧的条数 对无向图有：0=e=n(n-1)/2 有向图有：0=e=n(n-1),证明：每个顶点至多有n-1条边与其它的n-1个顶点相 连，则n个顶点至多有n(n-1)条边。但每条边连 接2个顶点，故最多为n(n-1)/2,7.1 图的定义和术语,2. 完全图 边达到最大的图,无向完全图：边数为n(n-1)/2的无向图 有向完全图：弧数为n(n-1)的有向图,权：与图的边或弧相关的数网：边或弧上带有权值的图,7.1 图的定义和术语,3. 顶点的度 TD（V） 无向图：为依附于顶点V的边数 有向图：等于以顶点V为弧头的弧数（称为V的 入度，记 为ID（V）与以顶点V为弧尾的弧数（称为V 的出度，记为OD（V）之和。即： TD（V）=ID（V）+OD（V）,无向图 n e= 1/2（TD(vi)） i=1,结论：,有向图 n n e= ID(vi)=OD(vi) i=1 i=1,无向图的度数为依附于顶点v的边数；有向图的度数等于以顶点v 为弧头的弧数与以顶点v为弧尾的弧数之和,7.1 图的定义和术语,4. 路径 无向图：顶点v到v的路径是一个顶点序列（v=vi0, vi1, , vim=v） 其中，（vij-1,vij ）E, 1=j=m 有向图： 顶点v 到v的路径是有向的顶点序列（v=vi0, vi1, , vim=v） 其中，（vij-1,vij ）A, 1=j0) write(closedgek.vex, k); 输出生成树的边 closedgek.lowcost:=0; 顶点k并入U FOR v:=1 TO vtxnum DO IF gnk, vclosedgev.lowcost THEN closedgev.lowcost:=gnk,v; closedgev.vex:=k 新顶点并入U后，重选最小代价边 ENDP； minispantree_PRIM,算法minispantree_PRIM的几点说明:1. gn为 网的邻接矩阵 即 gni, j=wij 或 为无穷大2. 辅助数组closedge1.n 有两个分量: closedgek.vex存放边(k, j)依附的另一顶点j( jU) closedgek.lowcost存放边(k, j)的权值，当值为0时，表示顶点k已加入到集合U中。 区别顶点 U或V-U，是根据， .lowcost=0 U .lowcost0 V-U closedgek.vex U 而 k V-U,算法minispantree_PRIM的几点说明:3. FUNC minimum(closedge):integer; min:=; h:=1; FOR k:=1 TO vtxnum DO IF closedgek.lowcost0 AND closedgek.lowcostmin THEN min:=closedgek.lowcost; h:=k RETURN(h)ENDF； minimum,例子：,四、克鲁斯卡尔（Kruskal）最小生成树算法,Kruskal 算法是逐步给生成树T中添加不和T中的边构成回路的当前最小代价边。特点: 以最小代价边主。设N=（V，E）是个连通网, 算法步骤为：1. 置生成树T的初始状态为T=（V，）2. 当T中边数n-1时, 重复下列步骤: 从E中选取代价最小的边（v, u）, 并删除之; 若（v, u）依附的顶点v和u落在T中不同的连同分量上，则将边（v, u）并入到T的边集中；否则，舍去该边，选择下一条代价最小的边.,四、克鲁斯卡尔（Kruskal）最小生成树算法,步骤 (v, u) E T,1 (1, 3),0,1,四、克鲁斯卡尔（Kruskal）最小生成树算法,步骤 (v, u) E T,3 (2, 5),2 (4, 6),四、克鲁斯卡尔（Kruskal）最小生成树算法,步骤 (v, u) E T,5 (1, 4),4 (3, 6),四、克鲁斯卡尔（Kruskal）最小生成树算法,步骤 (v, u) E T,6 (2, 3),边数=n-1=5代价=(1+2+3+4+5)=15,7.5 拓扑排序(topological sort) 拓扑排序是一种对非线性结构的有向图进行线性化的重要手段一、AOV网(Activity on vertex network) 一个有向图可用来表示一个施工流程图、一个产品生产流程图、或一个程序框图等。如图：,课程安排,施工从活动 a1、 a2开始，到达活动 a8和 a9时，整个施工结束。有向图中，顶点表示活动，弧表示活动 ai优先于活动 aj ，称这类有向图为顶点表示活动的网（AOV网）。,7.5 拓扑排序(topological sort),AOV网可解决如下两个问题：（1）判定工程的可行性。显然，有回路，整个工程就无法结束（2）确定各项活动在整个工程执行中的先后顺序。 称这种先后顺序为拓扑有序序列。,如图有如下拓扑有序序列： a1 a2 a3a4 a6 a5 a7 a8 a9 a2 a6 a1 a3 a4 a5 a7 a9 a8,二、拓扑排序算法,1. 算法步骤(1) 在AOV网中，选取一个没有前驱的顶点输出；(2) 删除该顶点和所有以它为弧尾的弧；(3) 重复以上两步，直到AOV网中全部顶点都已输出（得到拓扑有序序列）或者，图中再无没有前驱的顶点（AOV网中有环）,二、拓扑排序算法,如何实现算法中的(1)和(2)？对于(1)，没有前驱的顶点即入度为0的顶点；对于(2)，删除以它为弧尾的所有弧，即让该顶点的所有直接后继的入度减1。,由此分析知：拓扑排序算法的实现与顶点的入度有密切关系，因此，在选取存储结构时，应考虑： 能容易得到各顶点的入度； 有利于寻找任一顶点的所有直接后继。为此，采用邻接表作为AOV网的存储结构，并在头结点中增加一个存放顶点入度的域（indegree）,二、拓扑排序算法,FUNC toposort(VAR dig: adjlisttp; n, e: integer): Boolean; crt_adjlist(dig); 建邻接表 INIT(top); FOR i:=1 TO n DO IF digi.indegree=0 THEN PUSH(top，i); 所有入度为0的入top栈 m:=0;计数变量初值为0 WHILE NOT EMPTY(top) DO j:=POP(top); write(digj.vexdata); m:=m+1; q:=digj.firstare;设置移动指针 WHILE q NIL DO k:=q. adjvex; digk. indegree:=digk.indegree-1; IF digk.indegree=0 THEN PUSH(top, k); 入度减为0的顶点入栈 q:=q.nextarc ; IF m vek THEN vek:=vej+dut(); k:=NEXTADJ(dig, j, k) IF mn THEN RETURN(false) ELSE RETURN(true)ENDF; toporder,五、关键路径算法,PROC critical_path(VAR dig: adjlisttp); crt_adjlist(dig); IF NOT toporder(dig) THEN write(“有回路”) ELSE vl1.n:=ven; WHILE NOT empty(top2) DO j:=pop(top2); k:=FIRSTADJ(dig, j); WHILE k0 DO IF vlk-dut(); k:=NEXTADJ(dig, j, k) FOR j:=1 TO n DO 求ee 和 el，及关键活动 k:=FIRSTADJ(j); WHILE k0 DO ee:=vej; el:=vlk-dut(); IF ee=el THEN tag:=* ELSE tag:= ; writeln(j, k, dut(), ee, el, tag); k:=NEXTADJ(dig, j, k) ENDP; critical_path,7.7 最短路径在有向图中，寻找从某个源点到其余各个顶点或者每一对顶点之间的最短带权路径的运算，称为最短路径问题,一、某个源点到其余各顶点的最短路径算法迪杰特拉（Dijkstra） 算法：算法思想：按路径长度递增的次序产生到各顶点的最短路径使用DS：利用带权邻接矩阵cost表示当前找到的从源点V0到每个终点Vi的最短路径长度的辅助向量disti存储最短路径的向量pathi表示已找到从V0出发的最短路径的终点的集合S,7.7 最短路径,算法步骤：1. 用cost 初始化dist；置S=V0；2. 选择Vj,使得：distj=Mindisti|ViV-S Vj 就是当前求得的从V0出发的最短路径的终点，并将Vj并入S；3. 对V-S上的所有顶点Vk，修改： distk=Mindistj+costj, k, distk4. 重复2，3， n-1次。,7.7 最短路径,例子,终点 从v0 到各终点的 dist 值和最短路径,v1,v2,v4,v3,v5,vj,7.7 最短路径,PORC shortpath_DIJ(da.cost:adjmatrix; v:vtxptr; VAR dist:ARRAYvtxptr OF weightype; VAR path:ARRAYvtxptr OF set); FOR i:=1 TO vtxnum DO disti:=da.costv, i; IF distimax THEN pathi=v+i 集合并 ELSE pathi:= ; 空集 S:=v; FOR k:=1 TO vtxnum-1 DO wm:=max; j:=v; FOR i:=1 TO vtxnum DO 选取vj=MindistI|vi V-S IF NOT (i IN S) AND (distiwm) THEN j:=i; wm:=disti ; S:=S+j; FOR i:=1 TO vtxnum DO IF NOT (i IN S) AND (distj+da.costj, idisti) THEN disti:=distj+da.costj,i; pathi:=pathj+i ENDP;shortpath_DIJ,7.7 最短路径,二、每一对顶点之间的最短路径两种方法：每次以一个顶点为源点，重复调用Dijkstra算法n次； 弗洛伊德算法(Floyed)1.弗洛伊德算法思想：以A(0) i,j=costi,j 递推出：A(k)i,j=MinA(k-1)i,j, A(k-1)i,k+ A(k-1) k,j,1kn其中， Aki,j 表示从 vi到vj 的中间顶点的序号不大于k 的最短路径长度。最后得到的Ani,j就是从vi 到vj 的最短路径长度。,7.7 最短路径,2. Floyed 算法PROC shortpath_Floyed(da.cost:adjmatrix; VAR length:ARRAYvtxptr:vtxptr OF weightype VAR path: ARRAYvtxptr:vtxptr OF set); FOR i: =1 TO vtxnum DO FOR j:=1 TO vtxnum DO lengthi,j:=da.costi,j; IF lengthi, j max THEN pathi,j: