数据结构第七章

1、1第七章 图地图染色北京公交查询系统铺设线路电网输电模拟导游系统 V5 V01006030102010550 V1 V2 V3 V42第七章 图图的定义图的存储结构图的遍历图的应用最小生成树最短路径拓扑排序关键路径 V5 V01006030102010550 V1 V2 V3 V43 图图是由一个是由一个顶点集顶点集 V 和一个和一个弧集弧集 R构成构成的数据结构。的数据结构。 Graph = (V, R )其中，VR| v,wV 且 P(v,w) 表示从 v 到 w 的一条弧，并称 v 为弧尾弧尾，w 为弧头弧头。4 由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图有向图。EACB

2、D例如例如: :G = (V，VR)其中V=A, B, C, D, EVR=, , , , , , 5若VR 必有VR, 则称顶点v 和顶点w 之间存在一条边，用边，用(v,w)表示。BCAFED由顶点集和边集构成的图称作无向无向图图。例如: G2=(V2,VR2)V2=A, B, C, D, E, FVR2=(A, B), (A, E), (B, E), (C, D), (D, F), (B, F), (C, F) 6ABECDAEDBBC设图G=(V,VR) 和图 G=(V,VR),且 VV, VRVR,则称 G 为 G 的子子图图。1597211132 弧或边带权的图分别称作有向有向网网

3、或无向网无向网。7假设图中有 n 个顶点，e 条边，则 含有 e=n(n-1)/2 条边的无向图称作完全图完全图; 含有 e=n(n-1) 条弧的有向图称作 有向完全图有向完全图; 若边或弧的个数 enlogn，则称作稀疏图稀疏图，否则称作稠密图稠密图。8 假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点邻接点，例如例如: :D(B) = 3D(A) = 2 边(v,w) 和顶点v 和w 相关联关联。顶点顶点v的度：的度：与顶点与顶点v v相相关联的边的数目边的数目。ACDFEB右侧图中9顶点的出度出度: : 以顶点v 为弧尾的弧的数目;ABECD对对有向图有向图来说来说，顶

4、点的入度入度: : 以顶点v为弧头的弧的数目顶点的度度( (D)=)=出度出度( (OD)+)+入度入度( (ID) )例如例如: :ID(B) = 2OD(B) = 1D(B) = 3由于弧有方向性，则有入度入度和出度出度之分10设图G=(V,VR)中的一个顶点序列 u=vi0,vi1, , vim=w中，(vi,j-1,vi,j)VR 1jm,则称从顶点u 到顶点w 之间存在一条路径路径。路径上边的数目称作路径长度路径长度。ABECD如如:从A到D长度为 3 的路径A,B,C,D简单路径简单路径:指序列中顶点不重复出现的路径。简单回路简单回路:指序列中第一个顶点和最后一个顶点相同的路径。1

5、1若图G中任意两个顶点之间都有路径相通，称此图为连通图连通图若无向图为非连通图，则图中各个极大极大的连连通通子图子图称作此图的连连通分量通分量。BACDFEBACDFE12 若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图强连通图。ABECDABECD对有向图，对有向图，否则，其各个强连通子图称作它的强连通分量强连通分量BCDAE13BACDFE 假设一个连通图连通图有 n 个顶点和 e 条边，其中n-1 条边和n 个顶点构成一个极小连极小连通子图通子图，称该极小连通子图为此连通图的生成树生成树。对非连通图非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林生成森林。B

6、ACDFEBACDFEBACDFE14一一. 图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示二二. 图的邻接表存储表示图的邻接表存储表示三三. 有向图的十字链表存储表示有向图的十字链表存储表示 四四. 无向图的邻接多重表存储表示无向图的邻接多重表存储表示五五. 边集数组表示边集数组表示15用来表示图中用来表示图中顶点间顶点间相邻关系相邻关系的矩阵的矩阵网的邻接矩阵如何表示？网的邻接矩阵如何表示？Aij=0 (vi ,vj)VR1 (vi ,vj)VRAij= (vi ,vj)VRwij (vi ,vj)VRBACDFE01234501001010001100010100100111000

7、0011100 邻接矩阵的定义邻接矩阵的定义16ABECD1597211132有向图的邻接矩阵有向图的邻接矩阵有向网的邻接矩阵有向网的邻接矩阵ABECD012340 1 0 0 10 0 1 0 00 0 0 1 0110 0 00 0 1 0 0 15 9 3 211 7 21 171) 当图的各顶点的序号确定后，其邻接矩阵是唯一确定的；2) 无向图和无向网的邻接矩阵是一个对称矩阵；3) 无向图的邻接矩阵中第i行(或第i列)的非零元个数为第i个顶点的度； 邻接矩阵的性质邻接矩阵的性质4)有向图的邻接矩阵中第i行非零元个数为第i个顶点的出度，第i列非零元个数为第i个顶点的入度；5) 无向图的边

