(9.1)--数据结构第7章图.pdf

第第7章章 图图图图也是一类重要的也是一类重要的非线性非线性结构结构实例实例火车联票，交通网，火车联票，交通网，社交网社交网特点特点多个前驱多个后继多个前驱多个后继提提 纲纲 图的定义和术语图的定义和术语 图的存储结构图的存储结构-数组表示法数组表示法 图的存储结构图的存储结构-邻接表邻接表 图的遍历图的遍历-深度优先搜索深度优先搜索 图的遍历图的遍历-广度优先搜索广度优先搜索 最小生成树最小生成树 有向无环图有向无环图-拓扑排序拓扑排序 有向无环图有向无环图-关键路径关键路径 单源最短路径单源最短路径-迪杰斯特拉算法迪杰斯特拉算法 每一对顶点之间的最短路径每一对顶点之间的最短路径-弗洛伊德算法弗洛伊德算法图的定义和术语图的定义和术语图的抽象数据类型定义图的抽象数据类型定义ADT Graph数据对象数据对象V：V是具有相同特性的数据元素的集合是具有相同特性的数据元素的集合,称为称为顶点集顶点集。数据关系数据关系R：R=VRVR=|v,wV且且P(v,w)，表示从表示从v到到w的的弧弧，谓词谓词P(v,w)定义定义了弧了弧的意义和信息的意义和信息基本操作：基本操作：FirstAdjVex(G,v);NextAdjVex(G,v,w);DFSTraverse(G,v,Visit();BFSTraverse(G,v,Visit();ADT Graph;顶点顶点：图中数据元素称为顶点：图中数据元素称为顶点，V是顶点的有穷非空集合是顶点的有穷非空集合。顶点关系顶点关系的集合：的集合：VR例：例：有 向 图有 向 图：若：若 VR，则则表示从表示从v到到w的一条弧的一条弧，且且称称v为弧尾为弧尾，称称w为弧头为弧头，此时的此时的图称为有向图图称为有向图。无向图无向图：若若VR时必有时必有VR，则以则以无序对无序对（v,w）代替这两个有序对代替这两个有序对，表示表示v和和w之间的之间的一条边一条边，此时的图称为此时的图称为无向图无向图。G1=(V1,A1)其中：其中：V1=v1,v2,v3,v4A1=,G2=(V2,E2)其中：其中：V2=v1,v2,v3,v4,v5E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)设设n为图中为图中顶点数顶点数，e为边或弧的为边或弧的数目数目：无向完全图无向完全图：e的范围从的范围从0到到n(n-1)/2，有有n(n-1)/2条边的无向图称为无向完全图条边的无向图称为无向完全图。考虑考虑v1，一端在一端在v1的边有的边有n-1条条(n-1)+(n-2)+.+1=n(n-1)/2有向完全图有向完全图：e的范围从的范围从0到到n(n-1)，有有n(n-1)条弧的有向图条弧的有向图称为有向完全图称为有向完全图。网：网：若图中的边或弧带若图中的边或弧带有数值有数值，所带数值称为所带数值称为权权，图相应称为图相应称为无向网无向网或有向网或有向网。稀疏图和稠密图稀疏图和稠密图：有很少边或弧：有很少边或弧(如如enlogn)的图称为稀疏的图称为稀疏图；反之称为稠密图图；反之称为稠密图。子图子图：假设有两个图：假设有两个图G=(V,E)和和G=(V,E)，如果，如果V V且且E E，则称，则称G为为G的子图。的子图。例：例：提提 纲纲 图的定义和术语图的定义和术语 图的存储结构图的存储结构-数组表示法数组表示法 图的存储结构图的存储结构-邻接表邻接表 图的遍历图的遍历-深度优先搜索深度优先搜索 图的遍历图的遍历-广度优先搜索广度优先搜索 最小生成树最小生成树 有向无环图有向无环图-拓扑排序拓扑排序 有向无环图有向无环图-关键路径关键路径 单源最短路径单源最短路径-迪杰斯特拉算法迪杰斯特拉算法 每一对顶点之间的最短路径每一对顶点之间的最短路径-弗洛伊德算法弗洛伊德算法邻接点邻接点无向图中无向图中，如果边如果边(v,v)E，则称顶点则称顶点v和和 v互为邻接点互为邻接点，边边(v,v)依附于顶点依附于顶点v和和 v。顶点顶点v的度是和的度是和v相关联的边的相关联的边的数目数目，记为记为TD(V)。niviTDe1)(21有向图中有向图中，如果弧如果弧A，则称顶点则称顶点v 邻接到顶点邻接到顶点v，顶点顶点v称为顶点称为顶点v的邻接点的邻接点。弧弧和顶点和顶点v，v相关联相关联。以顶点以顶点v为头的弧的数目称为为头的弧的数目称为v的的入度入度，记为记为ID(V);以顶点以顶点v为为尾的弧的数目称为尾的弧的数目称为v的的出度出度，记为记为OD(V);顶点顶点v的度的度TD(V)=ID(V)+OD(V)。路径路径无 向 图 中 从无 向 图 中 从顶 点顶 点 v到顶点到顶点 v的路径是一 个顶点序列的路径是一 个顶点序列（v=vi,0,vi,1,.vi,m=v)，其中其中（vi,j-1,vi,j)E,1=j=m。若是有向图若是有向图,则则路径也是有向的路径也是有向的，顶点序列满足顶点序列满足 A,1=j=m。回路回路（环环）：第一个顶点和最后一个顶点相同的路径称为回第一个顶点和最后一个顶点相同的路径称为回路或环路或环。路径长度路径长度：是路径上边或弧的数目：是路径上边或弧的数目。简单路径：简单路径：序列中顶点不重复的路径称为简单路径序列中顶点不重复的路径称为简单路径。连通图连通图（无向图无向图）无向图无向图G中中，如果从顶点如果从顶点v到顶点到顶点v有路径有路径，则称则称v和和 v是是连通连通的的。如果对于图中如果对于图中任意两个顶点任意两个顶点v,vV，v和和 v都是连通的都是连通的，则称则称G是连通图是连通图。无向图中的无向图中的极大连通子图极大连通子图称为连通分量称为连通分量。强连通图强连通图有向图有向图G中中，如果对于如果对于每一对每一对v,vV，vv，从从v到到 v和从和从v到到 v都存在路径都存在路径，则称则称G是强连通图是强连通图。有向图中的极大强连通有向图中的极大强连通子图称为强连通分量子图称为强连通分量。生成树生成树一个一个连通图连通图的生成树是一个的生成树是一个极小连通子图极小连通子图，它含有图中它含有图中的所有顶点的所有顶点，但只有足以构成一棵树的但只有足以构成一棵树的n-1条边条边。有向树有向树如果一个有向图恰有一个顶点的入度为如果一个有向图恰有一个顶点的入度为0，其余顶点的入度其余顶点的入度均为均为1，则是一棵有向树则是一棵有向树。一个有向图的一个有向图的生成森林生成森林由若干棵有向树组成由若干棵有向树组成，含有图中全部含有图中全部顶点顶点，但只有足以构成若干棵互不相交的有向树的弧但只有足以构成若干棵互不相交的有向树的弧。提提 纲纲 图的定义和术语图的定义和术语 图的存储结构图的存储结构-数组表示法数组表示法 图的存储结构图的存储结构-邻接表邻接表 图的遍历图的遍历-深度优先搜索深度优先搜索 图的遍历图的遍历-广度优先搜索广度优先搜索 最小生成树最小生成树 有向无环图有向无环图-拓扑排序拓扑排序 有向无环图有向无环图-关键路径关键路径 单源最短路径单源最短路径-迪杰斯特拉算法迪杰斯特拉算法 每一对顶点之间的最短路径每一对顶点之间的最短路径-弗洛伊德算法弗洛伊德算法图的存储结构图的存储结构问题：问题：图的任意结点之间都可能有关系图的任意结点之间都可能有关系，多个前驱多个后继多个前驱多个后继顺序映象：顺序映象：不可能不可能！非顺序映象：可行的非顺序映象：可行的，但可能造成空间浪费但可能造成空间浪费。数组表示法数组表示法（有向图有向图，无向图无向图）用用两个数组两个数组分别存储数据元素分别存储数据元素（顶点顶点）信息和关系信息和关系（边或弧边或弧）信息信息。例：例：G1示例示例无向图无向图#define INFINITYINT_MAX#define MAX_V_NUM 20typedef enum DG,DN,UDG,UDN GrahpKind;typedef structVertexType vexsMAX_V_NUM;AdjMatrix arcs;int vexnum,arcnum;GraphKind kind;MGraph;提提 纲纲 图的定义和术语图的定义和术语 图的存储结构图的存储结构-数组表示法数组表示法 图的存储结构图的存储结构-邻接表邻接表 图的遍历图的遍历-深度优先搜索深度优先搜索 图的遍历图的遍历-广度优先搜索广度优先搜索 最小生成树最小生成树 有向无环图有向无环图-拓扑排序拓扑排序 有向无环图有向无环图-关键路径关键路径 单源最短路径单源最短路径-迪杰斯特拉算法迪杰斯特拉算法 每一对顶点之间的最短路径每一对顶点之间的最短路径-弗洛伊德算法弗洛伊德算法相关问题相关问题求顶点的度求顶点的度例：例：有向图有向图G1，求顶点，求顶点v1的度的度MGraph G1（有向图）；（有向图）；int ID=0,OD=0,TD;k=locate(v);for(i=0;iG1.vexnum;i+)OD=OD+G1.arcski.adj;for(i=0;iG1.vexnum;i+)ID=ID+G1.arcsik.adj;TD=ID+OD;邻接点邻接点例：例：无向图，求第一个邻接点和下一个邻接点无向图，求第一个邻接点和下一个邻接点MGraph G2（无向图）；（无向图）；int FirstAdjVex(MGraph G,int v)成功，返回邻接点位置，失败，返回成功，返回邻接点位置，失败，返回-1int i;for(i=0;iG1.vexnum;i+)if(G.arcsvi.adj)return(i);return(-1);邻接点邻接点int NextAdjVex(Mgraph G,int v,int w)成功，返回邻接点位置，失败，成功，返回邻接点位置，失败，返回返回-1int i;for(i=w+1;inext;求入度求入度for(i=0;iadjvex=k)ID+;break;else p=p-next;总度数：总度数：TD=ID+OD;思考：思考：FirstAdjVex(G,v)?NextAdjVex(G,v,w)?逆邻居表逆邻居表提提 纲纲 图的定义和术语图的定义和术语 图的存储结构图的存储结构-数组表示法数组表示法 图的存储结构图的存储结构-邻接表邻接表 图的遍历图的遍历-深度优先搜索深度优先搜索 图的遍历图的遍历-广度优先搜索广度优先搜索 最小生成树最小生成树 有向无环图有向无环图-拓扑排序拓扑排序 有向无环图有向无环图-关键路径关键路径 单源最短路径单源最短路径-迪杰斯特拉算法迪杰斯特拉算法 每一对顶点之间的最短路径每一对顶点之间的最短路径-弗洛伊德算法弗洛伊德算法图的遍历图的遍历图的编历图的编历从图中某个顶点出发从图中某个顶点出发，访遍图中其余顶点访遍图中其余顶点，且使每一个顶且使每一个顶点仅被访问一次点仅被访问一次。对图的遍历而言对图的遍历而言，除了要确定一条搜索路径之外除了要确定一条搜索路径之外，还要解还要解决决两个问题两个问题：(1 1)如何确保每个顶点都被访问到；如何确保每个顶点都被访问到；(2 2)如何确保每个顶点只被访问一次如何确保每个顶点只被访问一次。注注：图的遍历算法是求解图的连通性问题：图的遍历算法是求解图的连通性问题、拓扑排序和求拓扑排序和求关键路径等算法的基础关键路径等算法的基础。求顶点的所有邻接点求顶点的所有邻接点设已基于存储结构实现设已基于存储结构实现int FirstAdjVex(MGraph G,int v)；int NextAdjVex(MGraphG,int v,int w)；for(w=FirstAdjvex(G,v);w=0;w=NextAdjVex(G,v,w)对邻接点对邻接点w的处理的处理G4深度优先遍历算法深度优先遍历算法Boolean visitedMAX;Status(*VisitFunc)(int v);void DFS(Graph G,int v)visitedv=TRUE;VisitFunc(v);for(w=FirstAdjvex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);void DFSTraverse(Graph G,Status(*Visit)(int v)VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;for(v=0;vG.vexnum;+v)/处理从一个顶点出发处理从一个顶点出发，不能遍历不能遍历所有顶点的问题所有顶点的问题if(!visitedv)DFS(G,v);提提 纲纲 图的定义和术语图的定义和术语 图的存储结构图的存储结构-数组表示法数组表示法 图的存储结构图的存储结构-邻接表邻接表 图的遍历图的遍历-深度优先搜索深度优先搜索 图的遍历图的遍历-广度优先搜索广度优先搜索 最小生成树最小生成树 有向无环图有向无环图-拓扑排序拓扑排序 有向无环图有向无环图-关键路径关键路径 单源最短路径单源最短路径-迪杰斯特拉算法迪杰斯特拉算法 每一对顶点之间的最短路径每一对顶点之间的最短路径-弗洛伊德算法弗洛伊德算法广度优先搜索广度优先搜索广度优先搜索算法广度优先搜索算法void BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;InitQueue(Q);for(v=0;v=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);Enqueue(Q,w);/if/while/ifreturn;思考题：思考题：考虑二叉树的层序考虑二叉树的层序遍历遍历，树的层序遍历树的层序遍历?图的连通性问题图的连通性问题基本方法：基本方法：基于图的遍历算法基于图的遍历算法无向图的连通分量和生成树无向图的连通分量和生成树连通图连通图：从任意顶点出发一次遍历便可访问图中所有顶：从任意顶点出发一次遍历便可访问图中所有顶点。点。非连通图非连通图：需从多个顶点出发遍历，每次可访问一个连：需从多个顶点出发遍历，每次可访问一个连通分量。通分量。深度优先生成树和广度优先生成树深度优先生成树和广度优先生成树设设E(G)为连通图为连通图G中中所有边的集合所有边的集合，则从图中任一顶则从图中任一顶点出发遍历图时点出发遍历图时，必定将必定将 E(G)分成分成两个集合两个集合T(G)和和B(G)，其中其中 T(G)是遍历过程中经历的边的集合是遍历过程中经历的边的集合；B(G)是剩余边的是剩余边的集合集合。显然显然，T(G)和图和图G中的所有顶点一起构成连通图中的所有顶点一起构成连通图G的的极小连通子图极小连通子图（生成树生成树）。根据遍历的策略分别称为深度优根据遍历的策略分别称为深度优先生成树和广度优先生成树先生成树和广度优先生成树。例：例：图图G4的深度优先生成树和广度优先生成树的深度优先生成树和广度优先生成树生成森林生成森林对于对于非连通图非连通图，每个连通分量中的顶点集每个连通分量中的顶点集，和遍历时走过和遍历时走过的边一起构成若干棵生成树的边一起构成若干棵生成树，这些连通分量的生成树组成非这些连通分量的生成树组成非连通图的生成森林连通图的生成森林。提提 纲纲 图的定义和术语图的定义和术语 图的存储结构图的存储结构-数组表示法数组表示法 图的存储结构图的存储结构-邻接表邻接表 图的遍历图的遍历-深度优先搜索深度优先搜索 图的遍历图的遍历-广度优先搜索广度优先搜索 最小生成树最小生成树 有向无环图有向无环图-拓扑排序拓扑排序 有向无环图有向无环图-关键路径关键路径 单源最短路径单源最短路径-迪杰斯特拉算法迪杰斯特拉算法 每一对顶点之间的最短路径每一对顶点之间的最短路径-弗洛伊德算法弗洛伊德算法最小生成树最小生成树（连通网连通网）引例：引例：假设要在假设要在n个城市之间建立通信联络网个城市之间建立通信联络网，则连通则连通n个城个城市只需要市只需要n-1条线路条线路，每条线路有建设的代价每条线路有建设的代价。考虑：最省钱考虑：最省钱？最小生成树最小生成树：连通网的最小代价生成树连通网的最小代价生成树（所谓生成树的代价是所谓生成树的代价是树上各边的代价之和树上各边的代价之和）。MST性质性质假设假设N=(V,E)是一个连通网是一个连通网，U是顶点集是顶点集V的一个的一个非空子集非空子集。若若(u,v)是一条具有最小权值是一条具有最小权值（代价代价）的边的边，其中其中uU，vV-U（任意划分任意划分），则则必存在一棵包含边必存在一棵包含边(u,v)的最小生成树的最小生成树。证明：证明：反证法反证法。假设网假设网N的的任何一棵最小生成树都不包含任何一棵最小生成树都不包含(u,v)。设设T是连通是连通网上的一棵最小生成树网上的一棵最小生成树。普里姆算法普里姆算法(Prim)TE是已生成的最小生成树中边的集合是已生成的最小生成树中边的集合，U是已生成的最小生是已生成的最小生成树中顶点的集合成树中顶点的集合（构造法构造法）算法：算法：U=u0(u0V),TE=,在所有在所有uU,vV-U的边的边(u,v)E中中，找一条代价最小的找一条代价最小的边边(u0,v0)并入并入TE，同时同时v0并入并入U。当当UV时时，重复执行第重复执行第步步。算法的关键问题算法的关键问题：（1）找出一端属）找出一端属U,一端属一端属V-U的的所有边所有边(u,v)（2）确定代价最小的边）确定代价最小的边难点：难点：U和和V-U是是变化的变化的关注：关注：V-U中每个顶点中每个顶点到到U中中顶点的最小边顶点的最小边例：从顶点例：从顶点v1开始构造开始构造初始：初始：U=v1，TE=V-U=v2,v3,v4,v5,v6数组数组closedge记录记录V-U中顶点的情况：中顶点的情况：closedgei-1.lowcost=Mincost(u,vi)|uUclosedgei-1.adjvex=该边所依附的在该边所依附的在U中的顶点中的顶点void MiniSpanTree_PRIM(MGraph G,VertexType u)struct VertexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM;k=LocateVex(G,u);for(j=0;jG.vexnum;+j)if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;for(i=1;iG.vexnum;+i)/每次循环每次循环，找出一条代价最小的边找出一条代价最小的边k=minimum(closedge);printf(closedgek.adjvex,G.vexk);closedgek.lowcost=0;for(j=0;jG.vexnum;+j)if(G.arcskj.adjclosedgej.lowcost)closedgej=G.vexsk.G.arcskj.adj;时间复杂度时间复杂度：O(n2）提提 纲纲 图的定义和术语图的定义和术语 图的存储结构图的存储结构-数组表示法数组表示法 图的存储结构图的存储结构-邻接表邻接表 图的遍历图的遍历-深度优先搜索深度优先搜索 图的遍历图的遍历-广度优先搜索广度优先搜索 最小生成树最小生成树 有向无环图有向无环图-拓扑排序拓扑排序 有向无环图有向无环图-关键路径关键路径 单源最短路径单源最短路径-迪杰斯特拉算法迪杰斯特拉算法 每一对顶点之间的最短路径每一对顶点之间的最短路径-弗洛伊德算法弗洛伊德算法克鲁斯卡尔算法克鲁斯卡尔算法假设连通网假设连通网N=(V,E)，则令最小生成树的初始状态为则令最小生成树的初始状态为只有只有n个顶点而无边的非连通图个顶点而无边的非连通图T=(V,)，把边按代价自小到大把边按代价自小到大排序排序。在在E中中选择代价最小的边选择代价最小的边，若该边依附的若该边依附的顶点落在顶点落在T中不连通中不连通的分量上的分量上，则将此边则将此边加入到加入到T中中，否则舍弃此边而选择下一条代否则舍弃此边而选择下一条代价最小的边价最小的边。依次类推依次类推，直至直至T中所有的顶点都在同一连通分量上为止中所有的顶点都在同一连通分量上为止。算法实现的算法实现的关键问题关键问题：（1）排序）排序（2）判断最小代价边依附的顶点是否属于一个连通分量）判断最小代价边依附的顶点是否属于一个连通分量解决问题的解决问题的思路思路：每个连通分量用一棵：每个连通分量用一棵树树来表示。来表示。时间复杂度时间复杂度：O(eloge)提提 纲纲 图的定义和术语图的定义和术语 图的存储结构图的存储结构-数组表示法数组表示法 图的存储结构图的存储结构-邻接表邻接表 图的遍历图的遍历-深度优先搜索深度优先搜索 图的遍历图的遍历-广度优先搜索广度优先搜索 最小生成树最小生成树 有向无环图有向无环图-拓扑排序拓扑排序 有向无环图有向无环图-关键路径关键路径 单源最短路径单源最短路径-迪杰斯特拉算法迪杰斯特拉算法 每一对顶点之间的最短路径每一对顶点之间的最短路径-弗洛伊德算法弗洛伊德算法有向无环图及其应用有向无环图及其应用有向无环图有向无环图一个无环的有向图一个无环的有向图，简称简称DAG图图。DAG图的作用图的作用描述工程项目或系统的工具描述工程项目或系统的工具例：例：工程问题工程问题（分为活动分为活动，各活动之间有一定的约束各活动之间有一定的约束，先后先后）建造一栋房屋：地质勘探建造一栋房屋：地质勘探，建筑设计建筑设计，工程预算工程预算，材料采购材料采购，人员雇人员雇佣佣，基础施工基础施工，水电安装等水电安装等两个问题两个问题工程能否顺利进行工程能否顺利进行解解：基于：基于AOV网网，利用拓扑排序算法利用拓扑排序算法估算整个工程完成所必须的最短时间估算整个工程完成所必须的最短时间解解：基于：基于AOE网网，利用关键路径算法利用关键路径算法AOV网网用顶点表示用顶点表示活动活动，用用弧表示活动间的优先关系弧表示活动间的优先关系的有向图的有向图称为顶点表示活动的网称为顶点表示活动的网（Activity On Vextex Network)，简称简称AOV网网。网中顶点网中顶点i到顶点到顶点j有一条有向路径有一条有向路径，则则i是是j的的前驱前驱；j是是i的后继的后继。若若是网中一条弧是网中一条弧，则则i是是j的的直接前驱直接前驱；j是是i的的直接后继直接后继。例：例：学习流图学习流图拓扑排序拓扑排序（模拟项目的进行过程模拟项目的进行过程）在有向图中选一个在有向图中选一个没有前驱的顶点没有前驱的顶点且输出之且输出之从图中从图中删除删除该顶点和所有以它为尾的弧该顶点和所有以它为尾的弧重复重复直至全部顶点均已输出直至全部顶点均已输出，或者当前图中或者当前图中不存在无前驱的不存在无前驱的顶点顶点为止为止。不存在无前驱的顶点不存在无前驱的顶点算法实现算法实现拓扑排序算法拓扑排序算法int indegreeMAX_VERTEX_NUM;Status TopologicalSort(ALGraph G)FindInDegree(G,indegree);InitStack(S);for(i=0;inextarc)k=p-adjvex;if(!(-indegreek)Push(S,k);forwhileif(countG.vexnum)return ERROR;else return OK;提提 纲纲 图的定义和术语图的定义和术语 图的存储结构图的存储结构-数组表示法数组表示法 图的存储结构图的存储结构-邻接表邻接表 图的遍历图的遍历-深度优先搜索深度优先搜索 图的遍历图的遍历-广度优先搜索广度优先搜索 最小生成树最小生成树 有向无环图有向无环图-拓扑排序拓扑排序 有向无环图有向无环图-关键路径关键路径 单源最短路径单源最短路径-迪杰斯特拉算法迪杰斯特拉算法 每一对顶点之间的最短路径每一对顶点之间的最短路径-弗洛伊德算法弗洛伊德算法关键路径关键路径AOE网：用网：用边表示活动边表示活动（Activity On Edge)，AOE网是一个带权网是一个带权的有向无环图的有向无环图，其中其中，顶点表示事件顶点表示事件，弧表示活动弧表示活动，权表示活动权表示活动持续的时间持续的时间，通常通常AOE网用来估算工程的完成时间网用来估算工程的完成时间。例：例：研究研究AOE要解决的问题：要解决的问题：完成整项工程需要多少完成整项工程需要多少时间时间？那些那些活动活动是影响工程进度的关键是影响工程进度的关键？关键路径关键路径 路径的长度为路径上各活动的持续的时间之和路径的长度为路径上各活动的持续的时间之和，从源点到汇点最从源点到汇点最长的路径长的路径称为关键路径称为关键路径。假设开始点是假设开始点是v1，从从v1到到vj的最长路径的最长路径长度叫做事件长度叫做事件vj的的最早发生最早发生时间时间，vj发生后发生后，以以vj为弧尾的活动可以开始进行为弧尾的活动可以开始进行。若若ai是以是以vj为弧为弧尾的活动尾的活动，则则ai的的最早开始时间最早开始时间等于事件等于事件vj的的最早发生时间最早发生时间，用用e(i)表表示示。可以定义可以定义最迟最迟开始时间开始时间l(i)，这这是在不推迟整个是在不推迟整个工程完成的前提工程完成的前提下下，活动活动ai最迟最迟必须开始必须开始进行的进行的时间时间 l(i)-e(i)意味着完成活动意味着完成活动ai的时间余量的时间余量，若若l(i)=e(i)，则活动则活动ai为为关关键活动键活动。（即关键路径上的活动即关键路径上的活动）关键活动关键活动设设ve(j)是事件是事件j的的最早发生时间最早发生时间，vl(j)是事件是事件j的的最迟发生时间最迟发生时间，ai由弧由弧表示表示，其持续时间记为其持续时间记为dut()：求求ve(j)（每个事件的每个事件的最早发生时间最早发生时间）ve(0)=0 ve(j)=Maxve(i)+dut()T,j=1,2,.,n-1(顶点个数顶点个数）T是是所有以第所有以第j个顶点为头的个顶点为头的弧的集合弧的集合 求求vl(i)（每个事件的最迟发生时间每个事件的最迟发生时间）vl(n-1)=ve(n-1)vl(i)=Minvl(j)-dut()S,i=n-2,.,1,0(顶点个数顶点个数）,S是所有以第是所有以第i个顶点为个顶点为尾的弧的集合尾的弧的集合设设ai由弧由弧表示表示，其持续时间记为其持续时间记为dut()：e(i)=ve(j)l(i)=vl(k)-dut()算法实现算法实现求求ve初始化：初始化：所有顶点的所有顶点的ve初始化为初始化为0按拓扑序列处理每个顶点按拓扑序列处理每个顶点i依次考察其后继依次考察其后继kif(ve(i)+dut()ve(k)ve(k)=ve(i)+dut()求求vl初始化初始化:所有顶点的所有顶点的vl初始化为初始化为ve(n-1)按拓扑逆序处理每个顶点按拓扑逆序处理每个顶点i依次考察其后继依次考察其后继kif(vl(k)-dut()vl(i)vl(i)=vl(k)-dut()提提 纲纲 图的定义和术语图的定义和术语 图的存储结构图的存储结构-数组表示法数组表示法 图的存储结构图的存储结构-邻接表邻接表 图的遍历图的遍历-深度优先搜索深度优先搜索 图的遍历图的遍历-广度优先搜索广度优先搜索 最小生成树最小生成树 有向无环图有向无环图-拓扑排序拓扑排序 有向无环图有向无环图-关键路径关键路径 单源最短路径单源最短路径-迪杰斯特拉算法迪杰斯特拉算法 每一对顶点之间的最短路径每一对顶点之间的最短路径-弗洛伊德算法弗洛伊德算法最短路径最短路径讨论两个问题讨论两个问题单源最短路径单源最短路径任意两个顶点之间的最短路径任意两个顶点之间的最短路径从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径求最短路径的次序求最短路径的次序假设假设v0到到vi的最短路径如右图所示的最短路径如右图所示原则：原则：按最短路径长度按最短路径长度递增递增的次的次序求取单源最短路径序求取单源最短路径。迪杰斯特拉迪杰斯特拉(Dijkstra)算法算法设求顶点设求顶点v到其余顶点的最短路径到其余顶点的最短路径，S为已求得最短路径的顶点为已求得最短路径的顶点。考虑：考虑：长度长度最小最小的最短的路径的最短的路径，假设是到顶点假设是到顶点vj；下一条长度次短的路径下一条长度次短的路径，要么是要么是(v,vk)或是或是(v,vj,vk)一般情况一般情况：下一条最短路径：下一条最短路径（设其终点为设其终点为x）或者是弧或者是弧(v,x)，或者是或者是中中间只经过间只经过S中的顶点中的顶点而最后到达顶点的路径而最后到达顶点的路径。算法过程算法过程S为已求得最短路径的顶点集为已求得最短路径的顶点集，初始时为初始时为=v；引进一个辅助向量；引进一个辅助向量D，它的每个分量它的每个分量Di记录记录当前所找到的从始点当前所找到的从始点v到到每个终点每个终点vi（viV-S）的的，中间只经过中间只经过S中顶点的中顶点的最短路径的长度最短路径的长度。最小最小Di？初始时初始时：若从：若从v到到vi有弧有弧，则则Di为弧上的权值；否则为弧上的权值；否则Di为为。算法描述算法描述 以邻接矩阵存储有向网以邻接矩阵存储有向网，初始化初始化D；选择选择vj，使得使得Dj=MinDi|viV-Svj就是当前求得得一条从就是当前求得得一条从v出发的最短路径的出发的最短路径的终点终点。令令S=Sj。修改从修改从v出发到集合出发到集合V-S上任一顶点上任一顶点vk可达的最短路径长度可达的最短路径长度。如果如果Dj+arcsjkDk则修改则修改Dk为：为：Dk=Dj+arcsjk 重复操作重复操作共共n-1次次。布尔矩阵布尔矩阵p用每一行标识数组用每一行标识数组D中中，当前路径中包含的顶点有那些当前路径中包含的顶点有那些voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&p,ShortPathTable&D)for(v=0;vG.vexnum;+v)*初始化初始化finalv=FALSE;*初始时初始时，所有顶点都不在所有顶点都不在S中中Dv=G.arcsv0v;for(w=0;wG.vexnum;+w)Pvw=FALSE;if(DvINFINIY)Pvv0=TRUE;Pvv=TRUE;Dv0=0;finalv0=TRUE;for(i=1;iG.vexnum;+i)按长度递增按长度递增，依次求出依次求出n-1条最短路径条最短路径min=INFINIY;for(w=0;wG.vexnum;+w)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=TRUE;for(w=0;wG.vexnum;+w)if(!finalw&(min+G.arcsvwDw)Dw=min+G.arcsvw;Pw=Pv;Pww=TRUE;iffor时间复杂度时间复杂度O(n2)提提 纲纲 图的定义和术语图的定义和术语 图的存储结构图的存储结构-数组表示法数组表示法 图的存储结构图的存储结构-邻接表邻接表 图的遍历图的遍历-深度优先搜索深度优先搜索 图的遍历图的遍历-广度优先搜索广度优先搜索 最小生成树最小生成树 有向无环图有向无环图-拓扑排序拓扑排序 有向无环图有向无环图-关键路径关键路径 单源最短路径单源最短路径-迪杰斯特拉算法迪杰斯特拉算法 每一对顶点之间的最短路径每一对顶点之间的最短路径-弗洛伊德算法弗洛伊德算法每一对顶点之间的最短路径每一对顶点之间的最短路径例：例：方法：方法：这是两个顶点之间的这是两个顶点之间的直接路径直接路径，当然这不一定是最短当然这不一定是最短路径路径，这时的路径可称为这时的路径可称为中间不经过任意其它顶点中间不经过任意其它顶点的的“最短路径最短路径”。需要进行需要进行n次试探次试探，以确定最短路径以确定最短路径。首先考虑经过首先考虑经过v0的情况的情况，(vi,v0,vj)是否存在是否存在（即即(vi,v0)和和(v0,vj)是否存在是否存在），如果存在如果存在，则比较则比较(vi,vj)和和(vi,v0,vj)的路径长的路径长度度，取长度较短者为取长度较短者为从从vi到到vj的中间顶点的序号不大于的中间顶点的序号不大于v0的最短路的最短路径径。注注：D0叫做从叫做从vi到到vj的中间顶点的序号不大于的中间顶点的序号不大于v0的最短路径矩阵的最短路径矩阵。试探的次序：试探的次序：v0,v1,v2继续加入继续加入v1,v2,vn试探试探。例如例如，下一个试探的顶点是下一个试探的顶点是v1，考考察察(vi,.,v1,.,vj)是否存在是否存在，如果存在如果存在，则将其和已经得到的则将其和已经得到的中间顶中间顶点的序号不大于点的序号不大于v0的最短路径相比较的最短路径相比较，取长度较短者为从取长度较短者为从vi到到vj的的中间顶点的序号不大于中间顶点的序号不大于v1的最短路径的最短路径。弗洛伊德算法弗洛伊德算法(Floyd)定义一个定义一个n阶方阵系列：阶方阵系列：D(-1),D(0),D(1),.,D(k),.,D(n-1)D(-1)ij=arcsij D(k)ij=Min D(k-1)ij,D(k-1)ik+D(k-1)kj 0kn-1注注：D(k)ij是从是从vi到到vj的的中间顶点的序号不大于中间顶点的序号不大于k的最短路径矩阵的最短路径矩阵。voidShortestPath_FLOYD(MGraphG,PathMatrix&p,DistancMartrix&D)*pvwu标识当前标识当前D中顶点中顶点v到到w的最短路径包含那些顶点的最短路径包含那些顶点,for(v=0;vG.vexnum;+v)for(w=0;wG.vexnum;+w)Dvw=G.arcsvw;for(u=0;uG.vexnum;+u)pvwu=FALSE;if(DvwINFINIY)Pvwv=TRUE;Pvww=TRUE;forfor(k=0;kG.vexnum;+k)/依次加入顶点依次加入顶点0到到n-1进行试探进行试探for(v=0;vG.vexnum;+v)for(w=0;wG.vexnum;+w)if(Dvk+DkwDvw)Dvw=Dvk+Dkw;for(i=0;iG.vexnum;+i)pvwi=pvki|pkwi;if