广度优先遍历BFS课件.ppt

1、四川大学四川大学 计算机计算机(软件软件)学院学院图的类型定义图的类型定义 n(n0)个元素的有个元素的有限集合限集合四川大学四川大学 计算机计算机(软件软件)学院学院基基 本本 术术 语语四川大学四川大学 计算机计算机(软件软件)学院学院 图图是由一个是由一个顶点集顶点集V和一个和一个弧集弧集VR构构 成的数据结构成的数据结构 Graph=(V,VR)其中其中:VR|v,wV 且且 P(v,w)表示从表示从 v 到到 w 的一条弧，并称的一条弧，并称 v 为为弧尾弧尾，w 为为弧头弧头 谓词谓词 P(v,w)定义了弧定义了弧 的意义的意义或信息或信息四川大学四川大学 计算机计算机(软件软件)

2、学院学院 由于由于“弧弧”是有方向的，因此称由是有方向的，因此称由 顶点集和弧集构成的图为顶点集和弧集构成的图为有向图有向图 AB E C D 例如例如:G1=(V1,VR1)其中其中:V1=A,B,C,D,EVR1=,四川大学四川大学 计算机计算机(软件软件)学院学院若有若有 VR,必必有有 VR,则称则称(v,w)为顶点为顶点v和顶和顶点点w之间存在一条之间存在一条边边 B CA D F E由顶点集和边集构由顶点集和边集构成的图称作成的图称作无向图无向图例如例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=,四川大学四川大学 计算机计算机(软件软件)学院学院名词和术语名词和术

3、语网、子图网、子图 完全图完全图、稀疏图、稠密图稀疏图、稠密图邻接点、度、入度、出度邻接点、度、入度、出度路径、路径长度、简单路径路径、路径长度、简单路径、简单回路简单回路连通图、连通分量、连通图、连通分量、强连通图、强连通分量强连通图、强连通分量生成树、生成森林生成树、生成森林关节点、重连通图关节点、重连通图重连通分量、连通度重连通分量、连通度四川大学四川大学 计算机计算机(软件软件)学院学院AEFBBC设图设图G=(V,VR)和和图图G=(V,VR ),且且VV,VRVR,则则称称 G 为为 G 的的子图子图ABECF1597211132弧或边带权的图分弧或边带权的图分别称作别称作有向网有

4、向网或或无无向网向网四川大学四川大学 计算机计算机(软件软件)学院学院假设图中有假设图中有 n 个顶点，个顶点，e 条边，则条边，则 含有含有 e=n(n-1)/2 条边的无向图称条边的无向图称作作无向完全图无向完全图 含有含有 e=n(n-1)条弧的有向图称条弧的有向图称作作有向完全图有向完全图 若边或弧的个数若边或弧的个数 enlogn，则称，则称作作稀疏图稀疏图，否则称作，否则称作稠密图稠密图四川大学四川大学 计算机计算机(软件软件)学院学院 假若顶点假若顶点v 和顶点和顶点w 之间存在一条之间存在一条边，则称顶点边，则称顶点v和和w互为互为邻接点邻接点，边，边(v,w)(v,w)ID(

5、B)=3ID(A)=2和顶点和顶点v和和w相相关联关联 和顶点和顶点v 关联的边的数目定义为顶关联的边的数目定义为顶点的点的度度ACDFEB四川大学四川大学 计算机计算机(软件软件)学院学院顶点的顶点的出度出度:以顶点以顶点v为弧尾的弧的数目为弧尾的弧的数目ABECF有向图有向图顶点的顶点的入度入度:以顶点以顶点v v为弧头的弧的数目为弧头的弧的数目顶点的顶点的度度(TD)=)=出度出度(OD)+)+入度入度(ID)ID(B)=2OD(B)=1TD(B)=3四川大学四川大学 计算机计算机(软件软件)学院学院设图设图G=(V,VR)中的一个顶点序列中的一个顶点序列 u=vi,0,vi,1,vi,

6、m=w中中，(vi,j-1,vi,j)VR 1jm,则称从顶点则称从顶点u 到顶点到顶点w 之之间存在一条间存在一条路径路径。路径上。路径上边的数目称作边的数目称作路径长度路径长度ABECF长度为长度为3的路径的路径A,B,C,F四川大学四川大学 计算机计算机(软件软件)学院学院ABECF简单路径简单路径:序列中顶点序列中顶点不重复出现的路径不重复出现的路径简单回路简单回路:序列中第一序列中第一个顶点和最后一个顶个顶点和最后一个顶点相同的路径点相同的路径四川大学四川大学 计算机计算机(软件软件)学院学院若图若图G中任意两个中任意两个顶点之间都有路径顶点之间都有路径相通，则称此图为相通，则称此图