8、数等于矩阵中非零元个数的一半，有向图的弧数等于矩阵中非零元的个数。1() njD ViA ji1() njD ViA ij或18图图的邻接矩阵的的邻接矩阵的C语言描述语言描述#define VNUM /图中顶点的最大数目图中顶点的最大数目typedef struct VertexType vexsVNUM； / 定义顶点定义顶点 int arcsVNUMVNUM； / 定义边（弧定义边（弧） int vexnum, arcnum; / 顶点数，弧数顶点数，弧数 Graph ；/定义图定义图网网的邻接矩阵的的邻接矩阵的C语言描述语言描述#define VNUM /图中顶点的最大数目图中顶点的最大

9、数目typedef struct VertexType vexsVNUM； / 定义顶点定义顶点 WeightType arcsVNUMVNUM； int vexnum, arcnum; / 定义边的权值定义边的权值 NetGraph ； /定义网定义网顶点的信息顶点的信息：用一维数组一维数组来存储。边的信息边的信息： 用邻接矩阵邻接矩阵来存储。 图的图的邻接矩阵邻接矩阵存储方式存储方式19例：已知一个无向图，建立其存储结构。例：已知一个无向图，建立其存储结构。void crt_gragh(Gragh &ga ) scanf(&ga.vexnum，&ga.arcnum)

10、；/顶点数和边数顶点数和边数 for(i=0；iga.vexnum；i+) scanf(&ga.vexsi)； for(i=0；iga.vexnum；i+) for(j=0；jga.vexnum；j+ ) ga.arcsij=0； for(k=0；k arcnum ；k+) scanf(&i，&j)； / 读入一条边读入一条边 ga.arcsi-1j-1=1； ga.arcsj-1i-1=1 /crt_gragh 20已知一个有向网，建立其存储结构已知一个有向网，建立其存储结构。void crt_net(NetGraph &ga) scanf(&ga.v

11、exnum，&ga.arcnum)；/ 顶点数和弧数顶点数和弧数 for(i=0；iga.vexnum；i+) scanf(ga.vexsi)； for(i=0；iga.vexnum；i+) for(j=0；jga.vexnum；j+ ) ga.arcsij= MAXINT； for(k=0；kga.arcnum；k+) scanf(&i，&j，&w)； / 读入一条弧和弧上的权值读入一条弧和弧上的权值 ga.arcsi-1j-1= w ； /crt_net 21 邻接矩阵的特点邻接矩阵的特点(1) 邻接矩阵可以采用压缩存储方法邻接矩阵可以采用压缩存储方法 无向

12、图和无向网的邻接矩阵为对称矩阵;对于边(弧)个数较少的稀疏图,其邻接矩阵也稀疏，用行主序存储矩阵时存储空间利用率低。(2) 操作特点操作特点 其存储特点是一种顺序存储结构。其存储特点是一种顺序存储结构。 较为适合操作有：较为适合操作有： 计算顶点的度；求一个顶点的所有邻接点；插入或删除一条边(弧)等； 不太适合的操作有：不太适合的操作有： 顶点的插入和删除；图的遍历等。22方法：方法： 对图中对图中每个顶点每个顶点建立一个有建立一个有邻接关系邻接关系的顶点的顶点单链表单链表 顶点邻接表顶点邻接表； (2) 用一个用一个数组数组存各邻接表的头结点存各邻接表的头结点(顶点结点顶点结点) 对于无向图

13、无向图：第 i 个链表是与Vi相邻接的所有邻接点构成的单链表； 对于有向图有向图：第 i 个链表是以Vi为弧尾的所有弧头结点构成的单链表； data firstarc顶点的结点顶点的结点顶点信息顶点信息 头指针头指针adjvex nextarc info邻接表结点邻接表结点( (边结点边结点) )邻接点编号邻接点编号 指针指针 边的权值边的权值23typedef struct ArcNode int adjvex； / 该弧所指向的顶点的位置 struct ArcNode *nextarc； / 指向下一条弧的指针 InfoType info； / 该弧相关信息 ArcNode ，*ArcPo

14、inter；邻接表的组织：邻接表的组织：typedef struct VertexType vexdata；/顶点信息顶点信息 ArcPointer firstarc；/出边头指针，指向第一条出边出边头指针，指向第一条出边 VexNode；typedef struct VexNode adjlistVnum； / 邻接表 int vexnum，arcnum；/有向图的当前顶点数和弧数 AdjGraph24vexdata firstarc顶点结点无向图的邻接表无向图的邻接表 adjvex nextarc弧结点BACDFE012345102030405060704 1012345ABCDEF35

