数据结构 课件 第7章 图

CONTENTS提纲1/118第7章图017.1图的定义与术语027.2图的存储结构047.4最小生成树037.3图的遍历057.5有向无环图的应用067.6最短路径图（Graph）G由顶点集合V(G)和边集合E(G)构成。7.1.1图的定义说明：对于n个顶点的图，对每个顶点连续编号，即顶点的编号为0～n-1。通过编号唯一确定一个顶点。13242/1187.1图的定义与术语图的基本运算如下：

InitGraph(&g)：图初始化。

ClaerGraph(&g)：销毁图。

DFS(G，v)：从顶点v出发深度优先遍历。

BFS(G，v)：从顶点v出发广度优先遍历。…3/118图抽象数据类型＝逻辑结构＋基本运算（运算描述）1、无向图在图G中，如果代表边的顶点对是无序的，则称G为无向图。用圆括号序偶表示无向边。1324(1，3)2、有向图如果表示边的顶点对是有序的，则称G为有向图。用尖括号序偶表示有向边。1324<3，1>无向图G1有向图G24/1187.1.2图的基本术语设有两个图G=(V，E)和G'=(V'，E')，若V'是V的子集，即V'

V，且E'是E的子集，即E'

E，则称G'是G的子图。3、子图无向图G1的子图有向图G2的子图5/118无向图：每两个顶点之间都存在着一条边，称为完全无向图，包含有n(n-1)/2条边。1324完全无向图：n=4，e=n(n-1)/2=66/1184、无向完全图有向图：每两个顶点之间都存在着方向相反的两条边，称为有向完全图，包含有n(n-1)条边。有向完全图：n=4，e=n(n-1)=1213247/1185、有向完全图当一个图接近完全图时，则称为稠密图。

相反，当一个图含有较少的边数（即当e<<n(n-1)）时，则称为稀疏图。8/1186、稠密图、稀疏图7、权和网图中每一条边都可以附带有一个对应的数值，这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。

边上带有权的图称为带权图，也称作网。带权图132482799/118无向图：若存在一条边(i，j)

顶点i和顶点j为端点，它们互为邻接点。有向图：若存在一条边<i，j>

顶点i为起始端点（简称为起点），顶点j为终止端点（简称终点），它们互为邻接点。8、邻接点10/11813024(a)13024(b)无向图：以顶点i为端点的边数称为该顶点的度。有向图：以顶点i为终点的入边的数目，称为该顶点的入度。以顶点i为始点的出边的数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。顶点1的度为3顶点0的入度为1顶点0的出度为2顶点0的度为1+2=311/1189、顶点的度、入度和出度若一个图中有n个顶点和e条边，每个顶点的度为di（0≤i≤n-1），则有：1302413024n=5，e=8d0=3，d1=3，d2=3，d3=4，d4=3(d0+d1+d2+d3+d4)/2=8n=5，e=8d0=3，d1=3，d2=3，d3=4，d4=3(d0+d1+d2+d3+d4)/2=812/11810、路径和路径长度在一个图G=(V，E)中，从顶点i到顶点j的一条路径(i，i1，i2，…，im，j)。

所有的(ix，iy)∈E(G)，或者<ix，iy>∈E(G)路径长度是指一条路径上经过的边的数目。

若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。无向图G1的顶点1到顶点4的所有路径13/11811、回路或环

若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环。14/11812、简单路径、简单回路或简单环

序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。如图所示，两个图的粗线都构成环，左侧图起点和终点都为顶点1，并且其他顶点没有重复出现，故为简单环。而右侧的环，由于有重复的顶点2，所以不是简单环。15/11813、连通、连通图和连通分量无向图：若从顶点i到顶点j有路径，则称顶点i和j是连通的。若图中任意两个顶点都连通，则称为连通图，否则称为非连通图。无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。1023一个非连通图1023一个非连通图的两个连通分量5516/11814、强连通图和强连通分量

有向图：若从顶点i到顶点j有路径，则称从顶点i到j是连通的。若图G中的任意两个顶点i和j都连通，即从顶点i到j和从顶点j到i都存在路径，则称图G是强连通图。1023一个强连通图1023一个非强连通图17/118存储每个顶点的信息存储每条边的信息图的逻辑结构图的存储结构映射图的两种主要存储结构：