7、为连通图连通图若无向图为非连通若无向图为非连通图，则图中各个极图，则图中各个极大连通子图称作此大连通子图称作此图的图的连通分量连通分量BACDFEBACDFE四川大学四川大学 计算机计算机(软件软件)学院学院 若任意两个顶点之间若任意两个顶点之间都存在一条有向路径，则称此有向图都存在一条有向路径，则称此有向图为为强连通图强连通图,ABECFABECF对有向图，对有向图，否则，其各个强连通子否则，其各个强连通子图称作它的图称作它的强连通分量强连通分量四川大学四川大学 计算机计算机(软件软件)学院学院假设一个连通图有假设一个连通图有n个顶点和个顶点和e条边，其条边，其中中n-1 条边和条边和n个顶

8、点构成一个极小连通个顶点构成一个极小连通子图，称该极小连通子图为此连通图的子图，称该极小连通子图为此连通图的生成树生成树对非连通图，则对非连通图，则称由各个连通分称由各个连通分量的生成树的集量的生成树的集合为此非连通图合为此非连通图的的生成森林生成森林BACDFE四川大学四川大学 计算机计算机(软件软件)学院学院 没有关节点的连通图被称为没有关节点的连通图被称为重连重连通图通图 若连通图中的某个顶点和其相关若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称成两个或两个以上的连通分量，则称此顶点为此顶点为关节点关节点四川大

9、学四川大学 计算机计算机(软件软件)学院学院 一个连通图一个连通图G G如果不是重连通图，如果不是重连通图，那么它可以包括几个那么它可以包括几个重连通分量重连通分量 若依次删除一个连通图中的若依次删除一个连通图中的 1,2,1,2,k-1,k-1个顶点后个顶点后,该图仍连通该图仍连通,删除第删除第k k个顶个顶点后该图成为不连通的点后该图成为不连通的,则称该图的则称该图的连通度连通度为为k k四川大学四川大学 计算机计算机(软件软件)学院学院结构的建立和销毁结构的建立和销毁插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作对顶点的访问操作对顶点的访问操作顶点的遍历顶点的遍历插入和删除弧插

10、入和删除弧基本操作基本操作四川大学四川大学 计算机计算机(软件软件)学院学院CreatGraph(&G,V,VR):/按定义按定义(V,VR)构造图构造图DestroyGraph(&G):/销毁图销毁图结构的建立和销毁结构的建立和销毁四川大学四川大学 计算机计算机(软件软件)学院学院对顶点的访问操作对顶点的访问操作LocateVex(G,u);/若若G中存在顶点中存在顶点u，则返回该顶点在，则返回该顶点在/图中图中“位置位置”；否则返回其它信息；否则返回其它信息GetVex(G,v);/返回返回 v 的值的值PutVex(&G,v,value);/对对 v 赋值赋值value四川大学四川大学

11、计算机计算机(软件软件)学院学院对邻接点的操作对邻接点的操作FirstAdjVex(G,v);/返回返回v的的“第一个邻接点第一个邻接点”。若该顶点。若该顶点 /在在G中没有邻接点，则返回中没有邻接点，则返回“空空”NextAdjVex(G,v,w);/返回返回v的（相对于的（相对于w的）的）“下一个邻接下一个邻接/点点”。若。若w是是v的最后一个邻接点，则的最后一个邻接点，则/返回返回“空空”四川大学四川大学 计算机计算机(软件软件)学院学院插入或删除顶点插入或删除顶点InsertVex(&G,v);/在图在图G中增添新顶点中增添新顶点vDeleteVex(&G,v);/删除删除G中顶点中顶

