数据结构第9章图.pptx

《数据结构第9章图.pptx》由会员分享，可在线阅读，更多相关《数据结构第9章图.pptx（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的基本概念图的基本概念图的基本概念图的基本概念n n图图(Graph)图是由顶点集合图是由顶点集合图是由顶点集合图是由顶点集合(vertex)及顶点间及顶点间及顶点间及顶点间的关系集合组成的一种数据结构的关系集合组成的一种数据结构的关系集合组成的一种数据结构的关系集合组成的一种数据结构：n GraphGraph(V V,E E)其中其中其中其中:V V=x x|x x 某个数据对象某个数据对象某个数据对象某个数据对象 是顶点的有穷非空是顶点的有穷非空是顶点的有穷非空是顶点的有穷非空集合；集合；集合；集合；E E=(=(x x,y y)|)|x x,y y V V 或或或或 E E=y|x x

2、,y y V V 是顶点之间关系的是顶点之间关系的是顶点之间关系的是顶点之间关系的有穷集合。有穷集合。有穷集合。有穷集合。125634abcd无向图无向图有向图有向图V=1,2,3,4,5,6E=(1,2),(1,5),(1,6),(2,3),(2,4),(3,4),(4,5),(4,6)（边）V=a,b,c,dE=,（弧）第1页/共58页ADT Graph 数据对象数据对象:D=ai|1 i n,n 0,ai属Elemtype类型 数据关系数据关系:R1=|ai,aj D,1 i n,1 j n,每个元素可以有多个直接前驱和可以有多个直接后继 基本运算基本运算:InitGraph(t);Cl