邻接矩阵邻接表187.2图的存储结构邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E)是具有n（n>0）个顶点的图，顶点的编号依次为0～n-1。G的邻接矩阵A是n阶方阵，其定义如下：（1）如果G是无向图，则：

A[i][j]=1：若(i，j)∈E(G)0:其他（2）如果G是有向图，则：

A[i][j]=1：若<i，j>∈E(G)0:其他197.2.1邻接矩阵存储方法（3）如果G是带权无向图，则：

A[i][j]=wij

：若i≠j且(i，j)∈E(G)0：i=j∞：其他（4）如果G是带权有向图，则：

A[i][j]=wij

：若i≠j且<i，j>∈E(G)0：i=j∞：其他20对称不对称

1324132421邻接矩阵演示一个图的邻接矩阵表示是唯一的。特别适合于稠密图的存储。邻接矩阵的存储空间为O(n2)22邻接矩阵的主要特点：#defineMAXV<最大顶点个数> typedefstruct{intno; //顶点编号

InfoTypeinfo; //顶点其他信息}VertexType;typedefstruct //图的定义{intedges[MAXV][MAXV]; //邻接矩阵

intn，e; //顶点数，边数

VertexTypevexs[MAXV]; //存放顶点信息}MatGraph;声明顶点的类型声明的邻接矩阵类型23图的邻接矩阵存储类型定义如下：对图中每个顶点i建立一个单链表，将顶点i的所有邻接点链起来。0132123∧顶点0的单链表02∧顶点1的单链表013∧顶点2的单链表02∧顶点3的单链表247.2.2邻接表存储方法每个单链表上添加一个表头结点（表示顶点信息）。并将所有表头结点构成一个数组，下标为i的元素表示顶点i的表头结点。v00v11v22v33123∧02∧013∧02∧013225v00v11v2∧2v3∧312032356一个网132536∧22∧邻接表创建完毕26邻接表表示不唯一。特别适合于稀疏图存储。132∧v00312∧v00邻接表的存储空间为O(n+e)013227邻接表的特点如下：typedefstructANode{intadjvex; //该边的终点编号

structANode*nextarc; //指向下一条边的指针

InfoTypeweight; //该边的权值等信息}ArcNode;typedefstructVnode{Vertexdata; //顶点信息

ArcNode*firstarc; //指向第一条边}VNode;typedefstruct{VNodeadjlist[MAXV]; //邻接表

intn，e; //图中顶点数n和边数e}AdjGraph;声明边结点类型声明邻接表头结点类型声明图邻接表类型28图的邻接表存储类型定义如下：从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。图的遍历得到的顶点序列称为图遍历序列。297.3图的遍历图中顶点之间是多对多的关系，而从一个顶点出发一次只能找另外一个相邻顶点。13024例如：从顶点1出发，访问顶点1，

再访问顶点2，4，…