15、25 01 123 045 无向无向网网的邻接表的邻接表 adjvex info nextarc已知图的邻接表，如何求无向图中的顶点vi的度?无向图中边的个数？1 104 30 4 505 20 0 103 605 40 2 403 70 1 200 301 50 2 605 70 25A B C D E 012340 1 2 3 4 A B C D E3 30 2 0 有向图的邻接表有向图的邻接表有向图的有向图的逆逆邻接表邻接表如何求有向图中弧的个数?如何求有向图中顶点vi的出度和入度？1 4230 1241 ABECD0123426有向图的邻接表：有向图的邻接表：0 1 2 3 4 A B

16、 C D E1 4230 12ABECD01234如何生成有向图的邻如何生成有向图的邻接表结构？接表结构？读入图的信息：读入图的信息：顶点信息顶点信息：A B C D E弧弧(或边边)的信息: 例如例如：0，10，41，22，33，03，14，227建立有向图的邻接表的算法：建立有向图的邻接表的算法：void build_adjlist(AdjGraph &gb) scanf(&gb.vexnum， &gb.arcnum)；/顶点个数和弧数顶点个数和弧数 for(i=0；igb.vexnum；i+) scanf(gb.adjlisti.verdata)； gb.adjl

17、isti.firstarc= NULL； for(k=0；k gb.arcnum ；k+) scanf(&i，&j)； / 读入一对顶点序号读入一对顶点序号 p=(ArcPointer)malloc(sizeof(ArcNode)； padjver =j； / 生成结点生成结点 pnextarc= gb.adjlisti.firstarc； gb.adjlisti.firstarc = p； / build_adjlist 问：如何建立无向问：如何建立无向图的邻接表？图的邻接表？281) 图的邻接表的表示不是唯一的，它与邻接点的读入顺序有关；2) 无向图邻接表中第i个单链表中结

18、点个数为第i个顶点的度；3) 有向图邻接表中第i个单链表中结点个数为第i个顶点的出度；其逆邻接表中第i个单链表中结点个数为第i个顶点的入度； 邻接表的性质邻接表的性质4) 无向图的边数为邻接表中结点个数的一半，有向图的弧数为邻接表中结点个数。29 邻接表的特点邻接表的特点 存储特点：存储特点： 是一种顺序是一种顺序+ +链式的存储结构，链式的存储结构，当图中顶点个数较多，而边比较少时，可节省大量的空间。较为适合操作有：较为适合操作有： 计算顶点Vi的出度；求一个顶点的所有邻接点；插入或删除一条边(弧)；求顶点的一个邻接点的下一个邻接点等；不太适合的操作有：不太适合的操作有： 顶点的插入和删除；

19、顶点的入度等。30链表结点链表结点边起点 边终点边终点 下一入边入边指针 下一出边出边指针弧的权值tailvex headvexhlinktlinkinfo是有向图有向图的邻接表和逆邻接表结合结合起来得到的一种链表。表头结点表头结点顶点信息 入边头指针入边头指针 出边头指针datafirstinfirstout31typedef struct VexNode / 定义顶点定义顶点(头头)结点结点 VertexType data； ArcNode *firstin，*firstout； VexNode；typedef struct ArcBox / 定义定义弧弧结点结点 int tailvex，

20、 headvex； struct ArcBox *hlink， *tlink； InfoType info； ArcNode；十字链表的组织：十字链表的组织：32#define Vnum 20typedef struct VexNode ortholistVnum； /顶点(表头)结点数组 int vexnum，arcnum； /有向图的当前顶点数和弧数 OlGraph；有向图的结构表示有向图的结构表示(十字链表十字链表)33ABC2 02 10 20 1弧头相同弧头相同012读入弧： (0,1)、(0,2)、(2,0)、(2,1)弧尾相同弧尾相同 tailvex headvex hlink

21、tlink弧结点弧结点data firstin firstout顶点结点顶点结点ABC01234ivex ilink jvex jlink边结点边结点 ilink：指示下一条依附于顶点ivex的边。 jlink：指示下一条依附于顶点jvex的边。 data： 存储和该顶点相关的信息。 firstedge：指示第一条依附于该顶点的边 data firstedge顶点结点顶点结点354 12 42 32 10 30 1 例：对于无向图，例：对于无向图，读入顺序如下读入顺序如下边结点边结点:0 V01 V1 2 V2 3 V3 4 V4V0V1V2V3V4(0,1)；(0,3)；(2,1)；(2,3

22、)；(2,4)；(4,1)。ivex ilink jvex jlink36typedef struct ENode int ivex，jvex； / 顶点序号顶点序号 struct enode *ilink，*jlink； ENode；typedef struct VNode DataType data； / 顶点信息顶点信息 ENode *firstedge；/ 指向第一条依附于该顶点的边结点指向第一条依附于该顶点的边结点 VNode； / 定义头结点定义头结点 typedef struct VNode adjmulistVnum； int vexnum，edgenum； / 图的当前顶点数

