《第03基本数据结构与运算优秀课件.ppt》由会员分享，可在线阅读，更多相关《第03基本数据结构与运算优秀课件.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第03基本数据结构与运算基本数据结构与运算第1页，本讲稿共50页3.6.1图的基本概念BACD63215数据结构数据结构 B=B=（D D，R R）图：图：G=G=（V V，E E）顶点顶点:图中的数据元素图中的数据元素V V：表示：表示顶顶点的非空有限集合。点的非空有限集合。E E：表示两个顶点之间关系的集合。：表示两个顶点之间关系的集合。图的定义、术语第2页，本讲稿共50页图有向图无向图在有向图中，在有向图中，V 表示从表示从V V1 1到到V V3 3的一条弧。的一条弧。V V1 1为弧尾或初始点，为弧尾或初始点，V V3 3为弧头或终端点。为弧头或终端点。在无向图中，在无向图中，(V
2、(V1 1，V V3 3)表示表示V V1 1和和V V3 3之间的一条边之间的一条边。V1V3V2V4V1V3V2V4图的定义、术语第3页，本讲稿共50页V1V3V2V4V1V3V2V4顶点集合V=V1，V2，V3，V4弧的集合G=,顶点集合V=V1，V2，V3，V4边的集合E=(V1,V3),(V1,V2),(V1,V4),(V2,V4)G=(V,E)顶点(V1,V3)与(V3,V1)表示同一条边图的定义、术语第4页，本讲稿共50页BACD63215权：与图的边或弧相关的数。顶点的度顶点的度：依附于该顶点的边数或弧数。：依附于该顶点的边数或弧数。出度出度：（仅对有向图）以该顶点为尾的弧数。
3、：（仅对有向图）以该顶点为尾的弧数。入度入度：（仅对有向图）以该顶点为头的弧数。：（仅对有向图）以该顶点为头的弧数。路径路径：顶点：顶点A A与顶点与顶点C C之间存在一条路径。路径上边或弧的数目之间存在一条路径。路径上边或弧的数目 称为该路径的路径长度。称为该路径的路径长度。连通图连通图：无向图任意两顶点都有路径（：无向图任意两顶点都有路径（没有孤立顶点）没有孤立顶点）没有孤立顶点）没有孤立顶点）强连通图强连通图：有向图有向图任意两顶点都有路径任意两顶点都有路径网网网网：带权的图称为网：带权的图称为网：带权的图称为网：带权的图称为网图的定义、术语第5页，本讲稿共50页图的存储图的存储 邻接矩
4、阵邻接矩阵n n3.6.2 图的存储图的存储n n1.邻接矩阵法邻接矩阵法uu（1 1）给顶点编号）给顶点编号）给顶点编号）给顶点编号uu（2 2）建立邻接（关系）矩阵）建立邻接（关系）矩阵）建立邻接（关系）矩阵）建立邻接（关系）矩阵214312341 2 3 40 0 0 01 0 1 11 0 0 10 1 1 0a a i j i j表示弧表示弧 ij 1 1：表示有弧；：表示有弧；0:0:表示无弧表示无弧任意顶点的出度是该行元素之和任意顶点的出度是该行元素之和任意顶点的出度是该行元素之和任意顶点的出度是该行元素之和任意顶点的入度是该列元素之和任意顶点的入度是该列元素之和任意顶点的入度是
5、该列元素之和任意顶点的入度是该列元素之和第6页，本讲稿共50页图的存储图的存储 邻接矩阵邻接矩阵uu邻接矩阵的优点：邻接矩阵的优点：邻接矩阵的优点：邻接矩阵的优点：增减边的操作简单增减边的操作简单增减边的操作简单增减边的操作简单uu邻接矩阵的缺点：邻接矩阵的缺点：邻接矩阵的缺点：邻接矩阵的缺点：增减顶点的操作需要搬移大量的元素，增减顶点的操作需要搬移大量的元素，增减顶点的操作需要搬移大量的元素，增减顶点的操作需要搬移大量的元素，浪费存储空间浪费存储空间浪费存储空间浪费存储空间21431 2 3 41 2 3 41 1 2 2 3 3 4 40110101111010110无向图的邻接矩阵是对称
6、的无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的第7页，本讲稿共50页图的存储图的存储 邻接矩阵的实现邻接矩阵的实现n n图的邻接矩阵实现图的邻接矩阵实现typedef struct graph_mtypedef struct graph_melemtype nodeMAXNUM;elemtype nodeMAXNUM;int arcsMAXNUMMAXNUM;int arcsMAXNUMMAXNUM;graph_m;graph_m;顶点集合顶点集合顶点集合顶点集合边的邻接矩阵边的邻接矩阵边的邻接矩阵边的邻接矩阵二维数组二维数组第8页，本讲稿共50页图的存储图的存储
7、邻接表邻接表n n2.邻接表法邻接表法uu一个邻接表由两种结构组成一个邻接表由两种结构组成一个邻接表由两种结构组成一个邻接表由两种结构组成存放各顶点元素的数组，头结点存放各顶点元素的数组，头结点存放各顶点元素的数组，头结点存放各顶点元素的数组，头结点各顶点各自的邻接链表，邻接结点各顶点各自的邻接链表，邻接结点各顶点各自的邻接链表，邻接结点各顶点各自的邻接链表，邻接结点2143231 data2data3data4data134124233data顶点号顶点号元素域元素域邻接链表邻接链表头指针头指针2邻接顶点号邻接顶点号下一邻接结点下一邻接结点第9页，本讲稿共50页图的存储（课堂练习）图的存储（
8、课堂练习）n n请写出下面这副图的邻接表请写出下面这副图的邻接表uu1 1）给顶点编号）给顶点编号）给顶点编号）给顶点编号uu2 2）建立顶点数组）建立顶点数组）建立顶点数组）建立顶点数组uu3 3）建立各顶点的邻接链表）建立各顶点的邻接链表）建立各顶点的邻接链表）建立各顶点的邻接链表注意，此图为有向图注意，此图为有向图注意，此图为有向图注意，此图为有向图2 21 13 34 45 51 1datadata2 2datadata3 3datadata4 4datadata5 5datadata2 23 31 13 35 51 14 4第10页，本讲稿共50页图的存储图的存储 邻接表的实现邻接表
9、的实现n n邻接表的定义邻接表的定义uu头结点的定义头结点的定义头结点的定义头结点的定义uu邻接结点的定义邻接结点的定义邻接结点的定义邻接结点的定义顶点号元素域与头结点与头结点与头结点与头结点相邻的顶点相邻的顶点相邻的顶点相邻的顶点typedef struct headnodetypedef struct headnodeint node_index;int node_index;elemtype data;elemtype data;struct adj_node*next_adj;struct adj_node*next_adj;headnode;headnode;顶点号下一个与头结点相邻
10、的下一个与头结点相邻的下一个与头结点相邻的下一个与头结点相邻的顶点的邻接结点顶点的邻接结点顶点的邻接结点顶点的邻接结点typedef struct adj_nodetypedef struct adj_nodeint node_index;int node_index;struct adj_node*next_adj;struct adj_node*next_adj;adj_node;adj_node;第11页，本讲稿共50页图的存储图的存储 邻接表邻接表uu图邻接表的定义图邻接表的定义图邻接表的定义图邻接表的定义typedef struct graph_ltypedef struct gra
11、ph_lheadnode node_listMAXNUM;headnode node_listMAXNUM;int node_num;int node_num;graph_l;graph_l;231 data2data3data4data13412423第12页，本讲稿共50页图的存储图的存储 邻接表邻接表2143231 data2data3data4data1341242321431 data2data3data4data134134注意：有向图与无向图的区别注意：有向图与无向图的区别注意：有向图与无向图的区别注意：有向图与无向图的区别第13页，本讲稿共50页图的存储图的存储n n图的邻接表
12、存储法的特点图的邻接表存储法的特点uu优点优点优点优点节省存储空间节省存储空间节省存储空间节省存储空间边的插入和删除操作比较简便边的插入和删除操作比较简便边的插入和删除操作比较简便边的插入和删除操作比较简便uu缺点缺点缺点缺点结构复杂结构复杂结构复杂结构复杂vv具有两种不同的基本组成单元具有两种不同的基本组成单元具有两种不同的基本组成单元具有两种不同的基本组成单元第14页，本讲稿共50页图的存储图的存储n n3.边带权值的图的存储边带权值的图的存储uu1 1）在邻接矩阵中的实现）在邻接矩阵中的实现）在邻接矩阵中的实现）在邻接矩阵中的实现0 2 3 520 1 031 0 15 0 1 0a44
13、=a44=a i j a i j：记录边的权值；为：记录边的权值；为：记录边的权值；为：记录边的权值；为0 0表示无边表示无边表示无边表示无边1 12 24 43 32 23 35 51 11 1第15页，本讲稿共50页图的存储图的存储n n3.边带权值的图的存储边带权值的图的存储uu2 2）在邻接表中的实现）在邻接表中的实现）在邻接表中的实现）在邻接表中的实现在邻接结点结构中增加一个权值域在邻接结点结构中增加一个权值域在邻接结点结构中增加一个权值域在邻接结点结构中增加一个权值域1 data2data3data4data233211354102331顶点号顶点号边权值边权值1 12 24 43
14、 33 32 25 51 11 110103 3第16页，本讲稿共50页图的遍历图的遍历n n3.6.3 图的遍历图的遍历n n问题：问题：uu1 1）对于连通图，从一个顶点出发沿着所有可能）对于连通图，从一个顶点出发沿着所有可能）对于连通图，从一个顶点出发沿着所有可能）对于连通图，从一个顶点出发沿着所有可能的路径，是否可以将所有的顶点遍历到。的路径，是否可以将所有的顶点遍历到。的路径，是否可以将所有的顶点遍历到。的路径，是否可以将所有的顶点遍历到。uu2 2）图中有回路，遍历算法可能产生死循环。）图中有回路，遍历算法可能产生死循环。）图中有回路，遍历算法可能产生死循环。）图中有回路，遍历算法
15、可能产生死循环。n n有重复的路径称为有重复的路径称为回路回路2143第17页，本讲稿共50页图的遍历图的遍历 深优深优n n1.深度优先遍历深度优先遍历uu（1 1）从一个未访问过的顶点开始，访问它的一个）从一个未访问过的顶点开始，访问它的一个）从一个未访问过的顶点开始，访问它的一个）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。未访问过的相邻顶点。未访问过的相邻顶点。未访问过的相邻顶点。uu（2 2）如果顶点的所有相邻顶点都是已访问过的，）如果顶点的所有相邻顶点都是已访问过的，）如果顶点的所有相邻顶点都是已访问过的，）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个
16、顶点，选取它的另一个则需要回溯到之前的一个顶点，选取它的另一个则需要回溯到之前的一个顶点，选取它的另一个则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。未被访问的相邻顶点。未被访问的相邻顶点。未被访问的相邻顶点。uu（3 3）对于前两个步骤是递归的）对于前两个步骤是递归的）对于前两个步骤是递归的）对于前两个步骤是递归的第18页，本讲稿共50页图的遍历图的遍历 深优深优n n1.深度优先遍历深度优先遍历uu（1 1）从一个未访问过的顶点开始，访问它的一个）从一个未访问过的顶点开始，访问它的一个）从一个未访问过的顶点开始，访问它的一个）从一个未访问过的顶点开始，访问它的一个未访问过的
17、相邻顶点。未访问过的相邻顶点。未访问过的相邻顶点。未访问过的相邻顶点。uu（2 2）如果顶点的所有相邻顶点都是已访问过的，）如果顶点的所有相邻顶点都是已访问过的，）如果顶点的所有相邻顶点都是已访问过的，）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个顶点，选取它的另一个则需要回溯到之前的一个顶点，选取它的另一个则需要回溯到之前的一个顶点，选取它的另一个则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。未被访问的相邻顶点。未被访问的相邻顶点。未被访问的相邻顶点。uu（3 3）对于前两个步骤是递归的）对于前两个步骤是递归的）对于前两个步骤是递归的）对于前两个步骤是递归的1
18、258463717365284回到8173 652841 3 6 8 4 2 5 7或者按以下顺序遍历：或者按以下顺序遍历：或者按以下顺序遍历：或者按以下顺序遍历：注意使用栈支持递归：注意使用栈支持递归：注意使用栈支持递归：注意使用栈支持递归：第19页，本讲稿共50页图的遍历图的遍历 深优深优n n深度优先遍历的特点深度优先遍历的特点uu“深度深度深度深度”：总是访问顶点的：总是访问顶点的：总是访问顶点的：总是访问顶点的一个一个一个一个相邻顶点，好像相邻顶点，好像相邻顶点，好像相邻顶点，好像是沿着图中的一条路径走到是沿着图中的一条路径走到是沿着图中的一条路径走到是沿着图中的一条路径走到“底底底
19、底”，然后后退一，然后后退一，然后后退一，然后后退一点，再选一条路。如此点，再选一条路。如此点，再选一条路。如此点，再选一条路。如此“进进退退进进退退进进退退进进退退”，直到所有，直到所有，直到所有，直到所有顶点都被访问顶点都被访问顶点都被访问顶点都被访问uu对于连通图，如果第一个被访问的顶点的所有相对于连通图，如果第一个被访问的顶点的所有相对于连通图，如果第一个被访问的顶点的所有相对于连通图，如果第一个被访问的顶点的所有相邻顶点都被访问了，意味着图中所有顶点都被访邻顶点都被访问了，意味着图中所有顶点都被访邻顶点都被访问了，意味着图中所有顶点都被访邻顶点都被访问了，意味着图中所有顶点都被访问了
20、。问了。问了。问了。即栈空时即栈空时即栈空时即栈空时第20页，本讲稿共50页图的遍历图的遍历 深优深优n n用递归调用实现深度优先遍历算法用递归调用实现深度优先遍历算法void dfs void dfs（g g，v v）1 1访问顶点访问顶点访问顶点访问顶点v v；visit（v）；）；visited v =1;p=gv-next_adjwhile(p!=NULL)w=p-node_index;if(visitedw=0)p=p-next_adj;2 2取得顶点的一个未被访问过的顶点取得顶点的一个未被访问过的顶点取得顶点的一个未被访问过的顶点取得顶点的一个未被访问过的顶点ww；3 dfs3 d
21、fs（g g，ww）；回到）；回到）；回到）；回到2 2；4 4重复重复重复重复2 2，3 3直到该顶点所有的相邻顶点都被访问过；直到该顶点所有的相邻顶点都被访问过；直到该顶点所有的相邻顶点都被访问过；直到该顶点所有的相邻顶点都被访问过；dfs(g,w);第21页，本讲稿共50页12345void dfs（g，v）visited v =1;p=g v-next_adj while(p!=NULL)w=p-node_index;if(visited w =0)dfs(g,w);p=p-next_adj;void dfs（g，2）visited 2 =1;p=g 2-next_adj while(
22、p!=NULL)w=p-node_index;if(visited 3 =0)dfs(g,3);p=p-next_adj;void dfs（g，3）visited 3 =1;p=g 3-next_adj while(p!=NULL)w=p-node_index;if(visited 4 =0)dfs(g,4);p=p-next_adj;void dfs（g，4）visited 4 =1;p=g 4-next_adj while(p!=NULL)w=p-node_index;if(visited w =0)dfs(g,w);p=p-next_adj;void dfs（g，5）visited 5
23、=1;p=g 5-next_adj while(p!=NULL)w=p-node_index;if(visited w =0)dfs(g,w);p=p-next_adj;void dfs（g，1）visited 1 =1;p=g 1-next_adj while(p!=NULL)w=p-node_index;if(visited 2 =0)dfs(g,2);p=p-next_adj;if(visited 5 =0)dfs(g,5);第22页，本讲稿共50页图的遍历图的遍历 广优广优n n2.广度优先遍历广度优先遍历uu访问顶点访问顶点访问顶点访问顶点v v后，接着依次访问后，接着依次访问后，接
24、着依次访问后，接着依次访问v v的所有邻接顶点，的所有邻接顶点，的所有邻接顶点，的所有邻接顶点，再依次访问这些邻接顶点的邻接顶点。直到所有再依次访问这些邻接顶点的邻接顶点。直到所有再依次访问这些邻接顶点的邻接顶点。直到所有再依次访问这些邻接顶点的邻接顶点。直到所有的顶点都被访问过。的顶点都被访问过。的顶点都被访问过。的顶点都被访问过。125846371 12 23 34 45 56 67 78 8注意：注意：注意：注意：8 8是作为哪个是作为哪个是作为哪个是作为哪个顶点的邻接顶点被顶点的邻接顶点被顶点的邻接顶点被顶点的邻接顶点被访问的？访问的？访问的？访问的？1 12 23 34 45 56
25、67 78 8体会队列操作方式：体会队列操作方式：体会队列操作方式：体会队列操作方式：第23页，本讲稿共50页图的遍历图的遍历 广优广优n n广度优先遍历的特点广度优先遍历的特点uu“广度广度广度广度”：总是在访问了一个顶点后，依次访问：总是在访问了一个顶点后，依次访问：总是在访问了一个顶点后，依次访问：总是在访问了一个顶点后，依次访问它的所有相邻顶点。然后再从它的第一个相邻顶它的所有相邻顶点。然后再从它的第一个相邻顶它的所有相邻顶点。然后再从它的第一个相邻顶它的所有相邻顶点。然后再从它的第一个相邻顶点开始，访问其所有的相邻顶点。如此逐个顶点点开始，访问其所有的相邻顶点。如此逐个顶点点开始，访
26、问其所有的相邻顶点。如此逐个顶点点开始，访问其所有的相邻顶点。如此逐个顶点地逐步扩散，直到所有的顶点都被访问。地逐步扩散，直到所有的顶点都被访问。地逐步扩散，直到所有的顶点都被访问。地逐步扩散，直到所有的顶点都被访问。uu广度优先遍历操作具有队列操作的特点，当从队广度优先遍历操作具有队列操作的特点，当从队广度优先遍历操作具有队列操作的特点，当从队广度优先遍历操作具有队列操作的特点，当从队列中取出最后一个顶点，发现该顶点的所有相邻列中取出最后一个顶点，发现该顶点的所有相邻列中取出最后一个顶点，发现该顶点的所有相邻列中取出最后一个顶点，发现该顶点的所有相邻顶点都被访问过时，意味着图中所有的顶点都已
27、顶点都被访问过时，意味着图中所有的顶点都已顶点都被访问过时，意味着图中所有的顶点都已顶点都被访问过时，意味着图中所有的顶点都已被访问过被访问过被访问过被访问过第24页，本讲稿共50页生成树与图生成树与图n n3.6.4 图的应用图的应用n n1.生成树定义生成树定义uu假设存在这样一颗树：假设存在这样一颗树：假设存在这样一颗树：假设存在这样一颗树：树结点的集合与图的顶点集合相等树结点的集合与图的顶点集合相等树结点的集合与图的顶点集合相等树结点的集合与图的顶点集合相等树的分支全部由图的边组成。树的分支全部由图的边组成。树的分支全部由图的边组成。树的分支全部由图的边组成。称这颗树是这幅称这颗树是这
28、幅称这颗树是这幅称这颗树是这幅图的生成树图的生成树图的生成树图的生成树uu生成树是图的生成树是图的生成树是图的生成树是图的:子集子集子集子集/子图子图子图子图是一个不包含回路的子图是一个不包含回路的子图是一个不包含回路的子图是一个不包含回路的子图图的生成树是图的生成树是图的生成树是图的生成树是2 21 14 43 32 21 14 43 32 21 14 43 32 21 14 43 3不唯一的！不唯一的！不唯一的！不唯一的！唯一的！唯一的！唯一的！唯一的！取决于遍历方法和遍历的起始点取决于遍历方法和遍历的起始点第25页，本讲稿共50页生成树的示例生成树与图生成树与图对于一个有n个顶点的连通图
29、G，其生成树包含了 条边。深度优先搜索得到的生成树广度优先搜索得到的生成树n1第26页，本讲稿共50页权值权值权值权值生成树与图生成树与图n n2.最小费用生成树（最小费用生成树（通信网络、交通网络）uu在图所有生成树中，边的权值总和最小的生成树在图所有生成树中，边的权值总和最小的生成树在图所有生成树中，边的权值总和最小的生成树在图所有生成树中，边的权值总和最小的生成树1245636536642416124563边边边边1 13 31 14 46 62 22 25 53 31 14 44 43 36 64 42 23 35 51 12 26 63 35 56 65 56 66 6将边按将边按将
30、边按将边按权值大权值大权值大权值大小排列小排列小排列小排列第27页，本讲稿共50页生成树与图生成树与图n n算法分析算法分析uu关键技术：关键技术：关键技术：关键技术：为什么在（为什么在（为什么在（为什么在（1,41,4）边选中后不能选（）边选中后不能选（）边选中后不能选（）边选中后不能选（3,63,6）边）边）边）边在选择（在选择（在选择（在选择（3,63,6）边和（）边和（）边和（）边和（2,32,3）边时有什么不同，怎样设置条件以区）边时有什么不同，怎样设置条件以区）边时有什么不同，怎样设置条件以区）边时有什么不同，怎样设置条件以区别？别？别？别？vv当时当时当时当时3 3和和和和6 6
31、位于同一图中，位于同一图中，位于同一图中，位于同一图中，2 2、5 5和和和和3 3位于不同的图中位于不同的图中位于不同的图中位于不同的图中12456365366424161245631 14 44 43 36 64 42 23 35 5回路回路回路回路第28页，本讲稿共50页生成树与图生成树与图1245631 1）开始时所有的节点都位于不同的图中）开始时所有的节点都位于不同的图中）开始时所有的节点都位于不同的图中）开始时所有的节点都位于不同的图中2 2）选择一条连接两个不同子图的最短边）选择一条连接两个不同子图的最短边）选择一条连接两个不同子图的最短边）选择一条连接两个不同子图的最短边3 3
32、）连接以后两个子图的所有顶点都要改为）连接以后两个子图的所有顶点都要改为）连接以后两个子图的所有顶点都要改为）连接以后两个子图的所有顶点都要改为 在一个子图中在一个子图中在一个子图中在一个子图中4 4）当所有的顶点都位于一个子图中，）当所有的顶点都位于一个子图中，）当所有的顶点都位于一个子图中，）当所有的顶点都位于一个子图中，算法结束。算法结束。算法结束。算法结束。权值权值权值权值边边边边1 13 31 14 46 62 22 25 53 31 14 44 43 36 64 42 23 35 51 12 26 6思考思考思考思考既然是颗树，如果选择边数为既然是颗树，如果选择边数为既然是颗树，如
33、果选择边数为既然是颗树，如果选择边数为n n1 1个时可不可以结束算法呢？个时可不可以结束算法呢？个时可不可以结束算法呢？个时可不可以结束算法呢？算法的优化算法的优化算法的优化算法的优化第29页，本讲稿共50页图的最短路径图的最短路径n n3.最短路径最短路径uu图中两个顶点之间有图中两个顶点之间有图中两个顶点之间有图中两个顶点之间有 条路径条路径条路径条路径uu最短路径：最短路径：最短路径：最短路径：是路径中边（弧）的权值总和最小的路径是路径中边（弧）的权值总和最小的路径是路径中边（弧）的权值总和最小的路径是路径中边（弧）的权值总和最小的路径uu计算机网络中常使用最短路径算法计算最佳路径计算
34、机网络中常使用最短路径算法计算最佳路径计算机网络中常使用最短路径算法计算最佳路径计算机网络中常使用最短路径算法计算最佳路径uu交通网络中使用最短路径算法计算最短旅途交通网络中使用最短路径算法计算最短旅途交通网络中使用最短路径算法计算最短旅途交通网络中使用最短路径算法计算最短旅途多多多多Dijkstra AlgorithmDijkstra AlgorithmFloyd AlgorithmFloyd Algorithm第30页，本讲稿共50页A1A2A4A3A526512151 1）初始化时，设）初始化时，设）初始化时，设）初始化时，设A1A1到其它不直连顶点距离为到其它不直连顶点距离为到其它不直
35、连顶点距离为到其它不直连顶点距离为 寻找A1到所有节点的最短路径A2A3A4A5顶点距离路径2 2）选择距离最短的路径）选择距离最短的路径）选择距离最短的路径）选择距离最短的路径3 3）观察通过新选择的路径是否能更短）观察通过新选择的路径是否能更短）观察通过新选择的路径是否能更短）观察通过新选择的路径是否能更短地到达其它顶点地到达其它顶点地到达其它顶点地到达其它顶点4 4）选择出的最短路径将不参加下一轮比较）选择出的最短路径将不参加下一轮比较）选择出的最短路径将不参加下一轮比较）选择出的最短路径将不参加下一轮比较5 5）反复）反复）反复）反复2-42-4步，直到不剩有顶点步，直到不剩有顶点步，
36、直到不剩有顶点步，直到不剩有顶点265A2A3A4A1 A2 A33更新更新A1 A2 A33A1 A2 A4 A1 A2 A5 4A1 A2 A3 A44更新更新A1 A2 A3 A44A1 A2 A3 A58A1 A2 A54A1 A2 A3 A4 A5 更新更新Dijkstra Algorithm第31页，本讲稿共50页拓拓 扑扑 排排 序序按一定顺序进行的活动，可以使用顶点表示活动、顶点之间的有向边表示活动间的先后关系的有向图来表示，这种有向图称为顶点表示活动网络(ActivityOnVertexnetwork，简称AOV网)。AOV网中的有向边表示了活动之间的制约关系。4.拓 扑 排
37、 序第32页，本讲稿共50页将AOV网中的所有顶点排列成一个线性序列vi1,vi2,vin，并且这个序列同时满足关系：若在AOV网中从顶点vi到顶点vj存在一条路径，则在线性序列中vi必在vj之前，我们就称这个线性序列为拓拓扑扑序序列列。把对AOV网构造拓扑序列的操作称为拓扑排序。拓扑排序。在实际的意义上，AOV网中存在的有向环就意味着某些活动是以自己为先决条件，这显然是荒谬的。例如对于程序的数据流图而言，AOV网中存在环就意味着程序存在一个死循环。第33页，本讲稿共50页任何一个无环的AOV网中的所有顶点都可排列在一个拓扑序列里，拓扑排序的基本操作如下：(1)从网中选择一个入度为0的顶点并且
38、输出它。(2)从网中删除此顶点及所有由它发出的边。(3)重复上述两步，直到网中再没有入度为0的顶点为止。第34页，本讲稿共50页第35页，本讲稿共50页n以上的操作会产生两种结果：n一种是网中的全部顶点都被输出，整个拓扑排序完成；n另一种是网中顶点未被全部输出，剩余的顶点的入度均不为0，则说明网中存在有向环。n用以上操得到了一种拓扑序列：nC1,C2,C3,C4,C5,C7,C9,C10,C12,C11,C6,C8。n拓扑序列可以是种多第36页，本讲稿共50页AOV网拓扑排序过程第37页，本讲稿共50页在邻接表存储结构中实现拓扑排序算法的步骤为：在邻接表存储结构中实现拓扑排序算法的步骤为：(1
39、)扫描顶点表，将入度为0的顶点入栈。(2)当栈非空时执行以下操作：将栈顶顶点vi的序号弹出，并输出之；检查vi的出边表，将每条出边表邻接点域所对应的顶点的入度域值减1，若该顶点入度为0，则将其入栈；(3)若输出的顶点数小于n，则输出“有回路”，否则拓扑排序正常结束。第38页，本讲稿共50页关关 键键 路路 径径5.关键路径AOE网络(Activity On Edge network)：有向边：表示一个子工程（活动）边上的权值：表示一个活动持续的时间顶点：表示事件，它表示了一种状态，即它的入边所表示的活动均已完成，它的出边所表示的活动可以开始。这种带权的有向网络称为AOE网络(ActivityO
40、nEdgenetwork)，即边表示活动网络。第39页，本讲稿共50页一个AOE网络的示例第40页，本讲稿共50页关键路径：从源点到汇点的具有最大路径长度的路径。关键活动：关键路径上的各个活动。明确了哪些活动是关键活动就可以设法提高关键活动的功效，以便缩短整个工期。第41页，本讲稿共50页其中E1是网络中以vj为终点的入边集合，dur()是有向边上的权值。vl(j)的计算可从汇点开始，向源点逆推计算：(13.2)其中E2是网络中以vj为起点的出边集合。(1)(2)ve(j)的计算可从源点开始利用以下的递推公式求得第42页，本讲稿共50页ve(1)=0ve(2)=maxve(1)+dur()=m
41、ax0+3=3ve(3)=maxve(1)+dur()=max0+2=2ve(4)=mawve(2)+dur(),ve(3)+dur()=max3+4,2+3=7ve(5)=maxve(4)+dur(),ve(2)+dur()=max7+4,3+8=11ve(6)=maxve(3)+dur(),ve(4)+dur()=max2+7,7+2=9ve(7)=maxve(5)+dur(),ve(6)+dur()=max11+9,9+6=20vl(7)=ve(7)=20按(1)式和(2)式，可计算出图该AOE网各个事件的最早发生时间和最迟发生时间：第43页，本讲稿共50页vl(6)=minvl(7)d
42、ur()=min206=14vl(5)=minvl(7)dur()=min209=11vl(4)=minvl(5)dur(),vl(6)dur()=min114,112=7vl(3)=minvl(4)dur(),vl(6)dur()=min73,147=4vl(2)=minvl(4)dur(),vl(5)dur()=min74,118=3vl(1)=minvl(2)dur(),vl(3)dur()=min33,42=0第44页，本讲稿共50页利用ve(i)=e(i)和l(i)=vl(k)dur()网络的关键路径第45页，本讲稿共50页关键活动算法主要由以下步骤组成：(1)对AOE网进行拓扑排序，同时按拓扑排序顺序求出各顶点事件的最早发生时间ve，若网中有回路，则算法终止，否则执行(2)。(2)按拓扑序列的逆序求出各顶点事件的最迟发生时间vl。(3)根据ve和vl的值求出ai的最早开始时间e(i)和最迟开始时间l(i)。若l(i)=e(i)，则ai为关键活动。因为计算各顶点的ve值是在拓扑排序的过程中进行的，所以可通过对拓扑排序算法进行一些修正来实现求关键路径的算法。第46页，本讲稿共50页作业作业第47页，本讲稿共50页第48页，本讲稿共50页一个网络及其邻接矩阵第49页，本讲稿共50页Kruskal算法构造最小生成树的过程第50页，本讲稿共50页