再访问顶点2，3，0，…不同的搜索方法初始点30深度优先遍历（DFS）。广度优先遍历（BFS）。31根据搜索方法的不同，图的遍历方法有两种：（1）从图中某个初始顶点v出发，首先访问初始顶点v。（2）选择一个与顶点v相邻且没被访问过的顶点w，再从w出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。vw…深度优先遍历过程：327.3.1深度优先遍历算法深度优先遍历的过程体现出后进先出的特点：用栈或递归方式实现。34012初始点DFS：1→4→2…用栈保存访问过的顶点栈14如何确定一个顶点是否访问过?设置一个visited[]全局数组，visited[i]=0表示顶点i没有访问；visited[i]=1表示顶点i已经访问过。ivisited[i]33算法设计思路：voidDFS(AdjGraph*G，intv){ArcNode*p;intw;visited[v]=1; //置已访问标记

printf("%d"，v); //输出被访问顶点的编号

p=G->adjlist[v].firstarc; //p指向顶点v的第一条边的边头结点

while(p!=NULL){w=p->adjvex;if(visited[w]==0)DFS(G，w); //若w顶点未访问，递归访问它

p=p->nextarc;

//p指向顶点v的下一条边的边头结点

}}该算法的时间复杂度为O(n+e)。34采用邻接表的DFS算法：32014v=4的DFS序列：41032遍历过程结束34012DFS思路：距离初始顶点越远越优先访问！35深度优先遍历过程演示（1）访问初始点v，接着访问v的所有未被访问过的邻接点v1，v2，…，vt。（2）按照v1，v2，…，vt的次序，访问每一个顶点的所有未被访问过的邻接点。（3）依次类推，直到图中所有和初始点v有路径相通的顶点都被访问过为止。广度优先遍历的过程：367.3.2广度优先遍历算法广度优先搜索遍历体现先进先出的特点，用队列实现。34012初始点BFS：1→4→3→0…用队列保存访问过的顶点队列340如何确定一个顶点是否访问过?设置一个visited[]数组，visited[i]=0表示顶点i没有访问；visited[i]=1表示顶点i已经访问过。ivisited[i]37算法设计思路：voidBFS(AdjGraph*G，intv){intw，i;ArcNode*p;SqQueue*qu; //定义环形队列指针InitQueue(qu); //初始化队列intvisited[MAXV];//定义顶点访问标记数组for(i=0;i<G->n;i++)visited[i]=0; //访问标记数组初始化printf("%2d"，v); //输出被访问顶点的编号visited[v]=1;//置已访问标记enQueue(qu，v);思考题：为什么visited数组不需要设置为全局变量？38采用邻接表的BFS算法：while(!QueueEmpty(qu)) //队不空循环{deQueue(qu，w); //出队一个顶点wp=G->adjlist[w].firstarc; //指向w的第一个邻接点while(p!=NULL) //查找w的所有邻接点{if(visited[p->adjvex]==0) //若当前邻接点未被访问{printf("%2d"，p->adjvex); //访问该邻接点visited[p->adjvex]=1; //置已访问标记enQueue(qu，p->adjvex); //该顶点进队}p=p->nextarc; //找下一个邻接点}}printf("\n");}该算法的时间复杂度为O(n+e)。39v=4的BFS序列：41320遍历过程结束3201434012BFS思路：距离初始顶点越近越优先访问！40广度优先遍历过程演示一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点和构成一棵树的(n-1)条边。7.4.1生成树的概念命题：如果在一棵生成树上添加一条边，必定构成一个环。012345012345一棵生成树417.4最小生成树由深度优先遍历得到的生成树称为深度优先生成树。012345012345DFS生成树42可以通过遍历方法产生生成树：由广度优先遍历得到的生成树称为广度优先生成树。012345BFS生成树012345一个连通图的生成树不一定是唯一的！43对于带权连通图G（每条边上的权均为大于零的实数），可能有多棵不同生成树。每棵生成树的所有边的权值之和可能不同。其中权值之和最小的生成树称为图的最小生成树。44最小生成树的概念连通图：仅需调用遍历过程（DFS或BFS）一次，从图中任一顶点出发，便可以遍历图中的各个顶点，产生相应的生成树。非连通图：需多次调用遍历过程。每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树。所有连通分量的生成树组成非连通图的生成森林。重点：求带权连通图的最小生成树45非连通图和生成树普里姆（Prim）算法是一种构造性算法，用于构造最小生成树。过程如下：

（1）初始化U={v}。v到其他顶点的所有边为候选边；（2）重复以下步骤n-1次，使得其他n-1个顶点被加入到U中：

从候选边中挑选权值最小的边输出，设该边在V-U中的顶点是k，将k加入U中；

考察当前V-U中的所有顶点j，修改候选边：若(j，k)的权值小于原来和顶点k关联的候选边，则用(k，j)取代后者作为候选边。vkUV－UkjUV－Uv最小边小的边作为候选边467.4.2普里姆算法普里姆算法求解最小生成树的过程图G0164352U={0}0016435229111715262519231347Prim算法示例演示（起点0）普里姆算法求解最小生成树的过程图G0154352U={0，6}06016435229111715262519231348Prim算法示例演示（起点0）普里姆算法求解最小生成树的过程0164352291117152625192313图G0154352U={0，6，4}06449Prim算法示例演示（起点0）普里姆算法求解最小生成树的过程图G0154352U={0，6，4，3}0643016435229111715262519231350Prim算法示例演示（起点0）普里姆算法求解最小生成树的过程图G0154352U={0，6，4，3，2}06432016435229111715262519231351Prim算法示例演示（起点0）普里姆算法求解最小生成树的过程图G0154352U={0，5，4，3，2，1}064321最小生成树U={0，6，4，3，2，1，5}016435229111715262519231352Prim算法示例演示（起点0）jUV－Uvlowcost[j]closest[j](j，closest[j])是顶点j的最小边，权值为lowcost[j]k如何存储顶点j到U顶点集的最小边？顶点j到U的最小边一个顶点属于哪个集合？lowcost[k]=0lowcost[j]!=0图采用哪种存储结构更合适？邻接矩阵如何求U、V-U两个顶点集之间的最小边？（只求一条）只考虑V-U中顶点j到U顶点集的最小边（无向图），比较来找最小边53算法设计（解决4个问题）：#defineINF32767 //INF表示∞voidPrim(MatGraphg，intv){intlowcost[MAXV];intmin;intclosest[MAXV]，i，j，k;for(i=0;i<g.n;i++) //给lowcost[]和closest[]置初值

{ lowcost[i]=g.edges[v][i]; closest[i]=v;}普里姆（Prim）算法如下：iUV－Uvlowcost[i]closest[i]U中只有一个顶点v顶点i到U的最小边：(v，g.edges[v][i])54for(i=1;i<g.n;i++) //输出(n-1)条边

{min=INF;for(j=0;j<g.n;j++) //在(V-U)中找出离U最近的顶点k if(lowcost[j]!=0&&lowcost[j]<min) {min=lowcost[j]; k=j; //k记录最近顶点编号

}printf("边(%d，%d)权为:%d\n"，closest[k]，k，min);lowcost[k]=0; //标记k已经加入UkUV－Uxlowcost[k]closest[k]=xkUV－Ux输出：(closest[k]，k)55for(j=0;j<g.n;j++)//修改数组lowcost和closestif(lowcost[j]!=0&&g.edges[k][j]<lowcost[j]){lowcost[j]=g.edges[k][j];closest[j]=k;}}}修改U和V-U之间的候选边，即调整仅仅考虑V-U中的顶点xUV－Ukjlowcost[j]g.edges[k][j]U中除了k外的全部顶点本次加入顶点k56局部最优+调整＝全局最优贪心算法思想最优结果Prim()算法中有两重for循环，所以时间复杂度为O(n2)。普里姆算法分析57普里姆算法思路按权值的递增次序选择合适的边来构造最小生成树的方法。克鲁斯卡尔（Kruskal）算法也是一种求带权无向图的最小生成树的构造性算法。587.4.3克鲁斯卡尔算法

（1）置U的初值等于V（即包含有G中的全部顶点），TE的初值为空集（即图T中每一个顶点都构成一个连通分量）。（2）将图G中的边按权值从小到大的顺序依次选取：

若选取的边未使生成树T形成回路，则加入TE；

否则舍弃，直到TE中包含(n-1)条边为止。表示最小生成树的边集01643522810142518220164352有条件地加入(n-1)条边TE={}161259克鲁斯卡尔（Kruskal）算法过程：克鲁斯卡尔算法求解最小生成树的过程0154362123867954按边大小递增排序016435228101425182260Kruskal算法示例的演示克鲁斯卡尔算法求解最小生成树的过程取1号边01643521238679540164352取2号边取3号边取4号边取5号边取6号边取7号边取8号边操作选取了n-1条边最小生成树61Kruskal算法示例的演示算法设计（解决3个问题）：如何解决加入一条边后是否出现回路？图采用哪种存储结构更合适？边的排序问题？邻接矩阵这里采用直接插入排序算法采用连通分量编号或顶点集合编号62在实现克鲁斯卡尔算法Kruskal()时，用数组E存放图G中的所有边，其类型如下：typedefstruct{intu; //边的起始顶点

intv;//边的终止顶点

intw; //边的权值}Edge;EdgeE[MAXV];63voidKruskal(MatGraphg){inti，j，u1，v1，sn1，sn2，k;intvset[MAXV];EdgeE[MaxSize]; //存放所有边

k=0; //E数组的下标从0开始计

for(i=0;i<g.n;i++) //由g产生的边集Efor(j=0;j<g.n;j++)if(g.edges[i][j]!=0&&g.edges[i][j]!=INF) {E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j]; k++; }InsertSort(E，g.e); //用直接插入排序对E数组按权值递增排序

for(i=0;i<g.n;i++) //初始化辅助数组

vset[i]=i;k=1; //k表示当前构造生成树的第几条边j=0; //E中边的下标，初值为0while(k<g.n) //生成的边数小于n时循环{u1=E[j].u;v1=E[j].v; //取一条边的头尾顶点sn1=vset[u1];sn2=vset[v1]; //分别得到两个顶点所属的集合编号

if(sn1!=sn2) //两顶点属于不同的集合

{printf("(%d，%d):%d\n"，u1，v1，E[j].w);k++; //生成边数增1for(i=0;i<g.n;i++) //两个集合统一编号

if(vset[i]==sn2) //集合编号为sn2的改为sn1 vset[i]=sn1}j++; //扫描下一条边

}}64克鲁斯卡尔（Kruskal）算法如下：Kruskal算法的时间复杂度为O(elog2e)。上述算法不是最优的。改进：堆排序、并查集65voidKruskal(MatGraphg) //改进的Kruskal算法{inti,j,k,u1,v1,sn1,sn2;UFSTreet[MaxSize];EdgeE[MaxSize];k=1; //e数组的下标从1开始计for(i=0;i<g.n;i++) //由g产生的边集Efor(j=0;j<=i;j++) if(g.edges[i][j]!=0&&g.edges[i][j]!=INF){E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j];k++;}HeapSort(E,g.e); //采用堆排序对E数组按权值递增排序66MAKE_SET(t,g.n); //初始化并查集树tk=1; //k表示当前构造生成树的第几条边,初值为1j=1; //E中边的下标从1开始while(k<g.n) //生成的边数小于n时循环{u1=E[j].u;v1=E[j].v; //取一条边的头尾顶点编号u1和v2sn1=FIND_SET(t,u1);sn2=FIND_SET(t,v1); //分别得到两个顶点所属的集合编号if(sn1!=sn2) //两顶点属不同的集合,是最小生成树的边{printf("(%d,%d):%d\n",u1,v1,E[j].w);k++; //生成边数增1UNION(t,u1,v1); //将u1和v1两个顶点合并}j++; //扫描下一条边}}67

求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（kruskal）算法第二次选中但不是普里姆（Prim）算法（从v4

开始）第2次选中的边是（）。A.(v1，v3)B.(v1，v4)C.(v2，v3)D.(v3，v4)v1v2v3v410811858Prim（从v4

开始）：1：(v1，v4)，2：(v1，v3)或(v3，v4)，

不可能是(v2，v3)kruskal：1：(v1，v4)，2：(v1，v3)或(v3，v4)

或(v2，v3)，

注：2015年全国考研题答案为C示例681、什么是拓扑排序设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列v1，v2，…，vn称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若<i，j>是图中的边（或从顶点i

j有一条路径）:7.5.1拓扑排序在一个有向图中找一个拓扑序列的过程称为拓扑排序。则在拓扑序列中顶点i必须排在顶点j之前。ijij697.5有向无环图的应用

（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它。（2）从图中删去该顶点，并且删去从该顶点发出的全部有向边。（3）重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。702、拓扑排序步骤typedefstruct //表头结点类型{Vertexdata;//顶点信息

intcount;//存放顶点入度

ArcNode*firstarc;//指向第一条边}VNode;将邻接表定义中的VNode类型修改如下：用于找入度为0的顶点713、拓扑排序算法设计voidTopSort(AdjGraph*G) //拓扑排序算法{inti，j;intSt[MAXV]，top=-1; //栈St的指针为topArcNode*p;for(i=0;i<G->n;i++) //入度置初值0G->adjlist[i].count=0;for(i=0;i<G->n;i++) //求所有顶点的入度{p=G->adjlist[i].firstarc;while(p!=NULL){G->adjlist[p->adjvex].count++; p=p->nextarc;}}拓扑排序算法如下：修改后的含n个顶点的邻接表72for(i=0;i<G->n;i++) //将入度为0的顶点进栈if(G->adjlist[i].count==0){top++;St[top]=i;}while(top>-1) //栈不空循环{i=St[top];top--; //出栈一个顶点iprintf("%d",i); //输出该顶点p=G->adjlist[i].firstarc; //找第一个邻接点while(p!=NULL) //将顶点i的出边邻接点的入度减1{j=p->adjvex; G->adjlist[j].count--; if(G->adjlist[j].count==0) //将入度为0的邻接点进栈 {top++;St[top]=j; } p=p->nextarc; //找下一个邻接点}}}73

对如图所示的图进行拓扑排序，可以得到不同的拓扑序列为（）。解：不同的拓扑序列有：aebcdf、abcedf、abecdf。eabcdf示例74用一个带权有向图（DAG）描述工程的预计进度。顶点表示事件，有向边表示活动，边e的权c(e)表示完成活动e所需的时间（比如天数）。图中入度为0的顶点表示工程的开始事件（如开工仪式），出度为0的顶点表示工程结束事件。1、AOE网AOE网（ActivityOnEdge）757.5.2关键路径从AOE网中源点到汇点的最长路径，具有最大长度的路径叫关键路径。关键路径是由关键活动构成的，关键路径可能不唯一。762、关键路径求解过程7abcdefghk6452118244源点汇点一条关键路径77关键路径演示关键路径为源点到汇点的最长路径，这样转变为查找图中最长路径问题。求解过程可以通过修改Dijkstra算法来实现吗？（不能！）求一个AOE的关键路径求AOE的中的关键活动这里的给出的求解方法：78

（1）事件的最早开始和最迟开始时间

事件v的最早开始时间：规定源点事件的最早开始时间为0。定义图中任一事件v的最早开始时间（earlyevent）ee(v)等于x、y、z到v所有路径长度的最大值：ee(v)=0

当v为源点时ee(v)=MAX{ee(x)+a，ee(y)+b，ee(z)+c} 否则从左向右推进计算这是为什么源点要唯一！xyzvabcee(v)=?ee(x)ee(y)ee(z)793、求关键路径的过程事件v的最迟开始时间：定义在不影响整个工程进度的前提下，事件v必须发生的时间称为v的最迟开始时间（lateevent），记作le(v)。le(v)应等于ee(y)与v到汇点的最长路径长度之差：le(v)=ee(v) 当v为汇点时le(v)=MIN{le(x)-a，le(y)-b，le(z)-c} 否则vxyzabcle(v)=?le(x)le(y)le(z)从右向左推进计算这是为什么汇点要唯一！80

活动a的最早开始时间e(a)指该活动起点x事件的最早开始时间，即：

e(a)=ee(x)xy活动a时间为cee(x)le(y)

活动a的最迟开始时间l(a)指该活动终点y事件的最迟开始时间与该活动所需时间之差，即：

l(a)=le(y)-c81（2）活动的最早开始时间和最迟开始时间

（3）求关键活动

对于每个活动a，求出d(a)=l(a)-e(a)，若d(a)为0，则称活动a为关键活动。对关键活动来说，不存在富余时间。82先进行拓扑排序，假设拓扑序列为：ABCDEFGHI计算各事件的ee(v)如下：ee(A)=0ee(B)=ee(A)+c(a1)=6ee(C)=ee(A)+c(a2)=4ee(D)=ee(A)+c(a3)=3ee(E)=MAX(ee(B)+c(a4)，ee(C)+c(a5)}=MAX{7，5}=7示例ABCDa4=1a1=6a2=4a3=3EHIFGa6=3a5=1a7=9a8=7a10=2a11=3a9=383ee(F)=ee(E)+c(a7)=16ee(G)=ee(E)+c(a8)=14ee(H)=ee(D)+c(a6)=6ee(I)=MAX{ee(F)+c(a10)，ee(G)+c(a11)，ee(H)+c(a9)}=MAX(18，17，9}=18ABCDa4=1a1=6a2=4a3=3EHIFGa6=3a5=1a7=9a8=7a10=2a11=3a9=384le(I)=ee(I)=18le(H)=le(I)-c(a9)=15le(G)=le(I)-c(a11)=15le(F)=le(I)-c(a10)=16拓扑序列为ABCDEFGHI，按拓扑逆序IHGFEDCBA计算各事件的le(v)如下：ABCDa4=1a1=6a2=4a3=3EHIFGa6=3a5=1a7=9a8=7a10=2a11=3a9=385le(E)=MIN(le(F)-c(a7)，le(G)-c(a8)}={7，8}=7le(D)=le(H)-c(a6)=12le(C)=le(E)-c(a5)=6le(B)=le(E)-c(a4)=6le(A)=MIN(le(B)-c(a1)，le(C)-c(a2)，le(D)-c(a3)}={0，2，9}=0ABCDa4=1a1=6a2=4a3=3EHIFGa6=3a5=1a7=9a8=7a10=2a11=3a9=386计算各活动的e(a)、l(a)和d(a)如下：活动a1：e(a1)=ee(A)=0，l(a1)=le(B)-6=0，d(a1)=0活动a2：e(a2)=ee(A)=0，l(a2)=le(C)-4=2，d(a2)=2活动a3：e(a3)=ee(A)=0，l(a3)=le(D)-5=9，d(a3)=9活动a4：e(a4)=ee(B)=6，l(a4)=le(E)-1=6，d(a4)=0活动a5：e(a5)=ee(C)=4，l(a5)=le(E)-1=6，d(a5)=2ABCDa4=1a1=6a2=4a3=3EHIFGa6=3a5=1a7=9a8=7a10=2a11=3a9=387活动a6：e(a6)=ee(D)=5， l(a6)=le(H)-2=12， d(a6)=7活动a7：e(a7)=ee(E)=7， l(a7)=le(F)-9=7， d(a7)=0活动a8：e(a8)=ee(E)=7， l(a8)=le(G)-7=8， d(a8)=1活动a9：e(a9)=ee(H)=7， l(a9)=le(G)-4=15， d(a9)=8活动a10：e(a10)=ee(F)=16， l(a10)=le(I)-2=16， d(a10)=0活动a11：e(a11)=ee(G)=14， l(a11)=le(I)-4=15， d(a11)=1ABCDa4=1a1=6a2=4a3=3EHIFGa6=3a5=1a7=9a8=7a10=2a11=3a9=388

由此可知，关键活动有a10、a7、a4、a1，因此关键路径有两条：A－B－E－F－I。ABCDa4=1a1=6a2=4a3=3EHIFGa6=3a5=1a7=9a8=7a10=2a11=3a9=389

考虑带权有向图，把一条路径（仅仅考虑简单路径）上所经边的权值之和定义为该路径的路径长度或称带权路径长度。路径的概念从源点到终点可能不止一条路径，把路径长度最短的那条路径称为最短路径。vv1v2uc1c2c3

cm路径长度=c1+c2+…+cm路径：（v，v1，v2，…，u）7.6最短路径问题描述：给定一个带权有向图G与源点v，求从v到G中其他顶点的最短路径，并限定各边上的权值大于或等于0。单源最短路径问题：Dijkstra算法7.6.1单源最短路径问题：Dijkstra算法设G=(V，E)是一个带权有向图，把图中顶点集合V分成两组：SvU=V-Su第1组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径v，…，u，就将u加入到集合S中，直到全部顶点都加入到S中，算法就结束了）。第2组为其余未求出最短路径的顶点集合（用U表示）。每一步求出v到U中一个顶点u的最短路径，并将u移动到S中。直到U为空。狄克斯特拉（Dijkstra）求解思路

（1）初始化：S只包含源点即S={v}，v的最短路径为0。U包含除v外的其他顶点，U中顶点i距离为边上的权值（若v与i有边<v，i>）或∞（若i不是v的出边邻接点）。SvU=V-Siv与U中顶点i的边狄克斯特拉算法的过程

（2）从U中选取一个距离v最小的顶点u，把u加入S中（该选定的距离就是v

u的最短路径长度）。SvU=V-Suv与U中顶点u的边最小

（3）以u为新考虑的中间点，修改U中各顶点j的最短路径长度：若从源点v

j（j∈U）的最短路径长度（经过顶点u）比原来最短路径长度（不经过顶点u）短，则修改顶点j的最短路径长度。SvU=V-Suj两条路径进行比较：若经过u的最短路径长度更短，则修正顶点v

j的最短路径长度＝MIN(cvk+wkj，cvj)SvU=V-Sujuvj...cvu……cvj边wujv

j的路径：不经过顶点u经过顶点u修改方式vj考虑中间其他所有顶点k，通过比较得到v

j的最短路径k（4）重复步骤（2）和（3）直到所有顶点都包含在S中。如何存放最短路径长度：用一维数组dist[j]存储！源点v默认，dist[j]表示源点顶点j的最短路径长度。如dist[2]=12表示源点顶点2的最短路径长度为12。如何存放最短路径：从源点到其他顶点的最短路径有n-1条，一条最短路径用一个一维数组表示，如从顶点0

5的最短路径为0、2、3、5，表示为path[5]={0,2,3,5}。所有n-1条最短路径可以用二维数组path[][]存储。？算法设计（解决2个问题）若从源点v

j的最短路径如下：则一定是从源点v

u的最短路径？vuj…a…avu……vuj…a…b反证法证明：而通过b的路径更短，则v→…a→…u→j不是最短路径是v

u的最短路径与假设矛盾，问题得到证明。v

j最短路径中j的前一个顶点99改进的方法是采用一维数组path来保存：从path[j]推出的逆路径：j，w，u，v对应的最短路径为：v→u→w→jvwjpath[j]=wupath[w]=upath[u]=vvj的最短路径:0132454761576241S U dist[]path[]012345012345{0}{1,2,3,4,5}{0,4,6,7,∞,∞}{0,0,0,0,-1,-1}{0,1}{2,3,4,5}{0,4,5,7,11,∞}{0,0,1,0,1,-1}最小的顶点：1最小的顶点：2{0,1,2}{3,4,5}{0,4,5,7,11,9}{0,0,1,0,1,2}最小的顶点：3{0,1,2,3}{4,5}{0,4,5,7,11,9}{0,0,1,0,1,2}最小的顶点：5{0,1,2,3,5}{4}{0,4,5,7,10,9}{0,0,1,0,5,2}{0,1,2,3,5,4}{}{0,4,5,7,10,9}{0,0,1,0,5,2}最小的顶点：40132454761576241101Dijkstra算法示例演示voidDijkstra(MatGraphg，intv){intdist[MAXV]，path[MAXV];ints[MAXV];intmindis,i,j,u;for(i=0;i<g.n;i++){dist[i]=g.edges[v][i]; //距离初始化

s[i]=0; //s[]置空

if(g.edges[v][i]<INF)//路径初始化

path[i]=v; //顶点v到i有边时 else path[i]=-1; //顶点v到i没边时}s[v]=1; //源点v放入S中dist和path数组初始化狄克斯特拉算法如下（v为源点编号）：for(i=0;i<g.n;i++) //循环n-1次

{mindis=INF;

for(j=0;j<g.n;j++) if(s[j]==0&&dist[j]<mindis) {u=j; mindis=dist[j]; }s[u]=1; //顶点u加入S中for(j=0;j<g.n;j++) //修改不在s中的顶点的距离if(s[j]==0) if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j]){dist[j]=dist[u]+g.edges[u][j]; path[j]=u; }}Dispath(dist,path,s,g.n,v); //输出最短路径}狄克斯特拉算法的时间复杂度为O(n2)。找最小路径长度顶点u调整这里以源点0=>4的最短路径进行说明，dist[4]=10，即该最短路径长度为10。由顶点和path的对应关系知：顶点0,1,2,3,4,5path={0,0,1,0,5,2}path[4]=5,path[5]=2,path[2]=1,path[1]=0到源点，反推出最短路径为0→1→2→5→4。最短路径如图所示。顶点0到4的最短路径图利用dist和path求最短路径长度和最短路径问题描述：对于一个各边权值均大于零的有向图，对每一对顶点i≠j，求出顶点i与顶点j之间的最短路径和最短路径长度。1936~2001多源最短路径问题：Floyd算法1057.6.2多源最短路径问题：Floyd算法

假设有向图G=(V，E)采用邻接矩阵存储。设置一个二维数组A用于存放当前顶点之间的最短路径长度，分量A[i][j]表示当前顶点i

j的最短路径长度。递推产生一个矩阵序列：A0

A1

…

Ak

…

An-1。算法：迭代（递推）思路Ak[i][j]：i

j的路径上所经过的顶点编号不大于k的最短路径长度。ij0～k的顶点106Ak[i,j]=MIN{Ak-1[i,j]，Ak-1[i,k]+Ak-1[k,j]}kij…Ak-1[i,k]…Ak-1[k,j]……Ak-1[i,j]

初始时，有A-1[i][j]=g.edges[i][j]。

考虑从i

j的最短路径经过编号为k顶点的情况：A-1[i][j]=g.edges[i][j]Ak[i,j]=MIN{Ak-1[i,j]，Ak-1[i,k]+Ak-1[k,j]}0≤k≤n-1107（1）用二维数组A存储最短路径长度：Ak[i][j]表示考虑顶点0~k后得出的i

j的最短路径长度。An-1[i][j]表示最终的i

j的最短路径长度。（2）用二维数组path存放最短路径：pathk[i][j]表示考虑顶点0~k后得出的i

j的最短路径。pathn-1[i][j]表示最终i

j的最短路径。108算法设计（解决2个问题）kij…………ab若经过顶点k的路径更短：

pathk[i][j]=a=pathk-1[k][j]否则：

pathk[i][j]=b=pathk-1[i][j]不改变path