12、点v及其相关的弧及其相关的弧四川大学四川大学 计算机计算机(软件软件)学院学院插入和删除弧插入和删除弧InsertArc(&G,v,w);/在在G中增添弧中增添弧，若，若G是无向的，是无向的，/则还增添对称弧则还增添对称弧DeleteArc(&G,v,w);/在在G中删除弧中删除弧，若，若G是无向的，是无向的，/则还删除对称弧则还删除对称弧四川大学四川大学 计算机计算机(软件软件)学院学院遍遍 历历DFSTraverse(G,v,Visit();/从顶点从顶点v起起深度优先深度优先遍历图遍历图G，并对每，并对每/个顶点调用函数个顶点调用函数Visit一次且仅一次一次且仅一次BFSTravers

13、e(G,v,Visit();/从顶点从顶点v起起广度优先广度优先遍历图遍历图G，并对每，并对每/个顶点调用函数个顶点调用函数Visit一次且仅一次一次且仅一次四川大学四川大学 计算机计算机(软件软件)学院学院图的存储表示图的存储表示一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示二、图的邻接表存储表示二、图的邻接表存储表示四、有向图的十字链表存储表示四、有向图的十字链表存储表示 五、无向图的邻接多重表存储表示五、无向图的邻接多重表存储表示三、图的逆邻接表存储表示三、图的逆邻接表存储表示四川大学四川大学 计算机计算机(软件软件)学院学院Aij=0 (i,j)VR1 (i,j)VR图的

14、数组(邻接矩阵)存储表示BACDFE定义定义:矩阵的元素为矩阵的元素为四川大学四川大学 计算机计算机(软件软件)学院学院有向图的邻接矩有向图的邻接矩阵为非对称矩阵阵为非对称矩阵ABECD0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院网（边或弧带权值的图）的数组(邻接矩阵)存储表示如下否则或如VRvvvvwAjijiijij),(,593553182252四川大学四川大学 计算机计算机(软件软件)学院学院0 A 1 41 B 0 4 52 C 3 53

15、D 2 54 E 0 15 F 1 2 3BACDFE图的邻接表存储表示图的邻接表存储表示四川大学四川大学 计算机计算机(软件软件)学院学院 0 1 2 3 4有向图的邻接表有向图的邻接表1 4230 12 A B C D EABECD可见，在有向图的可见，在有向图的邻接表中不易找到邻接表中不易找到指向该顶点的弧指向该顶点的弧四川大学四川大学 计算机计算机(软件软件)学院学院ABECD在有向图的在有向图的邻接表中，邻接表中，对每个顶点，对每个顶点，链接的是指链接的是指向该顶点的向该顶点的弧弧图的逆邻接表存储表示图的逆邻接表存储表示 A B C D E 033420 012341四川大学四川大学

16、 计算机计算机(软件软件)学院学院有向图的十字链表存储表示有向图的十字链表存储表示 弧的结点结构弧的结点结构弧尾顶点位置 弧头顶点位置 弧的相关信息指向下一个有相同弧头有相同弧头的结点指向下一个有相同弧尾有相同弧尾的结点typedef struct ArcBox /弧弧的结构表示的结构表示 int tailvex,headvex;InfoType *info;struct ArcBox *hlink,*tlink;VexNode;四川大学四川大学 计算机计算机(软件软件)学院学院顶点的结点结构顶点的结点结构顶点信息数据 指向该顶点的第一条入弧第一条入弧指向该顶点的第一条出弧第一条出弧typed

17、ef struct VexNode /顶点的结构表示顶点的结构表示 VertexType data;ArcBox *firstin,*firstout;VexNode;四川大学四川大学 计算机计算机(软件软件)学院学院typedef struct VexNode xlistMAX_VERTEX_NUM;/顶点结点(表头向量)int vexnum,arcnum;/有向图的当前顶点数和弧数 OLGraph;有向图的结构表示有向图的结构表示(十字链表十字链表)四川大学四川大学 计算机计算机(软件软件)学院学院对右边所示的有向图G,十字链表表示如下:四川大学四川大学 计算机计算机(软件软件)学院学院无

18、向图的邻接多重表存储表示typedef struct Ebox VisitIf mark;/访问标记 int ivex,jvex;/该边依附的两个顶点的位置 struct EBox *ilink,*jlink;InfoType *info;/该边信息指针 EBox;边的结构表示边的结构表示四川大学四川大学 计算机计算机(软件软件)学院学院typedef struct /邻接多重表邻接多重表 VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;AMLGraph;顶点的结构表示顶点的结构表示typedef struct VexBox VertexTy

19、pe data;EBox *firstedge;/指向第一条依附该顶点的边 VexBox;无向图的结构表示无向图的结构表示四川大学四川大学 计算机计算机(软件软件)学院学院对右边所示的无向图G,邻接多重表表示如下:四川大学四川大学 计算机计算机(软件软件)学院学院图的遍历图的遍历四川大学四川大学 计算机计算机(软件软件)学院学院前进前进回退回退ACDEGBFIHACDEGBFIH123456789123456789深度优先遍历过程深度优先遍历过程 深度优先生成树深度优先生成树四川大学四川大学 计算机计算机(软件软件)学院学院ACDEGBFIHACDEGBFH123456789123456789

20、广度优先遍历过程广度优先遍历过程 广度优先生成树广度优先生成树I四川大学四川大学 计算机计算机(软件软件)学院学院void traverse(int n,Graph g)for(v=0;v n;v+)visitedv=false;for(v=0;v n;v+)if(!visitedv)dfs(v,g)或或 bfs(v,g);四川大学四川大学 计算机计算机(软件软件)学院学院void dfs(int v,Graph g)cout=0;w=NextAdjVex(g,v,w)if(!visitedw)dfs(w,g)四川大学四川大学 计算机计算机(软件软件)学院学院void bfs(int v,Gr

21、aph g)cout=0;w=NextAdjVex(g,v,w)if(!visitedw)cout GetVex(g,w);EnQueue(q,w);visitedw =true;四川大学四川大学 计算机计算机(软件软件)学院学院最小代价生成树最小代价生成树(minimum cost spanning tree)四川大学四川大学 计算机计算机(软件软件)学院学院 假设要在假设要在 n 个城市之间建立通讯个城市之间建立通讯联络网，则连通联络网，则连通 n 个城市只需要修建个城市只需要修建 n-1 条线路，条线路，如何在最节省经费的前如何在最节省经费的前提下建立提下建立这个这个通讯网通讯网？问题问

22、题四川大学四川大学 计算机计算机(软件软件)学院学院 构造网的一棵最小生成树，即：构造网的一棵最小生成树，即：在在 e 条带权的边中选取条带权的边中选取n-1条边（不条边（不构成回路），使构成回路），使“权值之和权值之和”为最小为最小该问题等价于该问题等价于四川大学四川大学 计算机计算机(软件软件)学院学院构造最小生成树的准则构造最小生成树的准则n必须使用且仅使用该网络中的必须使用且仅使用该网络中的n-1 条边来联结网络中的条边来联结网络中的 n 个顶点个顶点n不能使用产生回路的边不能使用产生回路的边n各边上的权值的总和达到最小各边上的权值的总和达到最小四川大学四川大学 计算机计算机(软件软件

23、)学院学院算法二：克鲁斯卡尔算法算法二：克鲁斯卡尔算法 算法一：普里姆算法算法一：普里姆算法 (Prim)四川大学四川大学 计算机计算机(软件软件)学院学院普里姆算法的普里姆算法的基本思想基本思想四川大学四川大学 计算机计算机(软件软件)学院学院 1.取图中任意一个顶点取图中任意一个顶点 v 作为作为 生成树的根，之后往生成树生成树的根，之后往生成树 上添加新的顶点上添加新的顶点 w四川大学四川大学 计算机计算机(软件软件)学院学院 2.在在生成树的构造过程中，图中生成树的构造过程中，图中 n 个个顶点分属两个集合：顶点分属两个集合：已落在生成树上的顶点已落在生成树上的顶点集集 U 和和尚未落

24、在生成树上的顶点集尚未落在生成树上的顶点集V-U，则则应在所有连通应在所有连通U中顶点和中顶点和V-U中顶点的边中选中顶点的边中选取权值最小的边取权值最小的边(v,w)这里这里v属于属于V，w属于属于UUV-U四川大学四川大学 计算机计算机(软件软件)学院学院 3.之后继续往生成树上添加顶之后继续往生成树上添加顶 点，直至生成树上含有点，直至生成树上含有 n-1 个顶点为止个顶点为止四川大学四川大学 计算机计算机(软件软件)学院学院abcdegf195141827168213ae12dcbgf7148531621所得生成树权值和所得生成树权值和=14+8+3+5+16+21=67四川大学四川大

25、学 计算机计算机(软件软件)学院学院252510504613228102514242216185046132504613210原图 (a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212四川大学四川大学 计算机计算机(软件软件)学院学院克鲁斯卡尔算法的克鲁斯卡尔算法的基本思想基本思想四川大学四川大学 计算机计算机(软件软件)学院学院具体做法具体做法:先构造一个只含先构造一个只含 n 个顶点的个顶点的子图子图 SG，然后从权值最小的边开始，然后从权值最小的边开始，若它的添加不使若它的添加不使SG 中产生回路，则在中产生回

26、路，则在 SG 上加上这条边，如此重复，直至加上加上这条边，如此重复，直至加上上 n-1 条边为止条边为止考虑问题的出发点考虑问题的出发点:为使生成树上为使生成树上边边的权值之和达到最小的权值之和达到最小，则应使生成树，则应使生成树中每一条边的权值尽可能地小中每一条边的权值尽可能地小四川大学四川大学 计算机计算机(软件软件)学院学院abcdegf195141827168213ae12dcbgf71485316217121819四川大学四川大学 计算机计算机(软件软件)学院学院10504613228102514242216181250461325046132原图 (a)(b)四川大学四川大学 计

27、算机计算机(软件软件)学院学院1012504613228102514242216181250461325046132101412原图 (c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院学生课程学习工程图学生课程学习工程图C8C3C5C4C9C6C7C1C2四川大学四川大学 计算机计算机(软件软件)学院学院拓扑排序拓扑排序(TopologicalSort)按照有向图给

28、出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系 由此所得顶点的线性序列称之为拓扑有序序列四川大学四川大学 计算机计算机(软件软件)学院学院例如：对于下列有向图例如：对于下列有向图BDAC可求得可求得拓扑有序序列拓扑有序序列：A B C D 或或 A C B D四川大学四川大学 计算机计算机(软件软件)学院学院BDAC反之，对于下列有向图反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路因为图中存在一个回路 B,C,D四川大学四川大学 计算机计算机(软件软件)学院学院进行拓扑排序的步骤进行拓扑排序的步骤一、从有向图中选取

29、一个没有前驱一、从有向图中选取一个没有前驱 的顶点，并输出之的顶点，并输出之 重复上述两步，直至图空，或者重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止图不空但找不到无前驱的顶点为止二、从有向图中删去此顶点以及所二、从有向图中删去此顶点以及所 有以它为尾的弧有以它为尾的弧四川大学四川大学 计算机计算机(软件软件)学院学院abcghdfeabhcdgfe四川大学四川大学 计算机计算机(软件软件)学院学院在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念 没有前驱的顶点没有前驱的顶点 入度为零的顶点入度为零的顶点 删除顶点及以它为尾的弧删除顶点及以它为尾的弧

30、弧头顶点的入度减弧头顶点的入度减1四川大学四川大学 计算机计算机(软件软件)学院学院C8C3C5C4C9C6C7C1C2四川大学四川大学 计算机计算机(软件软件)学院学院C0C1C2C3C4C5(a)有向无环图有向无环图C2C5C1C0C3(b)输出顶点输出顶点C4C1C2C5C3(c)输出顶点输出顶点C0C4C0C2C5C1C3(d)输出顶点输出顶点C3四川大学四川大学 计算机计算机(软件软件)学院学院C1C2C5(e)输出顶点输出顶点C2C5C1(f)输出顶点输出顶点C1C5(g)输出顶点输出顶点C5(h)拓扑排序完成拓扑排序完成四川大学四川大学 计算机计算机(软件软件)学院学院在算法中在

31、算法中,使用一使用一个个堆栈堆栈或或队列队列存放入度存放入度为零的顶点为零的顶点,供选择和供选择和输出无前驱的顶点输出无前驱的顶点四川大学四川大学 计算机计算机(软件软件)学院学院012345C0C1C2C3C4C5 C0 C1 C2 C3 0 C4 C5 0count data adj 130103 1 dest link 3 0 5 1 5 0 0 1 5 0四川大学四川大学 计算机计算机(软件软件)学院学院在算法中在算法中,使用一使用一个个堆栈堆栈或或队列队列存放入度存放入度为零的顶点为零的顶点,供选择和供选择和输出无前驱的顶点输出无前驱的顶点四川大学四川大学 计算机计算机(软件软件)学

32、院学院四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院指向新栈顶指向新栈顶 原栈顶元素在原栈顶元素在中中退到次退到次 栈顶栈顶四川大学四川大学 计算机计算机(软件软件)学院学院C0C1C2C3C4C513010313112322-112221-1222012345012345012345012345toptoptoptoptoptoptoptop四川大学四川大学 计算机计算机(软件软件)学院学院C0C1C2C3C4C52112222112212

33、-1-122-12-1-122-1012345012345012345012345toptoptoptoptoptop四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院void Graph:TopologicalSort()int top=-1;/入度为零的顶点栈初始化入度为零的顶点栈初始化 for(int i=0;in;i+)/入度为零顶点入度为零顶点 if(counti=0)/进栈进栈 counti=top;top=i;for(i=0;in;i+)/期望输出期望输出n个顶点个顶点 if(top=-1)/中途栈空中途栈空,转出转出 cout“

34、网络中有回路！网络中有回路！endl;return;四川大学四川大学 计算机计算机(软件软件)学院学院 else /继续拓扑排序继续拓扑排序 int j=top;top=counttop;/退栈退栈 coutj-dest;/另一顶点另一顶点四川大学四川大学 计算机计算机(软件软件)学院学院 if(-countk=0)/顶点入度减一顶点入度减一 countk=top;top=k;/顶点的入度顶点的入度减至零减至零,进栈进栈 p=p-link;四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院关键路径关键路径问题问题:假设以有向网表示一个施工流程假

35、设以有向网表示一个施工流程 图，弧上的权值表示完成该项子图，弧上的权值表示完成该项子 工程所需时间。工程所需时间。问：问：哪些子工程项是哪些子工程项是“关键工程关键工程”？即：即：哪些子工程项将影响整个工程的哪些子工程项将影响整个工程的 完成期限完成期限四川大学四川大学 计算机计算机(软件软件)学院学院abcdefghk64521187244例如例如:整个工程完成的时间为整个工程完成的时间为：从有向图的：从有向图的源源点点到到汇点汇点的最长路径的最长路径源点汇点6174四川大学四川大学 计算机计算机(软件软件)学院学院用有向边表示一个工程中的活动用有向边表示一个工程中的活动 (Activity

36、),用边上权值表示活动持续用边上权值表示活动持续时间时间 (Duration),用顶点表示事件用顶点表示事件 (Event)“关键活动关键活动”指的是：指的是：该弧上的该弧上的权值增加权值增加 将使有向图上的将使有向图上的最长路径的最长路径的长度增加长度增加四川大学四川大学 计算机计算机(软件软件)学院学院完成整个工程所需的时间取决完成整个工程所需的时间取决于从源点到汇点的最长路径长于从源点到汇点的最长路径长度度,即在这条路径上所有活动即在这条路径上所有活动的持续时间之和的持续时间之和。这条路径长。这条路径长度最长的路径就叫做度最长的路径就叫做关键路径关键路径四川大学四川大学 计算机计算机(软

37、件软件)学院学院 如何求关键活动？如何求关键活动？四川大学四川大学 计算机计算机(软件软件)学院学院假设第假设第 i i 条弧为条弧为 对第对第 j j 个顶点而言个顶点而言“事件事件(顶点顶点)”)”的最早发生时间的最早发生时间 veve(j j)“事件事件(顶点顶点)”)”的最迟发生时间的最迟发生时间 vlvl(j j)对第对第 i i 项活动而言项活动而言“活动活动(弧弧)”)”的最早开始时间的最早开始时间 eeee(i i)“活动活动(弧弧)”)”的最迟开始时间的最迟开始时间 elel(i i)四川大学四川大学 计算机计算机(软件软件)学院学院veve(源点源点)=0=0；veve(k

38、 k)=MaxMax veve(j j)+dutdut()(2 2=k k=n n,属于所有以属于所有以k k为为 头头的弧的集合的弧的集合)vlvl(汇点汇点)=veve(汇点汇点)；vlvl(j j)=MinMin vlvl(k k)dutdut()(1 1=j j=n-1n-1,属于所有以属于所有以j j为为 尾尾的弧的集合的弧的集合)四川大学四川大学 计算机计算机(软件软件)学院学院附注“事件(顶点)”的 最早发生时间 ve(j)ve(j)=从源点到顶点j的最长路径长度；“事件(顶点)”的 最迟发生时间 vl(k)vl(k)=从源点到汇点的最长路径长度-从顶点k到汇点的最长路径长度。四

