图论基础教学资料ppt电子教案课件.ppt

《图论基础教学资料ppt电子教案课件.ppt》由会员分享，可在线阅读，更多相关《图论基础教学资料ppt电子教案课件.ppt（28页珍藏版）》请在三一办公上搜索。

1、图论基础,图的概念,定义 一个图G是指一个二元组(V(G),E(G)其中:是非空有限集，称为顶点集，其中元素称为图G的顶点E(G)是顶点集V(G)中的无序或有序的元素对 组成的集合，即称为边集,其中元素称为边,赋权图,定义 若图 的每一条边e 都赋以一个实数w(e)，称w(e)为边e的权，G 连同边上的权称为赋权图。图论算法所研究的往往和权值有关,图的顶点度,定义 在无向图G中，与顶点v关联的边的数目,称为顶点v的度或次数，记为d(v)在有向图中，从顶点v引出的边的数目称为顶点v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d-(v).称d(v)=d+(v)+d-(v)为顶点

2、v的度或次数,图的矩阵表示,对无向图，其邻接矩阵，其中：,对有向赋权图,其邻接矩阵,图的邻接表表示,如图G2的邻接表为：,邻接表实现,链表？没有必要！vector?可行！动态花销较大！数组模拟？灵活！效率高！,邻接表-vector,vector eN;初始化：For(int i=0;ib，权值为cea.push_back(make_pair(b,c);优点：方便,数组模拟,typedef struct int v,next,val;edge;edge eMAXM;int pMAXN,eid;void init()memset(p,-1,sizeof(p);eid=0;void insert(i

3、nt from,int to,int val)eeid.v=to;eeid.val=val;eeid.next=pfrom;pfrom=eid+;,最短路问题,单源点：求赋权图中从给定点到其余顶点的最短路多源点：求赋权图中任意两点间的最短路.,多源最短路Floyd,从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。,for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(mapik+map kjmap

4、ij)mapij=mapik+mapkj;,mapi,j:=minmapi,k+mapk,j,mapi,j熟悉的式子!Floyd是一种动态规划算法!,c i,j,k表示从i 到j 的最短路径的长度，其中k 表示该路径中的最大顶点中间顶点不超过k 的i 到j 的最短路径有两种可能：该路径含或不含中间顶点k。若不含，则该路径长度应为ci,j,k-1，否则长度为 ci,k,k-1+c k,j,k-1。ci,j,k可取两者中的最小值。状态转移：ci,j,k=minci,j,k-1,c i,k,k-1+c k,j,k-1,zoj 1082,要在N个人中传播谣言，每个人传播谣言给他可以联系的人都有个时间，

5、求从哪个人开始传播谣言并使谣言传遍所有人的时间最短。,单源最短路,单源最短路SPFA,初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。直到队列为空时算法结束。SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也 就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。,图的生成树,在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G，即：V(G)=V(G);E(G)E(G)若边

6、集E(G)中的边既将图中的所有顶点连通又不形成回路，则称子图G是原图G的一棵生成树。一棵含有n个点的生成树，必含有n-1条边。,最小生成树,对于一个连通网（连通带权图，假定每条边上的权均为大于零的实数）来说，每棵树的权（即树中所有边的权值总和）也可能不同具有权最小的生成树称为最小生成树。,Kruskal,贪心思想将图G中的边按权值从小到大依次选取，若选取的边使生成树不形成回路，则把它并入TE中，若形成回路则将其舍弃，直到TE中包含N-1条边为止，此时T为最小生成树。,从小到大选取 排序！判断形成回路 并查集！,hdu 1233,某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政

7、府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。,prim.,假设G=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，U,TE初值均为空集。首先从V中任取一个顶点（假定取v1），将它并入U中，此时U=v1，然后只要U是V的真子集(UV)，就从那些一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短边，设为(vi,vj),其中viU,vjV-U，并把该边(vi,vj)和顶点vj分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后得到最小生成树。,关键问题,每次如何从连接T中和T外顶点的所有边中，找到一条最短的,