23、和边数图的当前顶点数和边数 AMLGrahp； 37方法：方法：用一个一维数组存储顶点信息；用一个一维数组存储顶点信息；用一个一维数组存图中所有的边用一个一维数组存图中所有的边, 数组规模数组规模图边数；图边数；每个数组元素存一条边的起点、终点、权值，次序任意每个数组元素存一条边的起点、终点、权值，次序任意 无向图，边起点可以任意选定；无向图，边起点可以任意选定；无权图，省去权值存储无权图，省去权值存储 边集数组边集数组: 12 3bacA12 3BC12 1646123112起点起点.233终点终点.1234起点起点1123终点终点2332权值权值121646适合：适合：对边依次处理的运算对

24、边依次处理的运算38遍历：遍历：从某顶点出发, 按一定搜索方法,不重复访问所有顶点。367984125问题：问题：可能存在多条路径都能到达同一顶可能存在多条路径都能到达同一顶点。点。即要解决顶点的重复访问。解决办法：解决办法：对已访问过的顶点做标记。设辅助数组: int visitedn；来记录每个顶点是否被访问过。访问过为1，否则为0。397.3.1 连通图的深度优先搜索连通图的深度优先搜索(Depth-First Search) 访问顶点的次序： V3V2 V4V9V1V6 V5V8V7深度优先遍历：深度优先遍历： 访问出发点V0； 任选一个出发点的一个没被访问过的邻接点，以该点出发深度优