39、川大学四川大学 计算机计算机(软件软件)学院学院eeee(i i)=veve(j j)elel(i i)=vlvl(k k)dutdut()veve(源点源点)=vlvl(源点源点)=0=0vlvl(汇点汇点)=veve(汇点汇点)关键活动关键活动:elel(i i)=eeee(i i)四川大学四川大学 计算机计算机(软件软件)学院学院 这两个递推公式的计这两个递推公式的计算必须分别在算必须分别在拓扑有序拓扑有序及及逆拓扑有序逆拓扑有序的前提下进行的前提下进行四川大学四川大学 计算机计算机(软件软件)学院学院abcdefghk64521187244a b c d efg h kvevl0000

40、000006457115 715 14 1818181818181818181816 1486610807拓扑有序序列拓扑有序序列:a-d-f-c-b-e-h-g-k四川大学四川大学 计算机计算机(软件软件)学院学院a b c d efg h kvevl06457715 14 18181416107866000064577715 14141602366887 10四川大学四川大学 计算机计算机(软件软件)学院学院显然显然 求求ve的顺序应该是的顺序应该是按拓扑有序按拓扑有序的的 次序次序 而而 求求vl的顺序应该是的顺序应该是按拓扑逆序按拓扑逆序的的 次序次序因为因为 拓扑逆序序列即为拓扑有序

