7第七章-图120张课件

☞7.1图的定义和基本术语7.2图的存储结构7.3图的遍历7.4图的生成树7.5拓扑排序7.6关键路径7.7最短路径第七章图☞7.1图的定义和基本术语第七章图1图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对图的定义和术语【例】157324G16V(G1)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}图(Graph)——图G是由两个集合V(G)和E(G)组成的2无向图

——无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集

E(G)是边的有限集合，边是顶点的无序对，记为

（v,w）或（w,v)，并且（v,w)=(w,v)简单的图：图中不包含顶点到其自身的弧或边，同一条弧或边不在图中重复出现有向图&无向图

有向图——有向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集

E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为<v,w>，v,w是顶点，v为弧尾，w为弧头无向图——无向图G是由两个集合V(G)和E(G)组成的简3【有向图G2】245136G2V(G2)={1,2,3,4,5,6}E(G2)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}【有向图G2】245136G2V(G2)={1,2,3,4权

——与图的边或弧相关的数网——带权的图叫~1452375318642G3子图

——如果图G(V,E)和图G’(V’,E’),满足：V’VE’E则称G’为G的子图356245136图与子图无向图&有向图&无向网&有向网UDGDGUDNDN权——与图的边或弧相关的数网——带权的图叫~145235有向完全图

——n个顶点的有向图最大边数是n(n-1)入度：以该顶点为头的弧的数目顶点的度无向图中，顶点的度为与每个顶点相关联的边数有向图中，顶点的度分成入度与出度出度：以该顶点为尾的弧的数目bac有向完全图bac无向完全图无向完全图

——n个顶点的无向图最大边数是n(n-1)/2邻接点——无向图G(V,E)中，如果边(u，v)∈E，则称顶点u，v互为邻接点，或者称顶点u，v相关联有向完全图——n个顶点的有向图最大边数是n(n-1)入度6【例】245136G2顶点2入度：1出度：3顶点4入度：1出度：0【例】157324G16顶点5的度：3顶点2的度：4G2中{1，2，3，5，6}是一条路径G1中{1，2，5，7}是一条路径例如路径

——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足

(Vij-1,Vij)E（1<jn)【例】245136G2顶点2入度：1出度：3【例】17路径长度——路径上边或弧的数目或沿路径各边权值之和回路——第一个顶点和最后一个顶点相同的路径简单路径——序列中顶点不重复出现的路径简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路aegcbfG1d{a，b，e，d}路径长度是3bdeacfG2{a，b，c，e}是一条路径路径长度——路径上边或弧的数目或沿路径各边权值之和回路——第8连通——无向图从顶点v到顶点w有一条路径，则说v和w是连通的连通图——无向图中任意两个顶点都是连通的叫连通图连通分量——无向图的极大连通子图叫连通分量【连通图】bdeacfbdeacf【有2个连通分量的无向图】连通——无向图从顶点v到顶点w有一条路径，则说v和w是连通的9强连通分量——有向图的极大强连通子图叫强连通分量强连通图——有向图中，如果对每一对顶点间都存在路径，则称G强连通图

【强连通图】ABC

【有2个强连通分量的有向图】ABCDE强连通分量——有向图的极大强连通子图叫强连通分量强连通图——10【例】157324G26【例】245136G1路径：1，2，3，5，6，3路径：1，2，5，7，6，5，2，3简单回路：3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：1，2，3，1路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1【例】157324G26【例】245136G1路径：1，2，117.1图的定义和基本术语

☞7.2图的存储结构7.3图的遍历7.4图的生成树7.5拓扑排序7.6关键路径7.7最短路径第七章图7.1图的定义和基本术语第七章图127.2.1邻接矩阵7.2.2邻接表7.2.3十字链表7.24邻接多重表7.2图的存储结构7.2.1邻接矩阵7.2图的存储结构13邻接矩阵——表示顶点间相联关系的矩阵例G22413例15324G1

定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵úúúúúûùêêêêêëé0001100000000110úúúúúúúûùêêêêêêêëé00110001011101010101010101A[i,j]=0若(vi,vj)或<vi,vj>E其它邻接矩阵——表示顶点间相联关系的矩阵例G22413例1532141452375318642úúúúúúúûùêêêêêêêëé∞61836∞24∞12∞∞784∞∞53∞75∞创建一个以邻接矩阵存储的图