3、earGraph(t);DSF(t);BSF(t);抽象数据类型数的定义第2页/共58页n n完全图完全图 若有若有若有若有 n n 个顶点的无向图有个顶点的无向图有个顶点的无向图有个顶点的无向图有 n n(n n-1)/2 1)/2 条边条边条边条边,则此图为完全无向图。有则此图为完全无向图。有则此图为完全无向图。有则此图为完全无向图。有 n n 个顶点的有个顶点的有个顶点的有个顶点的有向图有向图有向图有向图有n n(n n-1)1)条边条边条边条边,则此图为完全有向图。则此图为完全有向图。则此图为完全有向图。则此图为完全有向图。abc1234邻接顶点邻接顶点 如果如果如果如果 (u u,v

4、 v)是是是是 E E(G)(G)中的一条中的一条中的一条中的一条边，则称边，则称边，则称边，则称 u u 与与与与 v v 互为邻接顶点互为邻接顶点互为邻接顶点互为邻接顶点。例：存在例：存在(1,2)，则顶点，则顶点1与与2互为邻接点。互为邻接点。存在存在,则顶点则顶点a与与b互为邻接点。互为邻接点。第3页/共58页125634abcdn n顶点的度顶点的度 一个顶点一个顶点一个顶点一个顶点v v的度是与它相关联的边的的度是与它相关联的边的的度是与它相关联的边的的度是与它相关联的边的条数。记作条数。记作条数。记作条数。记作TD(TD(v v)。n n在有向图中在有向图中在有向图中在有向图中,

5、顶点的度顶点的度顶点的度顶点的度=入度入度入度入度+出度。出度。出度。出度。n n顶点顶点顶点顶点 v v 的入度的入度的入度的入度 是以是以是以是以 v v 为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数,记作记作记作记作 ID(ID(v v);顶点顶点顶点顶点 v v 的出度的出度的出度的出度 是以是以是以是以 v v 为始点的有为始点的有为始点的有为始点的有向边的条数向边的条数向边的条数向边的条数,记作记作记作记作 OD(OD(v v)。TD(TD(v v)=ID()=ID(v v)+OD()+OD(v v)例：TD(1)=3 TD(4)=4 TD(5)

6、=2例：TD(b)=ID(b)+OD(b)TD(d)=ID(d)+OD(d)=2+1=3=2+3=5第4页/共58页n n子图子图子图子图 设有两个图设有两个图设有两个图设有两个图 GG(V V,E E)和和和和 GG(V V,E E)。若。若。若。若 V V V V 且且且且 E E E E,则称则称则称则称 图图图图G G 是是是是 图图图图G G 的子图。的子图。的子图。的子图。0123子图子图0130123023n n权权 某些图的边具有与它某些图的边具有与它某些图的边具有与它某些图的边具有与它相关的数相关的数相关的数相关的数,称为权。这种称为权。这种称为权。这种称为权。这种带权图叫做

7、网络。带权图叫做网络。带权图叫做网络。带权图叫做网络。任意图都是其自身子图abcd 8 1 93 4 11 23第5页/共58页n n路径路径路径路径 在图在图在图在图 GG(V V,E E)中中中中,若从顶点若从顶点若从顶点若从顶点 v vi i 出发出发出发出发,沿一些边经过一些顶点沿一些边经过一些顶点沿一些边经过一些顶点沿一些边经过一些顶点 v vp p1 1,v vp p2 2,v vpmpm，到达顶点到达顶点到达顶点到达顶点v vj j。则则则则称顶点序列称顶点序列称顶点序列称顶点序列 (v vi i v vp p1 1 v vp p2 2.v vpm pm v vj j)为从顶点为

8、从顶点为从顶点为从顶点v vi i 到顶点到顶点到顶点到顶点 v vj j 的路径的路径的路径的路径。125634例：V1到V3的路径：123 、123423、16423、1544.n n路径长度路径长度 非带权图的路径长度是指此路径上边的条数。带权图的非带权图的路径长度是指此路径上边的条数。带权图的非带权图的路径长度是指此路径上边的条数。带权图的非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。路径长度是指路径上各边的权之和。路径长度是指路径上各边的权之和。路径长度是指路径上各边的权之和。n n简单路径简单路径 若路径上各顶点若路径上各顶点若路径上各顶点若路径上

9、各顶点 v v1 1,v v2 2,.,.,v vm m 均不均不均不均不 互相重复互相重复互相重复互相重复,则称这样则称这样则称这样则称这样的路径为简单路径。的路径为简单路径。的路径为简单路径。的路径为简单路径。n n回路回路 若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点与最后一个顶点与最后一个顶点v vm m 重合重合重合重合,则称这样则称这样则称这样则称这样的路径为回路或环。的路径为回路或环。的路径为回路或环。的路径为回路或环。路径长度：2 、5 、4 、3 .第6页/共58页n n连通图与连通分量连通图与连通分量连

10、通图与连通分量连通图与连通分量 在无向图中在无向图中在无向图中在无向图中,若从顶点若从顶点若从顶点若从顶点v v1 1到顶点到顶点到顶点到顶点v v2 2有路有路有路有路径径径径,则称则称则称则称顶点顶点顶点顶点v v1 1与与与与v v2 2是连通的是连通的是连通的是连通的。如果图中任意一对顶如果图中任意一对顶如果图中任意一对顶如果图中任意一对顶点都是连通的点都是连通的点都是连通的点都是连通的,则称此图是则称此图是则称此图是则称此图是连通图连通图连通图连通图。非连通图的极大连非连通图的极大连非连通图的极大连非连通图的极大连通子图叫做通子图叫做通子图叫做通子图叫做连通分量连通分量连通分量连通分

11、量。n n生成树生成树 一个连通图的生成树是其一个连通图的生成树是其一个连通图的生成树是其一个连通图的生成树是其极小连通子图极小连通子图极小连通子图极小连通子图。n n个顶点个顶点个顶点个顶点、n n-1 1条边条边条边条边、连通子连通子连通子连通子图图图图。12563441532连通图连通图非连通图非连通图两个连通分量两个连通分量125634125634第7页/共58页n n强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中在有向图中在有向图中,若对于每一若对于每一若对于每一若对于每一对顶点对顶点对顶点对顶点v vi i和和和和v vj j,都存在一条从都存在一条从都存在一条从都

12、存在一条从v vi i到到到到v vj j和从和从和从和从v vj j到到到到v vi i的路径的路径的路径的路径,则称此图是则称此图是则称此图是则称此图是强连通图强连通图强连通图强连通图。非强连通图的极大强连通子图叫做非强连通图的极大强连通子图叫做非强连通图的极大强连通子图叫做非强连通图的极大强连通子图叫做强连通分量强连通分量强连通分量强连通分量。abcd abcd 强连通图强连通图非强连通图非强连通图cabd 两个强连通分量两个强连通分量第8页/共58页图的存储表示图的存储表示图的存储表示图的存储表示邻接矩阵邻接矩阵(Adjacency Matrix)aij=abef cd vexs1 2

13、 3 4 5 6 a b c d e f A=0 1 0 0 1 11 0 1 1 0 00 1 0 1 0 00 1 1 0 1 11 0 0 1 0 01 0 0 1 0 0利用数组vertex 存储顶点基本思想：利用矩阵A表示顶点之间的关系无向图的邻接矩阵是对称矩阵第9页/共58页aij=A=abcd 8 1 93 4 11 23 vexs1 2 3 4A=a b c d 11111 1 1000 0 00 0 00A=abef cd vexs1 2 3 4 5 6 a b c d e f 4 8 2 19 6 7 3 1084931 11 23419841982 62633107107

14、A=0 1 0 0 1 11 0 1 1 0 00 1 0 1 0 00 1 1 0 1 11 0 0 1 0 01 0 0 1 0 0邻接矩阵所占存储空间与顶点数成正比但图中有无关系都分配存储空间边的插入和删除不影响存储空间大小0 100？求顶点的度第10页/共58页邻接矩阵的数据类型邻接矩阵的数据类型A=vexs1 2 3 4typedef struct int no;InfoType info;VertexTtypetypedef struct int edgesMAXVMAXV;/*各顶点之间的关系或权值*/int n,e;/*顶点数，边（或弧）的个数*/VertexType vexs

15、MAXV;/*存储顶点元素*/MGraph;第11页/共58页建立邻接矩阵*邻接矩阵初始化（置0或 ）*输入顶点数，弧数 ga-n ga-e*输入各顶点信息存入ga-vexs*输入各边信息（或权值）存入ga-edages A=vexs1 2 3 4第12页/共58页邻接表邻接表(Adjacency List)n n基本思想：基本思想：基本思想：基本思想：在无向图中，将依附于某个顶点的所有在无向图中，将依附于某个顶点的所有在无向图中，将依附于某个顶点的所有在无向图中，将依附于某个顶点的所有边边边边（边结点）（边结点）（边结点）（边结点）以单链表形式链接，每个链表设以单链表形式链接，每个链表设以单

16、链表形式链接，每个链表设以单链表形式链接，每个链表设立一个立一个立一个立一个表头结点表头结点表头结点表头结点。abef cd123456 abcdef(a,b)(a,e)(a,f)256(b,a)(b,c)(b,d)1 3 4(c,b)(c,d)2 4(d,b)(d,c)(d,e)(d,f)2 3 5 6 (e,a)(e,d)(f,a)(f,d)1 41 4 data firstarc 4 8 2 19 6 7 3 104 8 198 7 4 2 6adjvex info nextarc3 6 10 7 2 319 10adjvex nextarc注：在无向图中每个边生成两个结点？插入和删除(

17、d,f)=(f,d)?求顶点的度第13页/共58页 data firstarc1234abcd 8 5 93 7 11 13邻接表：在有向图中，将以该顶点作为弧尾顶点的所有弧链接成单链表。abcd 2 8 4 74 91 3 1 5 2 11 3 13 data firstarc1234 abcd 3 3 4 5 4 13 1 8 4 111 7 4 9逆邻接表逆邻接表：在有向图中，将以该顶点作为弧头顶点的所有弧链接成单链表。？求顶点的度第14页/共58页邻接表的结点结构和数据类型邻接表的结点结构和数据类型 data firstarc表头结点表头结点typedef struct ANode i

18、nt adjvex;/*邻接点存储序号*/InfoType info;/*若是网络存储权值*/struct ANode *nextarc;/*指向下一个边结点*/ArcNode;typedef struct Vertex data;/*存储顶点元素*/ArcNode *firstarc;/*指向依附于该顶点的第一边*/VNode;typedef VNode AdjListMAXV;typedef struct AdjList adjlist;int n,e;ALGraph;adjvex nextarc边结点边结点adjvex info nextarc第15页/共58页 data firstar

19、cadjvex info nextarc123456 abcdef256 1 3 4 2 4 2 3 5 6 1 41 44 8 198 7 4 2 63 6 10 7 2 319 10abef cd 4 8 2 19 6 7 3 10建立邻接表*邻接表初始化（置各单链表为空表 ga.firstarc=NULL）*输入各顶点信息存入 ga.data*输入各边信息，生成新结点，插入相应的单链中。第16页/共58页abcd 8 5 93 7 11 13 data firstarc1234abcd 2 8 4 74 91 3 1 5 2 11 3 13邻接表的基本操作插入：*确定单链表*生成新结点6

20、3 6*头插链表注：有向图只插入(或删除）一个结点，而无向图需插入（或删除）两个结点。删除：*确定结点*删除结点*释放结点 第17页/共58页十字链表十字链表(有向图有向图)abcd 8 5 93 7 11 13a a a b a c a d a 1 2 a 1 4a 2 4 a 3 1 a 4 1 a 4 2 a 4 3 tailvex headvex hlink tlink info弧结点data firstin firstout顶点结点第18页/共58页data firstin firstout顶点结点tailvex headvex hlink tlink info弧结点typedef

21、struct ArcNode int tailvex,headvex;struct ArcNode*hlink,*tlink;InfoType info;ArcNode;typedef struct VexNode VertexType data;ArcNode*firstin,*firstout;VexNode;十字链表的数据类型十字链表的数据类型第19页/共58页a 4 6(d,f)abef cd 4 8 2 19 6 7 3 10A BCDEFa 1 2(a,b)a 1 5(a,e)a 1 6(a,f)a 2 3(b,c)a 2 4(b,d)a 3 4(c,d)a 4 5(d,e)邻接多

22、重表邻接多重表（无向图）（无向图）mark ivex ilink jvex jlink边结点 data firstedge顶点结点第20页/共58页 data firstedge顶点结点 mark ivex ilink jvex jlink边结点typedef struct ENode int mark;int ivex,jvex;struct ENode*ilink,*jlink;InfoType info;ENode;邻接多重表的数据类型邻接多重表的数据类型typedef struct VNode VertexType data;ENode*firstedge;VNode;第21页/共58

23、页图的遍历图的遍历 (Graph Traversal)n n图的遍历图的遍历图的遍历图的遍历从图中某一顶点出发，沿着一从图中某一顶点出发，沿着一从图中某一顶点出发，沿着一从图中某一顶点出发，沿着一 些边访遍些边访遍些边访遍些边访遍图中所有的顶点，且使每个顶点仅被访问一次。图中所有的顶点，且使每个顶点仅被访问一次。图中所有的顶点，且使每个顶点仅被访问一次。图中所有的顶点，且使每个顶点仅被访问一次。n n为了避免重复访问，设置一个的辅助数组为了避免重复访问，设置一个的辅助数组为了避免重复访问，设置一个的辅助数组为了避免重复访问，设置一个的辅助数组 visited visited 标志标志标志标志各

24、顶点是否被访问过各顶点是否被访问过各顶点是否被访问过各顶点是否被访问过。n n图的遍历的分类：图的遍历的分类：深度优先搜索深度优先搜索深度优先搜索深度优先搜索 DFS(Depth First Search)DFS(Depth First Search)广度优先搜索广度优先搜索广度优先搜索广度优先搜索 BFS(Breadth First Search)BFS(Breadth First Search)第22页/共58页12563478深度优先搜索深度优先搜索DFS(Depth First Search)visited1 2 3 4 5 6 7 8DFS基本思想：*访问顶点v0。*依次从v0未被访

25、问的邻接点出发进行深度优先搜索遍历。遍历序列：1231256414521426264545262653178177383883733780 0 0 0 0 0 0 01 111111 1注：访问v0的邻接点与访问v0方法一样，用递归方式实现。12563478DFS(v0)的主要步骤：(1)访问顶点v0(2)确定第一邻接点w(3)若w未访问，则从w出发进行遍历DFS(w)(4)确定下一个邻接点w(5)重复(3)(4)直到所有邻接点都处理结束 第23页/共58页DFS(v0)的主要步骤：(1)访问顶点v0(2)确定第一邻接点w(3)若w未访问，则从w出发进行遍历DFS(w)(4)确定下一个邻接点w

26、(5)重复(3)(4)直到所有邻接点都处理结束 深度优先搜索深度优先搜索DFS(Depth First Search)DFS(v0)visite(v0);visitedv0=1;w=FIRST(v0);while(存在w)if (visitedw=0)DFS(w);w=NEXT(v0,w);第24页/共58页125634 data firstarc123456abcdef 562 3 1 4 2 4 3 5 6 2 4 1 1 4DFS(v0)visite(v0);visitedv0=1;w=FIRST(v0);while(存在w)if (visitedv0=0)DFS(w);w=NEXT(v

27、0,w);第一邻接点:p=G-adjlistv.firstarc下一个邻接点：p=p-nextarc第25页/共58页广度优先搜索广度优先搜索 BFS(Breadth First Search)12563478BFS基本思想：*访问顶点v0。*依次访问v0未被访问的邻接点*依次从这些邻接点出发进行广度优先搜索遍历。注：为了从已访问的邻接点出发，设置队列保存结点visited1 2 3 4 5 6 7 8遍历序列：1 2 3 4 5 7 8 612 223 334 445 557 7 7 8 88队列队列0 0 0 0 0 0 0 06 661 1 1 1 11 111 112563478第26

28、页/共58页BFS(v0)的主要步骤：(1)访问顶点v0(2)顶点v0入队列(3)取出队头v 确定第一邻接点w 若w未访问，则访问w，w入队列。确定下一个邻接点w 重复 直到所有邻接点都处理(4)重复(3)直到队列空。广度优先广度优先搜索搜索BFS(Breadth First Search)BFS(v0)init(Q);visite(v0);visitedv0=1;enqueue(Q,v0);while(!empty(Q)v=dequeue(Q);w=FIRST(v);while(存在w)if (visitedw=0)visite(w);visitedw=1;enqueue(Q,w);w=NE

29、XT(v,w);第27页/共58页BFS(v0)init(Q);visite(v0);visitedv0=1;enqueue(Q,v0);while(!empty(Q)v=dequeue(Q);w=FIRST(v);while(存在w)if (visitedw=0)visite(w);visitedw=1;enqueue(Q,w);w=NEXT(v,w);125634 data firstarc123456abcdef 562 3 1 4 2 4 3 5 6 2 4 1 1 4第一邻接点:p=G-adjlistv.firstarc下一个邻接点：p=p-nextarc第28页/共58页深度优先搜

30、索深度优先搜索DFS(Depth First Search)n n深度优先搜索深度优先搜索过程过程的示例的示例ACDEGBFIHACDEGBFIH123456791234567889深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树前进回退第29页/共58页广广度度优优先先搜搜索索BFS(Breadth First Search)n n广度优先搜索的示例广度优先搜索的示例ACDEGBFIH123456789123456789广度优先搜索过程广度优先搜索过程 ACDEGBFHI广度优先生成树广度优先生成树第30页/共58页 问题：问题：当对非连通图遍历时当对非连通图遍历时当对非连通图

31、遍历时当对非连通图遍历时,从图中某一顶点出从图中某一顶点出从图中某一顶点出从图中某一顶点出发发发发,利用深度优先搜索算法或广度优先搜索算法利用深度优先搜索算法或广度优先搜索算法利用深度优先搜索算法或广度优先搜索算法利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点不可能遍历到图中的所有顶点不可能遍历到图中的所有顶点不可能遍历到图中的所有顶点,只能访问到该顶只能访问到该顶只能访问到该顶只能访问到该顶点所在的最大连通子图点所在的最大连通子图点所在的最大连通子图点所在的最大连通子图(连通分量连通分量连通分量连通分量)的所有顶点。的所有顶点。的所有顶点。的所有顶点。ACDEBFGIHJO

32、NMLK非连通无向图要实现任意图的遍历，则要扫描图中的所有顶点。TRQVER()for(i=1;i=n;i+)visitedi=0;for(i=1;i=n;i+)if(visitedi=0)DFS(vi);TRQVER()for(i=1;i=n;i+)visitedi=0;for(i=1;i=n;i+)if(visitedi=0)BFS(vi);第31页/共58页ACDEBFGIHJONMLK非连通无向图ACDEBFGHIJKONML非连通图的连通分量n n对于非连通的无向图，所有连通分量的生成树对于非连通的无向图，所有连通分量的生成树对于非连通的无向图，所有连通分量的生成树对于非连通的无向图

33、，所有连通分量的生成树组成了非连通图的生成森林。组成了非连通图的生成森林。组成了非连通图的生成森林。组成了非连通图的生成森林。第32页/共58页ACDEBFGIHJONMLK非连通无向图ACDEBFGIHJONMLK非连通图的连通分量第33页/共58页1624351624351624351251042312104312542深度优先搜索遍历广度优先搜索遍历遍历序列:123456遍历序列:125634连连通通图图生生成成树树不同的遍历得到不同的生成树不同的遍历得到不同的生成树权值之和:20权值之和:14第34页/共58页最小生成树最小生成树(minimum cost spanning tree)

34、最小生成树最小生成树最小生成树最小生成树-在一个连通网得到的所有生成在一个连通网得到的所有生成在一个连通网得到的所有生成在一个连通网得到的所有生成树中树中树中树中,权值之和最小的生成树称为最小生成树权值之和最小的生成树称为最小生成树权值之和最小的生成树称为最小生成树权值之和最小的生成树称为最小生成树.3564257156146352n n使用且仅使用该网络中的使用且仅使用该网络中的使用且仅使用该网络中的使用且仅使用该网络中的n n-1 1 条边来联结网条边来联结网条边来联结网条边来联结网络中的络中的络中的络中的 n n 个必须顶点；个必须顶点；个必须顶点；个必须顶点；n n不能使用产生回路的边

35、；不能使用产生回路的边；不能使用产生回路的边；不能使用产生回路的边；n n各边上的权值的总和达到最小。各边上的权值的总和达到最小。各边上的权值的总和达到最小。各边上的权值的总和达到最小。应用:在若干个城市中建立通讯网。第35页/共58页MST性质：设设G=G=（V,EV,E）是一个连通网络，）是一个连通网络，U U是顶点集是顶点集V V的一个子集。的一个子集。若（若（u,vu,v）是）是G G中所有的一个端点在中所有的一个端点在U U（即（即u u U U）里，另一个端点不在）里，另一个端点不在U U（即（即v v V-U V-U）里的边中，具有最小权值的一条边，则一定存在）里的边中，具有最小

36、权值的一条边，则一定存在G G的一棵最小生成的一棵最小生成树包含此边树包含此边（u,vu,v）。）。UV-U反正法证明：假设G中任何一棵最小生成树中都不包含边（u,vu,v）。）。vuvu设设T T是一棵最小生成树，不包（是一棵最小生成树，不包（u,vu,v）,一定要包一定要包含一条边（含一条边（u u,v,v）。）。若用（若用（u,vu,v）取代（）取代（u u,v,v）得到一棵新的生成树）得到一棵新的生成树T T,由于由于W W（u,vu,v）W W（u,vu,v），则），则T T的权的权TT的权，的权，与假设矛盾。与假设矛盾。第36页/共58页5356425715614635254613

37、56242361657 756643255普里姆普里姆(Prim)算法算法n n基本思想：基本思想：基本思想：基本思想：设连通网络设连通网络设连通网络设连通网络 N N=(=(V V,E E)，最小生成树最小生成树最小生成树最小生成树T=(U,TE)T=(U,TE)（1 1）初始状态：）初始状态：）初始状态：）初始状态：U=vU=v0 0,TE=,TE=。（2 2）选择满足）选择满足）选择满足）选择满足MSTMST性质的一条边（性质的一条边（性质的一条边（性质的一条边（u,vu,v）,其中其中其中其中u u U U，v v V-UV-U，且边，且边（u,vu,v）的权值最小。）的权值最小。）的

38、权值最小。）的权值最小。（3 3）吸收）吸收）吸收）吸收v vU U,吸收吸收吸收吸收（u,vu,v）TETE。（4 4）重复（）重复（）重复（）重复（2 2）（）（）（）（3 3），直到），直到），直到），直到U=VU=V。第37页/共58页55351246142360657 755632143564257156035241 0 6 1 5 6 0 5 3 1 5 0 7 5 4 5 7 0 2 3 5 0 6 4 2 6 0cost lowcost closest 0 6 1 5 0 0 0 0 0 0最小5540最小222最小最小2050034 0 1 2 3 4 5cost :利用邻接

39、矩阵法存储图 i=j:costij=0 closest 和lowcost 分别存储顶点序号和权值，当lowcosti=0:顶点i已经吸收到U。当lowcosti 0:顶点i未被吸收V-U。当0lowcostivi可达的距离0 10 2 记录到达vi的路径1 1 1 1 1 1 1最小(Si=0)121修正:distmin+costminidisti?013 3043最小(Si=0)143084 010 4最小(Si=0)184095 015 5最小(Si=0)195最小(Si=0)110 4 013 6 113 6path=13467第42页/共58页10432101003050206010V

40、0V1 V0V1 10V0V3 V0V3 30V0V2 V0V3 V2 50V0V4 V0V3 V2 V4 50第43页/共58页拓扑排序拓扑排序(Topological Sort)(AOV网网)n n计划、施工过程、生产流程、程序流程等都计划、施工过程、生产流程、程序流程等都是是“工程工程”。除了很小的工程外，一般都把。除了很小的工程外，一般都把工程分为若干个叫做工程分为若干个叫做“活动活动”的子工程。完的子工程。完成了这些活动，这个工程就可以完成了。成了这些活动，这个工程就可以完成了。n n例如，计算机专业学生的学习就是一个工程，例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是

41、整个工程的一些活动。每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程这样在有的课程之间有领先关系，有的课程可以并行地学习。可以并行地学习。第44页/共58页 C1 高等数学高等数学 C2 程序设计基础程序设计基础 C3 离散数学离散数学 C1,C2 C4 数据结构数据结构 C3,C2 C5 高级语言程序设计高级语言程序设计 C2 C6 编译方法编译方法 C5,C4 C7 操作系统操作系统 C4,C9 C8 普通物理普通物理 C1 C9 计算机原理计算机原理 C8 C8C3C5C4C9C

42、6C7C1C2学生课程学习工程图学生课程学习工程图第45页/共58页n n可以用可以用可以用可以用有向图有向图有向图有向图表示一个工程。在这种有向图中，表示一个工程。在这种有向图中，表示一个工程。在这种有向图中，表示一个工程。在这种有向图中，用顶点表示活动用顶点表示活动用顶点表示活动用顶点表示活动，用有向边用有向边用有向边用有向边 表示表示表示表示活动活动活动活动V Vi i 必必必必须先于活动须先于活动须先于活动须先于活动V Vj j 进行进行进行进行。这种有向图叫做顶点表示活。这种有向图叫做顶点表示活。这种有向图叫做顶点表示活。这种有向图叫做顶点表示活动的动的动的动的AOVAOV网络网络网

43、络网络 (Activity On Vertices)(Activity On Vertices)。n n在在在在AOVAOV网络中不能出现有向回路网络中不能出现有向回路网络中不能出现有向回路网络中不能出现有向回路,即有向环。如即有向环。如即有向环。如即有向环。如果出现了有向环，则意味着某项活动应以自己作果出现了有向环，则意味着某项活动应以自己作果出现了有向环，则意味着某项活动应以自己作果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的为先决条件。因此，对给定的为先决条件。因此，对给定的为先决条件。因此，对给定的AOVAOV网络，必须先网络，必须先网络，必须先网络，必须先判断它

44、是否存在有向环。判断它是否存在有向环。判断它是否存在有向环。判断它是否存在有向环。n n检测有向环的一种方法是对检测有向环的一种方法是对检测有向环的一种方法是对检测有向环的一种方法是对AOVAOV网络构造它的拓网络构造它的拓网络构造它的拓网络构造它的拓扑有序序列。即将各个顶点扑有序序列。即将各个顶点扑有序序列。即将各个顶点扑有序序列。即将各个顶点 (代表各个活动代表各个活动代表各个活动代表各个活动)排列排列排列排列成一个线性有序的序列，使得成一个线性有序的序列，使得成一个线性有序的序列，使得成一个线性有序的序列，使得AOVAOV网络中所有应网络中所有应网络中所有应网络中所有应存在的前驱和后继关

45、系都能得到满足。存在的前驱和后继关系都能得到满足。存在的前驱和后继关系都能得到满足。存在的前驱和后继关系都能得到满足。拓扑排序拓扑排序拓扑排序拓扑排序第46页/共58页C8C3C5C4C9C6C7C1C2拓扑排序拓扑排序拓扑排序拓扑排序-在在在在AOVAOV网络中选一个网络中选一个网络中选一个网络中选一个没有直接前驱（度为没有直接前驱（度为没有直接前驱（度为没有直接前驱（度为0 0）的顶点的顶点的顶点的顶点,输出；输出；输出；输出；从图中删去该顶点从图中删去该顶点从图中删去该顶点从图中删去该顶点,同时删去所有它发出的有向边同时删去所有它发出的有向边同时删去所有它发出的有向边同时删去所有它发出的

46、有向边;重复以上重复以上重复以上重复以上 ,直到输出所有顶点或没有度为直到输出所有顶点或没有度为直到输出所有顶点或没有度为直到输出所有顶点或没有度为0 0的顶点。的顶点。的顶点。的顶点。C1,C2,C3,C4,C5,C6,C8,C9,C7或或 C1,C8,C9,C2,C5,C3,C4,C7,C6第47页/共58页C0C1C2C3C4C5拓扑排序的过程拓扑排序的过程(a)有向无环图有向无环图C2C5C1C0C3(b)输出顶点输出顶点C4C4C1C2C5C3(c)输出顶点输出顶点C0C0C2C5C1C3(d)输出顶点输出顶点C3第48页/共58页V1V2V3V4V5V6V3123456240012

47、V1V2V3V4V5V6 2 26 126 2 拓扑序列：V331V4V410V5V5020V1V11V6V60V2V2 51 第49页/共58页关键路径关键路径(Critical Path)(AOE网络网络)顶点V Vi i表示事件，弧a ak k表示活动，其权值为该活动持续的时间。每个事件发生时在它之前的活动已经完成，在它之后的活动可是开始。问题：（1）工程至少需要多少时间？最短时间（2）哪些活动是影响工程进度的关键？关键路径a9=21325a1=6a2=47689a10=2a8=7a5=1a6=3a7=9a3=5a4=14a11=4第50页/共58页几个与计算关键活动有关的量：几个与计算

48、关键活动有关的量：事件事件事件事件V Vi i 的最早可能开始时间的最早可能开始时间的最早可能开始时间的最早可能开始时间VeVe(i i)事件事件事件事件V Vi i 的最迟允许开始时间的最迟允许开始时间的最迟允许开始时间的最迟允许开始时间VlVl i i 活动活动活动活动a ak k 的最早可能开始时间的最早可能开始时间的最早可能开始时间的最早可能开始时间 e e k k 活动活动活动活动a ak k 的最迟允许开始时间的最迟允许开始时间的最迟允许开始时间的最迟允许开始时间 l l k k 时间余量时间余量时间余量时间余量 l l k k-e e k k a9=21325a1=6a2=476

49、89a10=2a8=5a5=1a6=3a7=9a3=5a4=14a11=4第51页/共58页Ve 1 2 3 4 5 6 7 8 90a9=21325a1=6a2=47689a10=2a8=5a5=1a6=3a7=9a3=5a4=14a11=4 事件V Vi i 的最早可能开始时间VeVe(i i)64578 16 12 18Ve1=0 Vej=MaxVei+dut(i,j)最短时间第52页/共58页Vl 1 2 3 4 5 6 7 8 918a9=21325a1=6a2=47689a10=2a8=5a5=1a6=3a7=9a3=5a4=14a11=4 事件V Vi i 的最迟允许开始时间Vl

50、Vl i i 14161279660Vln=Vl n=18 Vlj=MinVli-dut(i,j)第53页/共58页a9=21325a1=6a2=47689a10=2a8=5a5=1a6=3a7=9a3=5a4=14a11=4 活动a ak k 的最早可能开始时间 e e k k Ve 1 2 3 4 5 6 7 8 9064578 16 12 18e 1 2 3 4 5 6 7 8 9 10 11000645778 16 12第54页/共58页a9=21325a1=6a2=47689a10=2a8=5a5=1a6=3a7=9a3=5a4=14a11=4 活动a ak k 的最迟允许开始时间