41、序列拓扑逆序序列即为拓扑有序序列 的的逆序列逆序列因此因此 应该在拓扑排序的过程中，应该在拓扑排序的过程中，另设一个另设一个“栈栈”记下拓扑有序序记下拓扑有序序列列四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院四川大学四川大学 计算机计算机(软件软件)学院学院 依依最短路径的长最短路径的长度度递增的次序求得各递增的次序求得各条路径条路径源点源点v1 其中，从源其中，从源点到顶点点到顶点v的最的

42、最短路径是所有最短路径是所有最短路径中长度最短路径中长度最短者短者v2四川大学四川大学 计算机计算机(软件软件)学院学院 在这条路径上，必定只含一条弧，并且这条弧的权值最小。下一条路径长度次短(第1次)的最短路径最短路径的特点：路径长度最短(第0次)的最短路径最短路径的特点：它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。四川大学四川大学 计算机计算机(软件软件)学院学院其余最短路径(第k次)的特点：再下一条路径长度次短(第2次)的最短路径最短路径的特点:它可能有两种情况：或者是从源点不经过v2到该点；或者是从源点到顶点v2，再

43、到达该顶点。它或者是从源点不经过vk到该点；或者是从源点到vk，再到达该顶点。四川大学四川大学 计算机计算机(软件软件)学院学院求最短路径的迪杰斯特拉算法：设置辅助数组Dist，其中每个分量Distk 表示 当前所求得的从源点到其余各顶点 k 的最短路径。四川大学四川大学 计算机计算机(软件软件)学院学院1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的Distk值。假设求得最短路径的顶点为u，若若 Distu+G.arcsukDistk则将 Distk 改为 Distu+G.arcsuk。INFINITYkvarcsGkDist0.V0和k之间存在弧V0