25、先遍历深度优先遍历； 重复，直到V0没有邻接点没被访问；36798412540连通图的深度优先遍历的连通图的深度优先遍历的逻辑算法逻辑算法：void df_traver(gragh g，int v) /从从v号顶点出发，深度优先遍历连通图号顶点出发，深度优先遍历连通图 g printf(v)； visitedv=1；for(w=FirstAdjVex(g, v); w; w=NextAdjVex(g, v, w) if(visitedw=0) df_traver(g，w)； / dfs 41typedef struct ArcNode int adjvex； / 该弧所指向的顶点的位置 str

26、uct ArcNode *nextarc； / 指向下一条弧的指针 ArcNode ，*ArcPointer；邻接表的组织：邻接表的组织：typedef struct VertexType vexdata；/顶点信息顶点信息 ArcPointer firstarc；/出边头指针，指向第一条出边出边头指针，指向第一条出边 VexNode；typedef struct VexNode adjlistVnum； / 邻接表 int vexnum，arcnum；/有向图的当前顶点数和弧数 AdjGraph42 void df_traver (AdjGraph g，int v)/g的存储结构为邻接表的存

27、储结构为邻接表，v为出发点编号，标志数组已初始化为为出发点编号，标志数组已初始化为0 printf(g.adjlistv.vexdata)； / 访问出发点访问出发点 visitedv= 1； / 做标志做标志 p=g.adjlistv.firstarc； / 找邻接点找邻接点 while (pNULL) w = padjvex； if (visitedw=0) df_traver (g，w)；/ 递归调用递归调用 p=pnextarc； / 找下一个邻接点找下一个邻接点 /dfs 43 从图中的某个顶点V0出发，访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次

28、序依次访问它们的邻接点。7.3.2连通图的广度优先搜索连通图的广度优先搜索(Breadth-First Search) 一层一层二层二层三层三层访问顶点的次序： V3V2V1V6V4V5V9V8V736798412544显然，先被访问的顶点，其邻接点也先被访问. 实现时需要设置一个队列队列，用于记住访问顶点的次序：367984125算法：算法： 1. 将初始顶点号入队；将初始顶点号入队；2. 队列不空，则队列不空，则 队头顶点号出队,访问访问； 依次将其邻接顶点号入队；3.重复重复2，直到队列空，直到队列空，遍历过程结束。45邻接表结构下连通图的广义优先遍历算法：邻接表结构下连通图的广义优先遍

29、历算法：void bf_traver (AdjGraph g，int v0) / 队列队列Q存放已访问过的顶点编号，存放已访问过的顶点编号，v0为出发点编号为出发点编号 InitQueue(Q)； EnQueue(Q，v0)； while (!Qempty(Q) ) v=OutQueue(Q)； printf(g.adjlistv.vexdata)； visitedv=1； p=g.adjlistv.firstarc； while (p NULL) w=padjvex； / 取邻接点编号取邻接点编号 if (visitedw=0) InQueue(Q，w) ； p = pnextarc ； /

30、bfs 46void traver(gragh g) for(v=0；vn；v+) visitedv=0； for(v=0；vn；v+) if (visitedv=0) df_traver(g, v)； /或或bf_travers(g, v) 从图中的某个顶点V0出发深度（广度）优先深度（广度）优先遍历，遍历，之后另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。7.3.3 非连通图的深度非连通图的深度( (广度）优先遍历：广度）优先遍历：47 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前如何在最节省

31、经费的前提下建立提下建立这个通讯网通讯网？问题：问题：48图G中的边集合E(G)分成两个部分:T(G)与与G中中所有顶点所有顶点构成构成G的极小连通子图，的极小连通子图，即是即是G的一棵的一棵生成树生成树。深度优先生成树B(G)：剩余的边集。T(G)：遍历过程中经过的边集遍历过程中经过的边集生成树生成树367984125367984125广度优先生成树49已知一个带权图，求其生成树，使得树中所有边上的权值之和最小权值之和最小。 0 1 3 2 4 5 651536642最常用的算法： 普里姆普里姆(prim)算法算法 卡鲁斯卡尔卡鲁斯卡尔(kruskal)算法算法5014231534250V-

32、UU1. 普里姆普里姆(prim)算法算法 设G=(V, E)是连通图，最小生成树T的顶点集合为U，边的集合是TE。首先：首先：U =u0 (u0 V) ， TE = 重复执行下述操作：重复执行下述操作： 在所有u U， v V-U的边(u，v) E中找一条代价最小的边(ui ，v0)并入集合TE，同时v0并入U，直到 U = V为止。 51abcdegf195141827168213127例如例如: :aedcbgf148531621所得生成树权值和= 14+8+3+5+16+21 = 6752带权图带权图(网网)用邻用邻接矩阵表示接矩阵表示。struct VertexType adjvex

33、； / U集中的顶点 WeightType lowcost; / 边的权值 closedgeVNUM； 最小生成树用一个结构数组数组(closedge)表表示示，数组下标表示图中的顶点序号；对当前VU集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：typedef struct VertexType vexsVNUM; WeightType arcsVNUMVNUM;int vexnum, arcnum; NetGraph ；53 0123456 0 1 2 3 4 5 6closedge0123456AdjvexLowcost a b c d e f gabcdegf19514182

34、7168213127aedcbaaa19141814e12ee8168d3dd7213c5 51621gf 19 14 1819 5 7 12 5 3 7 3 8 21 14 12 8 16 21 2718 16 27 0162453G.arcsij:a b c d e f g0 1 2 3 4 5 6G.vexsi:54void MiniSpanTree_P(NetGraph G, VertexType u) /带权的连通图G的存储结构为邻接矩阵NetGraph， /用普里姆算法从顶点u出发构造网G的最小生成树 k=LocateVex (G, u); /确定起点u在图G中的位置 for (j

35、=0; jG.vexnum; j+) / 辅助数组初始化 if (jk) closedgej. adjvex = u; closedgej. lowcost= G.arcskj ; closedgek.lowcost = 0; / 初始，Uu for (i=0; iG.vexnum; i+) 55 k = minimum(closedge); / 求出加入生成树的下一个顶点(k) printf(closedgek.adjvex, G.vexsk， closedgek.lowcost ); / 输出生成树上一条边 closedgek.lowcost = 0; /第k顶点并入U集 for(j=0;

36、 jG.vexnum; +j) /修改其它顶点的最小边 if (G.arcskj closedgej.lowcost) closedgej.adjvex = G.vexsk; closedgej. lowcost =G.arcskj; /MiniSpanTree_P56设设G=（V， E )是连通图是连通图 将边从小到大排序；将边从小到大排序； 将将n个顶点分成个顶点分成n棵树；棵树； 选最小的一条边（选最小的一条边（u，v)，满，满足足u，v不在同一连通集不在同一连通集 重复，选够重复，选够n-1条边停止；条边停止；（0，2）=1 （1，2）=5（3，5）=2 （2，3）=5（1，4）=3

37、（0，1）=6（2，5）=4 （2，4）=6（0，3）=5 （4，5）=6 0 1 3 2 4 5 651536642 X X二、二、克克鲁斯卡尔鲁斯卡尔(kruskal)算法算法12025314525123457普里姆算法普里姆算法 克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名算法名适应范围适应范围比较两种算法58给定有向图G=(V, E)，G中E上的权值为W(e)；设源点的编号为v0， G的存储结构为邻接矩阵邻接矩阵。 WeightType netNN； V5 V01006030102010550 V1 V2 V3 V4 10 3

38、0 100 5 50 10 20 60 netij=存储存储结构结构:59Dijkstra算法：算法： 按路径长度按路径长度递增递增的次序产生最短路径。的次序产生最短路径。 如源点到其它每一个顶点都有一条最短路径： ( v0， ， v1) ( v0， ， v2) ( v0， ， vn) 在上面的路径中，先求最短的，再求次短的，。首先将网中的所有顶点分成两个集合首先将网中的所有顶点分成两个集合S和和T：S：凡以v0为源点，已经确定了最短路径的终点并入集合S。S的初始状态只包含v0。T：尚未确定最短路径的顶点的集合。其初始状态包含除源点外的所有顶点。60引进两个辅助数组来记源点(设其编号为v0)到

39、其它顶点的最短路径长度路径长度和路径集合路径集合。 disti：表示v0到顶点vi的最短路径的长度。 pathi: 表示以上路径中所经过的顶点集合其初始状态为： disti = netv0i ； pathi= v0, i，当E ，否则 初始时S=v0，以后不断地修改以后不断地修改S和和disti：设第一条最短路径为(v0，vj):则 distj=min disti |viT，此时 S=v0，j61假设下一条次短路径的终点是vk，则这条路径或者是(v0，vk)， 或者是(v0，vj，vk)。所以有必要修改v0号顶点到除j号顶点以外其它顶点的距离，即修改disti(iT)disti=minnetv

40、0i，distj+netjijS,iT重复执行下述操作，直到选够重复执行下述操作，直到选够n-1条路径：条路径：（1）设下一条所选路径的终点为vk ，则：distk= mindistiiT，将k加入到S中。（2）修改disti iTdisti=mindisti，distk+netkikS，iT 62 v1 v2 v3 v4 v5 入选入选S的点的点disti 10 30 100pathi (v0,v2) (v0,v4) (v0,v5) 10 30 100 5 50 10 20 60 netij=从从v0出发出发 10(v0,v2)disti / 60 30 100 pathi (v0,v2,v

41、3)disti / 50 / 90pathi (v0,v4,v3) (v0,v4,v5) disti / / / 60pathi (v0,v4,v3,v5) 30(v0,v4) 50(v0,v4,v3) 60(v0,v4,v3,v5)v2v4v3v5 V5 V01006030102010550 V1 V2 V3 V463存储结构：存储结构：Adjmatrix netnn； 存储有向网的邻接矩阵。WeightType distn； disti: 存储v0到vi的路径长度。int insetn；若vi在顶点集合S中，则inseti=1，否则inseti=0；初始时：insetv0=1，其它为0。i

42、nt pathnn；二维数组二维数组； pathi是一维数组，存储源点v0到各顶点vi的最短路径，若若pathik=1，表示，表示vk在该路径中。在该路径中。0 0 0 0 0 00 0 0 0 0 01 0 1 0 0 01 0 0 1 1 01 0 0 0 1 01 0 0 1 1 10 1 2 3 4 5p0p1p2p3p4p564void shortpath(Adjmatrix net， int v0， WeightType &distn，int &pathnn) for (i=0；in；i+) / dist、inset、path初始化初始化 disti= netv0i

43、； inseti=0； /所有顶点都不在所有顶点都不在S中中 pathi0.n-1=0；/所有所有pathi为空路径为空路径 if(distiMAXINT) pathiv0=1；pathii=1； /如果如果disti ,让让pathi=v0，vi ； / 初始化完成初始化完成 insetv0=1；/初始化集合初始化集合S=v065for(k=0；kn；k+) / 构造至多构造至多n-1条路径条路径 min= MAXINT； j=v0； / 初始化一个最短路径长初始化一个最短路径长 for(i=0；in；i+) /找入选点及找入选点及min值值 if(inseti=0 & distim

44、in) j=i； min=distj ；/min=mindisti, iT if(jv0) insetj=1；/ S=S+j for(i=0；in；i+) / 修改修改disti, iT if( inseti=0 & (distj+netjidisti) disti=distj + netji； pathi0.n-1= pathj0.n-1； pathii=1； / pathi=pathj+i / end_for k /shortpath T(n)= O(n2)66一个解决办法是：每次以一个顶点为源点，重复执行dijkstra算法n次。 T(n) = O(n3)另一算法：另一算法：由F

45、loyd提出, T(n) = O(n3)，但形式较简单形式较简单存储结构仍使用邻接矩阵存储结构仍使用邻接矩阵net。为了描述简单，设顶点的编号从1n；邻接矩阵数组的下标也从1n。67若存在，则存在路径vi,vj / 路径中不含其它顶点若,存在，则存在路径vi,v1,vj / 路径中所含顶点序号不大于1若vi,v2, v2,vj存在， 则存在一条路径vi, , v2, vj / 路径中所含顶点序号不大于2 依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。68设二维数组设二维数组A来存储任一对顶点的最短路径长度，来存储任一对顶点的最短路径长度，开始时，开始时，Aij的值

46、取的值取netij的值的值。 将A记为A(0) 。要进行要进行n次试探次试探。(1)对每一条路径，先考虑让路径经过顶点v1，比较路径和+ 的长度，取其短者为当前求得的最短路径长度，记为A(1)。称为中间点序号不大于中间点序号不大于1的最短路径(2)在A(1)的基础上让路径经过顶点v2，可求得A(2) 称为中间点序号不大于中间点序号不大于2的最短路径。 (n)在A(n-1)的基础上让路径经过顶点vn，可求得A(n) 69序列序列A(k)ij（k=1，2，n)的求法：的求法：假设已知A(k-1)ij，分两种情况： 顶点vi到顶点vj的最短路径不通过中间点中间点vk， 则: A(k)ij= A(k-

47、1)ij (2) 顶点vi到顶点vj的最短路径经过中间点中间点vk ， 则: 该路径由 + 组成，此时应修改A(k)ij为 A(k-1)ik + A(k-1)kj A(0)ij = netij A(k)ij=minA(k-1)ij，A(k-1)ik+A(k-1)kj其中：A(i)ij= A(i-1)ij；A(j)ij=A(j-1)ij； A(k)ii = A(0)ii（k=1，2，n)70A(0) = 1 4 9 2 3 5 8 6 A(3)= 1 10 3 12 9 2 3 4 6 9 10 6 A(2)= 1 10 3 9 2 3 4 6 6 A(4)= 1 9 3 11 8 2 3 4

