第七章-图PPT课件

.,1,第七章图,7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径,.,2,第七章图,在线性结构中，数据元素之间是一对一的线性关系，除第一个数据元素和最后一个数据元素之外，每个数据元素只有一个直接前驱和一个直接后继。在树型结构中，数据元素之间是一对多的层次和分支的关系，除根结点外，每个数据元素都只有一个直接前驱（即双亲结点），但每个数据元素都可能有多个直接后继（即孩子结点）。然而在图型结构中，数据元素之间的关系是任意的，是多对多的关系，既图中任意两个结点之间都可能相关。,.,3,7.1图的定义和术语,图中的数据元素通常称为顶点。图G由两个集合V和E组成，通常记为G(V，E)其中，V是图中顶点的有穷非空集合，E是V中顶点间的边的有穷集。除此之外，也通常将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。图可分为无向图和有向图两类。,.,4,7.1图的定义和术语,无向图：图中的每条边都是无方向的。在无向图中，一条无向边是由两个顶点组成的无序对，通常用圆括号表示。例如（vi，vj）表示一条无向边，在无向图中，（vi，vj）和（vj，vi）是两条相同的无向边。（无向）完全图：任意两个顶点之间都有一条无向边的无向图。（无向）完全图是含有n个顶点和n(n-1)/2条边的无向图。,.,5,7.1图的定义和术语,如下图G是一个无向图,图G可记作：G（V，E），其中VA,B,C,D,E,FE=(A,B),(A,E),(B,F),(B,E),(C,F),(C,D),(D,F),若(vi，vj)是一条无向边，则称顶点vi和vj互为邻接点，或称vi和vj相邻接；同时称边(vi，vj)依附于顶点vi和vj，或称边(vi，vj)与顶点vi和vj相关联。,.,6,7.1图的定义和术语,有向图：图中的每条边都是有方向的。在有向图中，一条有向边是由两个顶点组成的有序对，通常用尖括号表示。例如表示一条有向边，vi是边的起始点，vj是边的终点。因此，和是两条不同的有向边。有向边也称为弧，边的起始点称为弧尾，终点称为弧头。,.,7,7.1图的定义和术语,如下图G是一个有向图,图G可记作：G（V，E），其中VA,B,C,D,E,FE=,若vi,vj是图中的一条有向边，则称顶点vj是vi的领接点，或称顶点vi邻接到vj，或顶点vj邻接自顶点vi，并称弧vi,vj依附于顶点vi和vj，或称弧vi,vj与顶点vi和vj相关联。,.,8,7.1图的定义和术语,有向完全图：任意两个顶点之间都有一对相向的有向边的有向图。即含有n个顶点和n(n-1)条弧（有向边）的有向图。,权：与图的边或弧相关的数。这些权可以表示从一个顶点到另一个顶点的距离或者耗费。网：弧（或边）带权的图称为网。,.,9,7.1图的定义和术语,子图：给定图G1=（V1，E1）、图G2=（V2，E2），若V1是V2的子集，E1是E2的子集，则称G1是G2的子图。例：,.,10,7.1图的定义和术语,无向图中顶点v的度：指的是和v相关联的边的数目，通常记为D(v)。,例：在右图中D(B)=D(F)3D(A)=D(C)=D(D)=D(E)=2,结论无向图中：顶点的度之和=边数的两倍,.,11,7.1图的定义和术语,有向图中顶点v的度分为入度和出度。顶点v的入度：以顶点v为终点的有向边的数目，记为ID(v)；顶点v的出度：以顶点v为起始点的有向边的数目，记为OD(v)；有向图中顶点v的度则定义为该顶点的入度和出度之和，即D(v)ID(v)十OD(v)。,.,12,7.1图的定义和术语,例：在下面的有向图中ID(A)=1；OD(A)=2;D(A)=3ID(C)=1；OD(C)=1;D(C)=3,结论有向图中：顶点入度之和=顶点出度之和=弧数,.,13,7.1图的定义和术语,在无向图G中，若存在一个顶点序列（vp,vi1,，vin，vq），使得(vp，vil)，(vi1,vi2)，(vin，vq)均属于边集E(G)，则称顶点vp到vq存在一条路径。若G是有向图，则路径也是有向的，它由E(G)中的有向边vp，vil,vil，vi2,，vin，vq组成。路径长度：该路径上边的数目。序列中顶点不重复出现的路径称为简单路径。起点和终点相同(vpvq)的路径称为回路。若一条路径上除了vp和vq可以相同外，其余顶点均不相同，则称此路径为简单回路或简单环。,.,14,7.1图的定义和术语,例如：在有向图G中：（A,B,C,F）是图G的一条路径，它是由有向边序列,组成，它是一条简单路径，路径的长度是3。（A,B,C,F,B,E）也是图G的一条路径，它是由有向边序列A,B,组成，它不是简单路径，这条路径的长度是5。,也是图G的一条路径，这条路径的长度是4，它是一条简单回路。,.,15,7.1图的定义和术语,在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。若图G中任意两个不同的顶点vi和vj都连通，则称G为连通图。无向图G的一个极大连通子图称为G的一个连通分量。显然，任何连通图的连通分量只有一个，就是它自身，而非连通的无向图有多个连通分量。,.,16,7.1图的定义和术语,例如：下图所示为两个无向图G1和G2，其中:G1是一个连通图G2是由4个连通分量组成的非连通图。,.,17,7.1图的定义和术语,在有向图G中，若对于其中的任意两个不同的顶点vi和vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图G的极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。,.,18,7.1图的定义和术语,例如：下图所示为两个有向图G1和G2，其中:G1是一个强连通图，G2是由3个强连通分量组成的非连通图。,.,19,7.1图的定义和术语,结论有n个顶点的有向图最多有条边，最少有条边。有n个顶点的无向图最多有条边，最少有条边。有n个顶点的连通图最少有条边，若少于条边，图一定是非连通图，多于条边，连通图中一定有环路存在。,n(n-1),n(n-1)/2,0,0,n-1,n-1,n-1,.,20,7.1图的定义和术语,生成树：一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只含有足以构成一棵树的n-1条边。如图所示：连通图G的一棵生成树,注意:一棵有n个顶点的生成树一定有n-1条边。但有n个顶点和n-1条边的图，一定是一棵生成树吗？,.,21,7.2图的存储结构,由于图的结构比较复杂，除了要把图的各顶点存入计算机，还应该把各顶点之间的关系也输入计算机，而图中任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序映象的存储结构，但可以借助数组的数据类型表示图中顶点之间的关系，即图的领接矩阵的存储结构。另一方面，也可以用链表表示图，如领接表、领接多重表和十字链表是图常用的三种链式存储结构。,.,22,7.2图的存储结构,对于具体问题中的图来说,要为其选择最好的存储结构，不仅仅要依赖于图的性质如有向图还是无向图,以及图中的数据,例如:顶点数,边数等,而且还与在图上所实施的操作有关，例如对图中的顶点进行插入或删除操作的频率等.下面将主要介绍图的领接矩阵和领接表这两种存储方式。,.,23,7.2.1邻接矩阵,邻接矩阵(数组表示法）是用二维数组表示顶点之间相邻关系的存储结构。设G(V，E)是具有n个顶点的无权图，则G的邻接矩阵是具有如下性质的n阶方阵：,.,24,7.2.1邻接矩阵,例1：给定4个顶点的有向图,.,25,7.2.1邻接矩阵,例2：给定6个顶点的无向图,A,注:无向图的邻接矩阵是对称的，即Aij=Aji,.,26,7.2.1邻接矩阵,若G(V，E)是具有n个顶点的带权图（网）则G的邻接矩阵是具有如下性质的n阶方阵：,.,27,7.2.1邻接矩阵,例：给定6个顶点的无向网（无向带权图）,无向网G1及其领接矩阵存储结构,.,28,7.2.1邻接矩阵,例2：给定6个顶点的有向网（有向带权图）,v0v1v2v3v4v5v01030100v1v2550v310v42060v5,图G2的领接矩阵存储结构,有向带权图G2,.,29,7.2.1邻接矩阵,结论在无向图的领接矩阵中,顶点vi的度等于邻接矩阵中第i行(或第i列)上非零元素的个数；在有向图的领接矩阵中，顶点vi的出度等于邻接矩阵中的第i行上非零元素的个数;在有向图的领接矩阵中，顶点vi的入度等于邻接矩阵中的第i列上非零元素的个数.,.,30,7.2.1邻接矩阵,图的领接矩阵存储表示用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储图的顶点信息。其形式说明如下：#definen6/*图的顶点数*/#definee8/*图的边（弧）数*/typedefstructcharvexsn+1；/*设顶点的数据类型为char型*/intarcsn+1n+1；/*设权值类型为int*/Graph；GraphG;,.,31,7.2.1邻接矩阵,创建无向网的算法#defineMAX10000CreatGraph(Graph*G)/*建立无向网络*/inti，j，k；intw；for(i1；i=n；i+)G-vexsigetchar()；/*读入n个顶点信息*/for(i1；i=n；i+)for(j1；j=n；j+)G-arcsijMAX；/*邻接矩阵初始化*/for(k1；k=e；k+)/*读入e条边*/scanf(”ddd”，vnext;,.,44,7.3.2图的广度优先搜索,广度优先搜索类似于树的按层次遍历。设图G的初态是所有顶点均未访问过，在G中任选一顶点Vi为初始出发点，则广度优先搜索的基本思想是：首先访问出发点Vi，接着依次访问vi的所有邻接点wl，w2，wt，然后，再依次访问与wl，w2，wt邻接的所有未曾访问过的顶点，依此类推，直至图中所有和出发点v有路径相通的顶点都已访问到为止;若此时图中尚有顶点未被访问（即当图为非连通图时），则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。,.,45,7.3.2图的广度优先搜索,例1:图的广度优先搜索,12345678,图7.13(a),广度优先搜索结果：v1-v2-v3-v4-v5-v6-v7-v8,.,46,7.3.2图的广度优先搜索,广度优先搜索算法如下：voidBFS(GraphG,intv）InitQueue(Q);visitedv=1;printf(“d”，v);EnQueue(Q,v);while(!QueueEmpty(Q)DelQueue(Q,u);for(w=FirstAdjVex(G,u);w;w=wnext)if(!visitedw)visitedw=1;printf(“d”，w);EnQueue(Q,w);,.,47,7.3.2图的广度优先搜索,voidBFSTraverse(GraphG,intv)for(v=0;vG.vexnum;v+)visitedv=false;for(v=0;vG.vexnum;v+)if(!visitedv)BFS(G,v);,.,48,7.4图的连通性问题,7.4.1无向图的连通分量和生成树在无向图的遍历算法中，若从某个顶点出发访问下一个顶点时增加这两个顶点之间的边，则可得到连通图的一棵生成树或不连通的图的生成森林。由深度优先遍历得到的生成树称为深度优先生成树。由广度优先遍历得到的生成树称为广度优先生成树。,.,49,7.4.2最小生成树,图的生成树不是唯一的，从不同的顶点出发进行遍历，可以得到不同的生成树。对于连通网G(V，E)而言，图中的边是带权的，因而G的生成树的各条边也是带权的。我们把生成树各条边的权值总和称为生成树的权（或称代价），并把权最小的生成树称为G的最小生成树。生成树和最小生成树有许多重要的应用。例如：令图G的顶点表示城市，边表示连接两个城市之间的通讯线路。n个城市之间最多可设立n(n-1)2条线路，把n个城市连接起来至少要n-1条线路,则图G的生成树表示了建立通讯网络的可行方案。,.,50,7.4.2最小生成树,如果给图中的边都赋予权，而这些权可表示两个城市之间通讯线路的长度或建造代价，那么，如何选择n-1条线路，使得建立的通讯网络其线路的总长度最短或总代价最小呢?这就转换为如何构造该图的一棵最小生成树的问题。以下我们只讨论无向图的最小生成树问题。,.,51,7.4.2最小生成树,.,52,7.4.2最小生成树,构造最小生成树可以有多种算法，其中大多数构造算法都是利用了最小生成树的下述性质：设G(V,E)是一个连通带权图，U是顶点集V的一个真子集。若边(u,v)（uU，vV-U）是图G的所有边中权值最小的一条边，则一定存在图G的一棵最小生成树包含此边(u,v)。这个性质称为MST性质。可用反证法证明(略)下面将重点介绍两个利用MST性质构造最小生成树的算法：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。,.,53,7.4.2最小生成树,Prim算法的基本思想是：假设G=(V，E）是连通网，设T=(U，TE)是最小生成树初始情况下设Uu0(u0V）,TE.重复执行下述操作：在所有的uU，vVU的边(u，v)E中，找一条权值最小的边（u0,v0)，将其并入集合TE，同时将v0并入集合U，直至UV为止，此时TE中必有n1条边，则T=(U,TE)即为G的一棵最小生成树。,.,54,7.4.2最小生成树,Prim算法求最小生成树：,1.（1,2）被选中U=1,2,2.（2,5）被选中U=1,2,5,3.（2,3）被选中U=1,2,3,5,4.（1,4）被选中U=1,2,3,4,5,6.（5,7）被选中U=1,2,3,4,5,6,7,7.（7,8）被选中U=1,2,3,4,5,6,7,8,5.（3,6）被选中U=1,2,3,4,5,6,U=1,TE=,.,55,7.4.2最小生成树,Kruskal算法的基本思想：假设G=(V，E）是连通网，设T=(U，TE)是要求的最小生成树。初始情况下设UV,TE.并将连通网中的所有边按权值的非递减次序进行排列，然后执行：依次将连通网中有序排列的各条边（u,v）作如下处理：若将（u,v）加入TE中后，TE中的边构成了一条回路，则不将（u,v）加入TE中；否则将（u,v）加入TE中。重复上述过程，直至TE中已有n-1条边为止。此时T=(U,TE)即为G的一棵最小生成树。,.,56,7.4.2最小生成树,Kruskal算法求最小生成树过程：,1.（1，2）被选中,2.（2，5）被选中,3.（2，3）被选中,4.（1，4）被选中,6.（5，6）不被选中,8.（5，7）被选中,7.（7，8）被选中,5.（3，6）被选中,5,.,57,7.4.2最小生成树,练习题：分别用Prim算法和Kruskal算法求如下无向图的最小生成树。,无向带权图G,用Prim算法求其最小生成树,用Kruskal算法求其最小生成树,.,58,7.5有向无环图及其应用,有向无环图:是一个无环的有向图.简称DAG图.有向无环图的作用:常用来描述一个过程（如一个系统进行的过程，一个工程进行的过程）.通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，通常我们把这些子工程称为活动，当这些活动完成时，整个工程也就完成了。,.,59,7.5.1AOV网,而在各个活动之间,有些必须按规定的先后次序进行，有些则没有先后次序要求.那么，工程中的这种各个活动之间的次序要求,可以用一个有向图来表示：图中每个顶点代表一个活动.如果从顶点vi到顶点vj之间存在有向边，则表示活动vi必须先于活动vj进行.这种用顶点表示活动,用有向边（弧）表示顶点间优先关系的有向图称为AOV网.比如教学计划的制定.,.,60,7.5.1AOV网,表示必修课程优先关系的有向图（AOV网）,.,61,7.5.1AOV网,AOV网的特点:在AOV网中一定不能有回路。在AOV-网中如果出现了有向环，则意味着某项活动应以自己的完成作为先决条件，这是不合理的，工程将无法进行。因此，对给定的有向图，判断它是否是一个AOV-网，应先判断有向图中是否存在环路。检测有向图中是否存在有向环,可用拓扑排序的方法即对AOV-网构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则AOV-网中必定无环，否则，AOV-网中一定存在环路。,.,62,7.5.1AOV网,拓扑排序：1.在有向图中选一个没有前驱的顶点（即入度为0的顶点）且输出之。2.从图中删除该顶点和所有从它发出的边。重复上述两步，直到全部顶点均已输出或当前图中不存在无前驱的顶点为止。若所有顶点均已输出，则说明有向图中无有向环，得到的顶点输出序列即为拓扑序列；否则说明未输出的顶点构成了有向环。,.,63,7.5.1AOV网,举例：,拓扑序列为：,C1,C4,C2,C3,C5,C7,C9,C11,C6,C10,C12,C8,.,64,7.5.2关键路径,与AOV网相对应的是AOE网(ActivityOnEdgenetwork)，AOE网即边表示活动的网络。AOE网是一个有向带权图，图中的：边：表示活动(子工程)，边上的权：表示该活动的持续时间，即完成该活动所需要的时间；顶点：表示事件，每个事件是活动与活动之间的转接点，即表示在它之前的所有活动已经完成，在它之后的活动可以开始。AOE网的作用：它通常用来表示一个工程的计划或进度，可用来估算工程的完成时间。,.,65,7.5.2关键路径,举例：,工程的开始点（源点）,工程的完成点（终点）,.,66,7.5.2关键路径,关键路径：路径长度最长的路径。关键活动：关键路径上的活动。求工程的最短工期：在AOE网上求一条关键路径的长度。,问题：1.完成此工程最短需要多长时间？2.影响此工程进度的活动是哪些？3.如何加快工程进度、缩短工程完成时间？,源点到终点的最长路径的长度,最长路径上的所有活动,缩短最长路径长度,.,67,7.5.2关键路径,设源点是v1,定义：事件vi的最早发生时间ve(i)：事件vi最早可以发生的时间，即从v1到vi的最长路径长度。事件vi的最迟发生时间vl(i)：在不影响整个工程进度的前提下事件vi最迟必须发生的时间。活动ak=的最早开始时间ee(k)：等于事件vi的最早发生时间ve(i)。活动ak=的最迟开始时间el(k)：在不影响整个工程进度的前提下，活动ak最迟必须开始的时间，等于事件vj的最迟发生时间vl(j)减去活动ak的持续时间dut()。关键活动ak=即为ee(k)=el(k)的活动。,.,68,7.5.2关键路径,E,E,.,69,7.5.2关键路径,顶点Ive(i)vl(i)V1v2v3v4v5v6v7v8v9,064577161418,0668710161418,64511297424,0006457771614,02366877101614,02302300300,.,70,7.5.2关键路径,2条关键路径,关键路径长度均为18，关键活动为：a1a4a7a8a10a11,.,71,7.5.2关键路径,由此可见，用AOE网来估算某些工程完成的时间是非常有用的。要想加快整个工程的完成速度，缩短整个工期，只有提高关键活动的速度才有效。另外，若网中有几条关键路径，那么只提高一条关键路径上的关键活动的速度还不能导致整个工程缩短工期，而必须提高同时在几条关键路径上的活动的速度。注意：关键活动的速度提高是有限度的。,.,72,7.5.2关键路径,练习题：求下图所示的AOE网的所有关键路径。,有10个事件、14个活动的AOE-网,.,73,7.6最短路径,在复杂的交通网络中，人们常常会提出这样的问题：从A地到B地之间是否有道路相通?在有多条通路的情况下，哪一条道路长度最短（最省时、最省钱）等?解决这类问题也就是在带权图中求最短路径的问题。交通网络可用带权图来表示。图中的顶点表示城市，边表示两个城市之间有路相通，边上的权值可表示两个城市之间的距离（或交通费用或途中所花费的时间等）。那么，求两个顶点之间的最短路径，是指在连接两个顶点的所有路径中，选择一条路径上各边权值之和最小的路径。最短路径的问题常见两种:从某源点到其余各顶点之间的最短路径(要求)每一对顶点之间的最短路径(不要求),.,74,7.6.1单源点最短路径,求从某个源点到其余各个顶点的最短路径,例1：如有向带权图G,源点终点最短路径长度v0v1v0v2（v0v2)10v0v3（v0v4v3）50v0v4（v0v4）30v0v5（v0v4v3v5）60,有向带权图G,.,75,7.6.1单源点最短路径,v0v1v2v3v4v5012345v001030100v11v22550v3310v442060v55,图G的领接矩阵存储结构A66,有向带权图G,图G以及它的领接矩阵的存储结构如下所示：,.,76,7.6.1单源点最短路径,迪杰斯特拉（Dijkstra）算法算法的核心思想：按最短路径长度递增的次序依次求出各条最短路径。为了描述算法步骤，需要引入几个辅助向量：Di：表示当前所找到的从源点V0出发到终点Vi的最短路径的长度；初始状态Di=A0iS：为已经求出了最短路径的顶点组成的集合；初始状态为S=V0；Pi：记录当前所找到的从源点出发只经过S中的顶点到达Vi的最短路径中Vi的前驱顶点；那么当S中包含了图中所有顶点时，Di即为最终找到的从源点出发到达Vi的最短路径长度，Pi即为最终找到的从源点出发到达Vi的最短路径中Vi的前驱顶点。,.,77,7.6.1单源点最短路径,分析：显然，长度最短的一条最短路径就是长度为：Dj=minDi|ViV的路径。此路径是：（V0，Vj）那么下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是Vk，则可想而知，这条路径或者是（V0，Vk）或者是（V0，Vj，Vk）。即它的长度或者是从V0到Vk的弧上的权值，或者是Dj加上从Vj到Vk的弧上的权值之和。那么，长度倒数第三短的最短路径是？依次下去，一般情况下下一条最短路径是？,.,78,7.6.1单源点最短路径,已知S集合是已经求得了最短路径的终点的集合，那么一般情况下，可以证明：下一条长度次短的最短路径（设其终点是Vx)或者是（V0，Vx），或者是中间只经过S中的顶点而最后到达顶点Vx的路径。反证法证明：假设下一条要找的长度次短的最短路径上有一个顶点不在S中，则说明存在一条终点不在S中，而路径长度比此路径长度更短的路径。但这是不可能的。因为我们是按最短路径长度递增的次序来产生各条最短路径的，故长度比此路径更短的所有最短路径都已经产生，它们的终点必定在S中，即假设不成立！,.,79,7.6.1单源点最短路径,因此，一般情况下：下一条长度次短的最短路径（设其终点是Vx)，或者是（V0，Vx），或者是中间只经过S中的顶点而最后到达顶点Vx的路径。那么下一条长度次短的最短路径的长度或者是弧(V0，Vx)上的权值A0x;或者是Dk(VkS)加上弧(Vk,Vx)的权值:DkAkx(VkS,VxV-S)。即下一