44、和k之间不存在弧其中的最小值即为最短路径的长度其中的最小值即为最短路径的长度。四川大学四川大学 计算机计算机(软件软件)学院学院求每一对顶点之间的最短路径求每一对顶点之间的最短路径弗洛伊德算法的基本思想是：弗洛伊德算法的基本思想是：从从 v vi i 到到 v vj j 的所有可能存在的的所有可能存在的路径中，选出一条长度最短的路径路径中，选出一条长度最短的路径四川大学四川大学 计算机计算机(软件软件)学院学院顶点集为V=v1,v2,.vn第0步:若存在,则存在路径vi,vj/路径中不含其它顶点,相当于中间点集U=A0ij=G.arcsij(编程序时不写上标，即为Aij=G.arcsij)第1步:若,存在，则存在路径vi,v1,vj/路径中所含顶点序号不大于1,相当于中间点集U=v1A1ij=MINA0ij,A0i1+A01j第2步:若vi,v2,v2,vj存在，则存在一条路径vi,v2,vj/路径中所含顶点序号不大于2号,相当于中间点集U=v1,vnA1ij=MINA0ij,A0i1+A01j 第n步:若vi,vn,vn,vj存在，则存在一条路径vi,vn,vj/路径中所含顶点序号不大于n号,相当于中间点集U=V,为最短路径Anij=MINAn-1ij,An-1in+An-1nj