48、6 9 10 6 A(1)= 1 4 9 2 3 4 7 6 31954862例： v3 v4 v1 v271void floyd(AdjMatrix net，PathMatrix &path ，DistancMatrix &a)/i和和j之间的最短路径为之间的最短路径为pij，最短路径长为，最短路径长为aij；若；若/pijk为为TRUE，则，则k是从是从i到到j当前求得最短路径上的顶点当前求得最短路径上的顶点for(i=0；in；i+) for(j=0；jn；j+) aij= netij； for(k=0；kn；k+)pijk=FALSE； if (aijMAXINT) p

49、athiji=TRUE；pathjkk=TRUE； 72for (k=0；kn；k+) for (i=0；in；i+) for (j=0；jn；j+) if (aik+akjaij) aij=aik+akj； for (t=0；tn；t+) / pathi,j=pathi,k+pathk,jpjkt=pjit | pjkt； / floyd 73有向无环图有向无环图(directed acycline graph)：以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。a1a10a4a7a8a2a5a3a11a6a974一一. .拓扑排序问题的提出拓扑排序问题的提出 在现实世界中

50、,一项大的工程通常有若干个子工程构成，这些子工程和主工程的关系可以用有向图来描述。子工程称为活动(Activity)，活动之间经常存在先后的次序关系。a1a10a4a7a8a2a5a3a11a6a975 在一个有向图中如果用顶点表示活动顶点表示活动，用弧表示活动间优先关系弧表示活动间优先关系，该图称为用顶点表示活动的网 (Activity On Vertex Network) ， 简称AOV_网。网。i是j的前驱前驱，j是i的后继后继； i是k的直接前直接前驱驱，k是i的直接后继直接后继。 i k j 二二. AOV_网网76三三. 拓扑序列的定义拓扑序列的定义 设图G是一个具有n个顶点的有向