网的邻接矩阵可定义为：ïîïíì>Î<=∞，其它E(G)v,v或)v,(v若,],[jijiijjiAw1452375318642úúúúúúú15typedefstructArcCell{VRTypeadj;InfoType*info;}ArcCell,AdjMatrix[MAX][MAX];typedefstructMGraph{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;GraphKindkind;}MGraph;MgraphG;typedefstructArcCellMgraphG16例aecbdG1úúúúúúúûùêêêêêêêëé0011000101110101010101010Gvexsarcsvexnumarcnumkind65UDGabcde例aecbdG1úúúúúúúûùêêêêêêêëé001117特点：

有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²

无向图中顶点Vi的度是邻接矩阵A中第i行元素之和

有向图中，

顶点Vi的出度是A中第i行元素之和

顶点Vi的入度是A中第i列元素之和

无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2特点：有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空18邻接表

实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）例G1bdac1234acdbvexdatafirstarc

3

2

4

1^^^^adjvexnextarc邻接表实现：为图中每个顶点建立一个单链表，第i个单链表中的19aecbdG21234acdbdatafirtarc

4

2

1

2^^^adjvexnextarc5e

4

3

5^

1

5

3

2

3^创建一个以邻接表存储的图aecbdG21234acdbdatafirtarc4220特点G1bdac1234acdbdatafirstarc

4

1^

1^^

3^adjvexnextarc

有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数

无向图中顶点Vi的度为第i个单链表中的结点数

逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表特点G1bdac1234acdbdatafirstarc421有向图的十字链表表示法bdac^^^^^^^^创建一个以十字链表存储的图

02

01

23

20

32

31

30tailvexheadvexhlinktlinkabcd0123datafirstinfirstout有向图的十字链表表示法bdac^^^^^^^^创建一个以十22无向图的邻接多重表表示法aecbd^^^^^创建一个以邻接多重表存储的图0123acdb4e

01

03

23

21

24

41ivexjvexilinkjlinkdatafirstedge无向图的邻接多重表表示法aecbd^^^^^创建一个以邻接多237.1图的定义和基本术语7.2图的存储结构

☞7.3图的遍历7.4图的生成树7.5拓扑排序7.6关键路径7.7最短路径第七章图7.1图的定义和基本术语第七章图247.3.1深度优先遍历DFS7.3.2广度优先遍历BFS

7.3图的遍历7.3.1深度优先遍历DFS7.3图的遍历25

遍历图：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。

深度优先遍历DFS

广度优先遍历BFS两种遍历方法：遍历图：从图中某个顶点出发游历图，访遍图中其余顶点，并且26深度优先遍历(DFS)V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V3V6V7方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止深度优先遍历(DFS)V1V2V4V5V3V7V6V8深度遍27V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V6V3V7深度遍历：V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8V1V2V4V5V3V7V628V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V3V6V7V5V1V2V4V5V3V7V6V8深度遍历：V1V2V29816273551428764342587361V1V2V4V5V3V7V6V8例深度遍历：816273551428764342587361V1V2V430V1V2V4V5V3V7V6V8深度遍历：V112341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6

4

1^

5

1

2

8

2^678678

7

3

6

3

5

4^^^V3V7V6V2V5V8V4V1V2V4V5V3V7V6V8深度遍历：V112341331V1V2V4V5V3V7V6V812341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6^

4

8

2^678678

7^^^深度遍历：V1V3V7V6V2V4V8V5V1V2V4V5V3V7V6V812341342vexdat32深度优先遍历算法

递归算法方法：1）选定任意一点作起始点2）访问起始点，并标注“已访问”3）对起始点的每一个邻接点进行如下操作：若该邻接点未访问过，以它作为新的起始点进行2）3）的操作。（算法特点：递归）深度优先遍历算法递归算法方法：33DFSTraverse(){for()DFS(G,v)//对非连通图需要多次出发DFS}DFS

()//以v为起点深度遍历{visit(v);//访问顶点vfor(w=v的第一个邻接点;w;w=v的下一个邻接点)DFS(G,w);}DFSTraverse()34广度优先遍历(BFS)V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。广度优先遍历(BFS)V1V2V4V5V3V7V6V8广度遍35V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8广度遍历：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8V1V2V4V5V3V7V636V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V6V7V8V5V1V2V4V5V3V7V6V8广度遍历：V1V2V37816273551428764332548671V1V2V4V5V3V7V6V8例广度遍历：816273551428764332548671V1V2V438V1V2V4V5V3V7V6V8广度遍历：V112341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6

4

1^

5

1

2

8

2^678678

7

3

6

3

5

4^^^V3V2V5V3V7V5V8V1V2V4V5V3V7V6V8广度遍历：V1123413391423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

20123451fr遍历序列：10123454fr遍历序列：1401234543fr遍历序列：1431423512341342vexdatafirstarc54012341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2012345432fr遍历序列：1432012345

32fr遍历序列：1432012345

325fr遍历序列：143251423512341342vexdatafirstarc55441012345

25fr遍历序列/p>

5fr遍历序列/p>

fr遍历序列：1432512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

21423501234542BFSTraverse(){for()

//对于非连通图需要有多个起始点

{EnQueue(v)//v是起点Visit(v)

while()//队列不空

{DeQueue()while()//所有邻接点入队一个访问一个

{EnQueue（w）Visit(w)}}

}}广度优先遍历算法BFSTraverse()广度优先遍历算法437.1图的定义和基本术语7.2图的存储结构7.3图的遍历

☞7.4图的生成树7.5拓扑排序7.6关键路径7.7最短路径第七章图7.1图的定义和基本术语第七章图44什么是生成树？一个图可以有许多棵不同的生成树一个有n个顶点的连通图的生成树有n-1条边定义：所有顶点均由边连接在一起，但不存在回路的子图叫~V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8有两种特殊的生成树：深度优先生成树&广度优先生成树一个连通图的生成树其实就是该连通图的极小连通分量什么是生成树？一个图可以有许多棵不同的生成树一个有n45V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V7V1V2V4V5V3V6V8广度遍历：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例深度遍历：V1V2V446非连通图ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林生成森林：非连通图每个连通分量的生成树一起组成非连通图的~需要从多个顶点出发，经过多次搜索非连通图ABLMCFDEGHKIJABLMCFJDEGHKI47对于连通网络，其生成树的各边也是带权值的，其各边的权值之和称作生成树的权，权值最小的生成树称为最小生成树14523753186421452375318642对于连通网络，其生成树的各边也是带权值的，其各边的权值之和称48问题分析1654327131791812752410

假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路该问题等价于：在e条带权的边中选取n-1条（不构成回路），使“权值之和”为最小。即：构造网的一棵最小生成树如何在最节省经费的前提下建立这个通讯网？问题提出问题分析165432713179181275241049构造最小生成树方法方法一：普里姆(Prim)算法

MST性质假设N=(V,{E})是一个连通网，U是顶点集V中的非空子集，若(u,v)是所有一端在U中而另一端在V-U中的所有边中具有最小权值的边，则必存在一棵最小生成树包含边(u,v)。构造最小生成树方法方法一：普里姆(Prim)算法MST50若图中所有顶点均加入中，则在3操作中记录的边和相关的顶点构成该网络的最小生成树以下的表述中，u表示U中的顶点,v表示V-U中的顶点

1选任一个顶点加入U2标出一端在U中，而另一端在V-U中的边和其权值，如果有多条边同时从U中的不同的顶点出发到达v，则只选其中权值小的那条3在2中标出的所有(u,v)中，选出权值最小的一条边，记录这条边，并将顶点v加入U中4若U<>V,根据新加入U中的顶点，调整连接U和V中的边（u，v），返回3若图中所有顶点均加入中，则在3操作中记录的边和相关的顶点构成51例1654326513566425131163141643142116432142516543214253***Prim算法***例1654326513566425131163141643152方法二：克鲁斯卡尔(Kruskal)算法例165432651356642516543212345算法思想：设连通网N=(V,{E})，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量。在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。依此类推，直至T中所有顶点都在同一连通分量上为止方法二：克鲁斯卡尔(Kruskal)算法例165432651531用顶点数组和边数组存放顶点和边信息2初始时，令每个顶点的集合互不相同；每个边的flag为03选出权值最小且flag为0的边4若该边依附的两个顶点的集合值不同，即非连通，则令该边的flag=1,选中该边；再令该边依附的两顶点的集合以及两集合中所有顶点的集合相同。若该边依附的两个顶点的集合值相同，即连通，则令该边的flag=2,即舍去该边。5重复上述步骤，直到选出n-1条边为止算法实现：1用顶点数组和边数组存放顶点和边信息算法实现：54例1654326513566425datajihe124536124536124536vexhweight112213233544vextflag6153550000000134256789334556666426000011111421112222216543212345例1654326513566425datajihe1245355普里姆算法适于稠密图；克鲁斯卡尔算法需对e条边按权值进行排序，则适于稀疏图例.请分别用Prim算法和Kruskal算法构造该网络的最小生成树。

普里姆算法适于稠密图；例.请分别用Prim算法和Kruska567.1图的定义和基本术语7.2图的存储结构7.3图的遍历7.4图的生成树

☞7.5拓扑排序7.6关键路径7.7最短路径第七章图7.1图的定义和基本术语第七章图57一个无环的有向图称作有向无环图(DirectidAcyclineGragp)有向无环图有向无环图是描述一项工程或系统的进行过程的有效工具一个无环的有向图称作有向无环图(DirectidAcycl58课程代号课程名称先修棵C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1C2C3C4C5C6C7C8C9C10C11C12学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业？？？顶点——表示课程有向弧——若课程i是课程j的先决条件，则图中有弧<i,j>学生选修课程问题课程代号课程名称59AOV网

——

用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(ActivityOnVertexnetwork)，简称AOV网。拓扑排序

——

把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫~检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环AOV网——用顶点表示活动，用弧表示活动间优先关系的有向60在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧拓扑排序的方法重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止在有向图中选一个没有前驱的顶点且输出之拓扑排序的方法重复上述61C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一个AOV网的拓扑序列不是唯一的C1C2C3C4C5C6C7C8C9C10C11C12拓扑序62C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）C1C2C3C4C5C6C7C8C9C10C11C12拓扑序63C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2（2）C9C3C4C5C6C7C8C10C11C12拓扑序列：C1--C2--C3（3）C2C3C4C5C6C7C8C9C10C11C12拓扑序列：64C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4（4）C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5（5）C4C5C6C7C8C9C10C11C12拓扑序列：C1--65C6C8C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7（6）C11拓扑序列：C1--C2--C3--C4--C5--C7--C9C6C8C9C10C12C6C8C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11C6C8C10C11C12拓扑序列：C1--C2--C3--66C6C8C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6C8C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12C8拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8C6C8C12拓扑序列：C1--C2--C3--C4--C567算法实现重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕以邻接表作存储结构把邻接表中所有入度为0的顶点进栈栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈算法实现重复上述操作直至栈空为止。若栈空时输出的顶点个数不是6832104例1234560122infr

5

5

4

3^^^vexnext3^

2

5^

2

40123456^top16toptop32104例1234560122infr5543^^693210416top输出序列：6top例1234560122infr

5

5

4

3^^^vexnext3^

2

5^

2

40123456^3210416top输出序列：6top例1234560122700122infr

5

5

4

3^^^vexnext3^

2

5^

2

40123456^输出序列：6321041topp0122infr5543^^^vexnext3^2710122infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6321041topp0122infr5543^^^vexnext2^2720122infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6321041topp0122infr5543^^^vexnext2^2730112infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6321041topp0112infr5543^^^vexnext2^2740112infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6321041topp=NULL0112infr5543^^^vexnext2^2750112infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：61321041toptop0112infr5543^^^vexnext2^2760112infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104topp0112infr5543^^^vexnext2^2770102infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104topp40102infr5543^^^vexnext2^2780102infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p4top0102infr5543^^^vexnext2^2790102infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p4top0102infr5543^^^vexnext2^2800002infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p4top30002infr5543^^^vexnext2^2810002infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p4top30002infr5543^^^vexnext2^2820002infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p4top30002infr5543^^^vexnext2^2830001infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p4top30001infr5543^^^vexnext2^2840001infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：6132104p=NULL4top30001infr5543^^^vexnext2^2850001infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：613321044top30001infr5543^^^vexnext2^2860001infr

5

5

4

3^^^vexnext2^

2

5^

2

40123456^输出序列：613321044topp0001infr5543^^^vexnext2^2870001infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：613321044topp0001infr5543^^^vexnext1^2880001infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：613321044topp0001infr5543^^^vexnext1^2890000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：613321044topp20000infr5543^^^vexnext1^2900000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：613321044topp20000infr5543^^^vexnext1^2910000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：613321044top2p=NULL0000infr5543^^^vexnext1^2920000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：6132321044top2p=NULL0000infr5543^^^vexnext1^2930000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：6132321044topp=NULL0000infr5543^^^vexnext1^2940000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：61324321044top0000infr5543^^^vexnext1^2950000infr

5

5

4

3^^^vexnext1^

2

5^

2

40123456^输出序列：6132432104topp0000infr5543^^^vexnext1^2960000infr

5

5

4

3^^^vexnext0^

2

5^

2

40123456^输出序列：6132432104topp50000infr5543^^^vexnext0^2970000infr

5

5

4

3^^^vexnext0^

2

5^

2

40123456^输出序列：6132432104topp=NULL50000infr5543^^^vexnext0^2980000infr

5

5

4

3^^^vexnext0^

2

5^

2

40123456^输出序列：61324532104top50000infr5543^^^vexnext0^2990000infr

5

5

4

3^^^vexnext0^

2

5^

2

40123456^输出序列：61324532104topp=NULL拓扑排序算法0000infr5543^^^vexnext0^2100例.写出下图所有可能的拓扑序列bcdegfa例.写出下图所有可能的拓扑序列bcdegfa1017.1图的定义和基本术语7.2图的存储结构7.3图的遍历7.4图的生成树7.5拓扑排序

☞7.6关键路径7.7最短路径第七章图7.1图的定义和基本术语第七章图102例

设一个工程有11项活动，9个事件

事件V1——表示整个工程开始

事件V9——表示整个工程结束987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4AOE网（ActivityOnEdge）边表示活动用顶点表示事件，弧表示活动，权表示活动持续的时间；网中只有：唯一一个入度为0的点源点唯一一个出度为0的点汇点完成整项工程至少需要多少时间？哪些活动是影响工程进度的关键？例设一个工程有11项活动，9个事件987645321a1103Ve(j)——表示事件Vj的最早发生时间Vl(j)——表示事件Vj的最迟发生时间ee(i)——表示活动ai的最早开始时间el(i)——表示活动ai的最迟开始时间el(i)-ee(i)——表示完成活动ai的时间余量关键活动就是时间余量el(i)-ee(i)＝0的活动关键路径

——

路径长度最长的路径叫~关键活动

——

关键路径上的活动叫~987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Ve(j)——表示事件Vj的最早发生时间关键路径——路径104如何找ee(i)=el(i)的关键活动？设活动ai用弧<j,k>表示，其持续时间记为：dut(<j,k>)则有：（1）ee(i)=Ve(j)（2）el(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)从Ve(1)=0开始向前递推(2)从Vl(n)=Ve(n)开始向后递推如何找ee(i)=el(i)的关键活动？设活动ai用弧<j,105987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动eeelel-ee00002266046258377077071031616014140033求关键路径步骤求Ve(i)->求Vl(j)->求ee(i),el(i),计算el(i)-ee(i)987645321a2=4a3=5a5=1a6=2a9=4a106算法描述输入顶点和弧信息，建立其邻接表计算每个顶点的入度对其进行拓扑排序排序过程中求顶点的Ve[i]将得到的拓扑序列进栈按逆拓扑序列求顶点的Vl[i]计算每条弧的ee[i]和el[i],找出ee[i]=el[i]的关键活动987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4按拓扑排序的顺序计算Ve按逆拓扑排序的顺序计算Vl因此：对以拓扑排序算法为基础修改关键路径算法算法描述987645321a2=4a3=5a5=1a6=2a107987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4inlink

vexnextvexdata

info123456789123456789011121122

26

34

45^

79^

51^

62^

51^

87^

84^

910^

94^987645321a2=4a3=5a5=1a6=2a9=4a1087.1图的定义和基本术语7.2图的存储结构7.3图的遍历7.4图的生成树7.5拓扑排序7.6关键路径

☞7.7最短路径第七章图7.1图的定义和基本术语第七章图109问题提出用带权的有向图表示一个交通运输网，图中：顶点——表示城市边——表示城市间的交通联系权——表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径从某个源点到其余各顶点的最短路径51643208562301371732913长度最短路径<V0,V1><V0,V2><V0,V2,V3><V0,V2,V3,V4><V0,V2,V3,V4,V5><V0,V1,V6>813192120问题提出用带权的有向图表示一个交通运输网，图中：从某个源点到110迪杰斯特拉(Dijkstra)算法思想按路径长度递增次序产生最短路径算法：把V分成两组：（1）S：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值

S中顶点：从V0到此顶点的最短路径长度

T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值,或是从V0经S中顶点到Vk的路径权值之和（反证法可证）迪杰斯特拉(Dijks