51、图，包含图G的所有n个顶点的一个序列：Vi1,Vi2,Vin，当满足下面条件时该序列称为G的一个拓扑序列拓扑序列：当在图G中，从顶点Vi到顶点Vj有一条路径时，在序列中Vi必须排在Vj的前面。构造拓扑序列的过程称为构造拓扑序列的过程称为拓扑排序拓扑排序。77例如：在如下的AOV_网中：序列：v1v3v2v4v5v6v7 是一个拓扑序列；序列：v2v1v3v5v4v7v6 也是一个拓扑序列；v3v1v2v4v5v6v7 程序设计程序设计 汇编汇编语言语言 信息技术信息技术 数据结构数据结构 编译原理编译原理 离散数学离散数学 操作系统操作系统78例如：对于下列有向图BDAC可求得可求得拓扑有序序

52、列拓扑有序序列： A B C D 或或 A C B D对于下列有向图：对于下列有向图：BDAC不能求得它的拓扑不能求得它的拓扑有序序列。有序序列。存在一个回路存在一个回路 四四. .拓扑序列的特点拓扑序列的特点1) 一个有向图的拓扑序列一般不唯一。一个有向图的拓扑序列一般不唯一。2) 有向无环图一定存在拓扑序列。有向无环图一定存在拓扑序列。79五五. 拓扑排序的算法描述拓扑排序的算法描述如果顶点没有全部输出，且当前图中不存在无前驱的顶点，则说明有向图中存在环(1) 在有向图中选一个没有前驱的顶点且输出；(2) 从图中删除该顶点以及以该顶点为弧尾的所有弧； 重复上述两步，直至全部顶点均已输出。8

53、0V1V2V3V4V5V6V2V3V4V5V6V2V3V4V5例(a)输出 V1(b) 输出V6(c)输出V4V2V3V5(d) 输出V3V2V5 (e) 输出V2或V5拓扑序列：拓扑序列：V1 V6 V4 V3 V2 V5V1 V6 V4 V3 V5 V2 V6 81邻接表存储结构中实现拓扑排序的算法邻接表存储结构中实现拓扑排序的算法可用可用加了入度域加了入度域(id)的头结点的的头结点的邻接表邻接表来存储有向图。来存储有向图。弧的读入顺序如下弧的读入顺序如下(0，1) 、(0，2)、(0，3)、(2，1)、(2，4)、(3，2)、(3，4)、(5，3)、(5，4)用一个顺序栈存放入度为用一

54、个顺序栈存放入度为0的顶点序号。的顶点序号。 顶点顶点 入度入度 指针指针 0 V0 0 3 2 1 1 V1 2 2 V2 2 4 1 3 V3 2 4 2 4 V4 3 5 V5 0 4 3 V0V1V4V3V4V5821、逻辑算法：、逻辑算法： InitStack(s)； 将所有入度为零的顶点的栈 ； m = 0； / m记已输出顶点的个数记已输出顶点的个数 while (!Empty(s) v= Pop(s)； printf(v)； m=m+1； w = FirstAdjvex(g，v)； while (w存在) 入度(w)=入度(w)-1； if (入度(w)= 0) push(s，

55、w)； w = NextAdjvex(g，v，w) if (mn) return ERROR；/ 该图有回路该图有回路 else return OK； 832、邻接表结构下的算法：、邻接表结构下的算法：typedef struct arcnode int adjvex； / 邻接点位置邻接点位置 struct arcnode *nextarc； /下一个弧结点指针下一个弧结点指针 ArcNode，*ArcPointer；typedef struct DataType vexdata ； / 顶点类型顶点类型 int id； / 入度入度 ArcPointer firstarc； / 头指针头指

56、针 VexNode；typedef struct VexNode adjlistVnum； / 邻接表邻接表 int vexnum，arcnum； /有向图的当前顶点数和弧数有向图的当前顶点数和弧数 AdjGraph84status top_sort(AdjGraph g) InitStack(s)； m = 0； / 初始化顺序栈初始化顺序栈s for(i=0；ig.vexnum；i+)if(g.adjlisti.id=0) Push(s，i)； while (! Empty(s) v=Pop(s)； printf(g.adjlistv.vexdata)； m=m+1； p= g.adjli

57、stv.firstarc； while(pNULL) w = padjvex ； g.adjlistw.id-； if(g.adjlistw.id =0) Push(s，w)； p = pnextarc； if (mn) return ERROR；else return OK； / top_sort85 顶点顶点 入度入度 指针指针 0 V0 0 3 2 1 1 V1 2 2 V2 2 4 1 3 V3 2 4 2 4 V4 3 5 V5 0 4 3 先先输出输出 v5栈栈s 5 0按topsort算法得到的拓扑序列为：V5、V0、V3、V2、V1、V4。1201110003 2 41V0V1

58、V4V3V4V586 AOE_网(activity on edge)：在对工程进度进行管理时，往往用顶点表示往往用顶点表示事件事件，弧表示，弧表示活动活动，弧上的权表示活动持续的时间，这种网称为AOE网。12a1=6a4=1a2=4a3=5a5=1a6=2a9=4a11=4a7=9a10=2a8=7源点源点汇点汇点968753487(1) 完成整项工程至少要花多少时间？完成整项工程至少要花多少时间？整个工程完成的时间为整个工程完成的时间为：从有向图的：从有向图的源点源点到到汇点汇点的最长路径。的最长路径。abcdefghk64521187244源点源点汇点汇点6174(2) 哪些活动是影响工程

59、进度的关键？哪些活动是影响工程进度的关键？关键路径关键路径：路径长度最长最长的路径。关键活动关键活动：关键路径上的所有活动。88事件事件Vi的最早发生时间的最早发生时间：从源点源点到Vi的最长路径长度最长路径长度。ViV1 . . .l(i) - e(i): 完成活动完成活动ai的的余量余量。jkai 定义定义 当当e(i)=l(i)时，活动时，活动ai为为关键活动。关键活动。定义定义 e(i) 活动活动ai的的最早最早(early)开始时间。开始时间。 l(i) 活动活动ai的的最迟最迟(late)开始时间。开始时间。 也是也是以以Vi为尾的弧为尾的弧所表示的所表示的活动活动的的最早开始时间

60、最早开始时间 其中：ai 89可知Ve(j)是以Vj为弧尾的活动ai的最早开始时间 即: Ve(j)=e(i) weight() ：活动ai的持续时间。 “事件事件j(顶点顶点)” 的的 最早最早发生时间发生时间 Ve(j)Ve(j) = 从源点到顶点从源点到顶点j的的最长最长路径长度路径长度;“事件事件k(顶点顶点)” 的的 最迟最迟发生时间发生时间 Vl(k) Vl(k) = 从顶点从顶点k到汇点的到汇点的最短最短路径长度路径长度;jkweight第第i i项活动项活动aiVe(j)Vl(k)e(i)，l(i) 定义定义 90假设第 i 条弧为 “活动活动ai(弧弧)”的 最早开始时间 e(i) e(i) = Ve(j)；“活动活动ai(弧弧)”的 最迟开始时间 l(i) l(i) = Vl(k) weight() ；jkai 事件发生时间的计算公式