图论在竞赛中的应用ppt课件.ppt

《图论在竞赛中的应用ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论在竞赛中的应用福州大学包能辉2006.6.14图论问题图论是数学的一个分支，它以图为研究对象，研究节点和边组成的图形的数学理论和方法。图论问题与程序设计联系紧密，经典的图论模型以及相关算法已成为竞赛中不可或缺的知识。竞赛中主要遇到的图论问题图的连通性可遍历性问题生成树问题最短路网络流匹配竞赛中图论应用关键在于图论模型的建立一、图的相关数据结构邻接矩阵（很常用）邻接表、压缩邻接数组前向星、后向星关联矩阵（几乎不用）邻接表用数组直接实现（耗空间）链表实现用STL中的动态数组vectorvectorgraph[N];压缩邻接数组，可以加一

2、个表f[i],表示第i个点后接的边在大数组中的起始下标。不适合有点边的删除和增加的题目。缺点是点的输入必须有一定规律。前向星弥补了这个缺点。一般在点多边少时使用前向星压缩邻接数组的扩展structgraphtype{inta,b;booloperatr<(constgraphtype&x)const{returna

3、连通无向图的割顶和桥环的检测DFS框架intc[MAX];//遍历标志,c[i]=0未遍历,1已遍历未检查,2已遍历已检查intdepth[MAX];//深度intgraph[MAX][MAX];//邻接矩阵intCut[MAX];//Cut[i]==1割点intBrige[MAX][MAX];//Brige[i][j]==1(i,j)为桥intRoot;//根节点intAncestor[MAX];//Ancestor[k]为k及k的子孙相连的辈分最高的祖先voidfindnode(intk,intkfather,intdeep){inti,to

4、t;//tot为顶点k的儿子数量c[k]=1;depth[k]=deep;Ancestor[k]=deep;tot=0;for(i=0;i1)

5、

6、(k!=Ro

7、ot&&Ancestor[i]>=depth[k]))Cut[k]=1;//求桥的if(Ancestor[i]>depth[k])Brige[k][i]=1;}}c[k]=2;}BFS许多图论的算法中都用到BFS的思想拓扑排序等问题的实现都可以看成特殊的BFS三、图的连通性问题无向图的割顶、桥有向图的极大强连通分支图的块划分连通度问题无向图的割顶、桥在DFS框架上增加Ancestork和Tot值的计算Ancestork记录和k及k的子孙相连的辈份最高的祖先的深度。Tot表示k的儿子数。当i的某个儿子及儿子的子孙没有指向i祖先的后向边时，i是图的割

8、顶。如果y是x的儿子并且Ancestory>Dx(注意不是>=)，则(x,y)是图的桥。zju2588有向图的极大强连通分支Kosaraju'sAlgorithm有向图做DFS，记下后序遍历编号dfn。改变有向图中所有边的方向从最大的dfn开始再DFS,每次DFS找到一个极大连通分支2-sat问题(xi+xj)...构造边(－xi，xj)和(－xj，xi)求极大连通子图PKU2723Tarjan'sAlgorithm只需要修改一下基本的DFS过程，只遍历一次，用到一个栈。Tarjan用到了Ancestor数组，类似桥的算法。该点通过后向边所能回到

9、Ancestor的点，那么就可以说是个环，那么经过的点必是强连通的。Gabow‘sAlgorithm思想同Tarjan，不过没有了Ancestor数组，取而代之的另一个栈。因为并没必要所有结点的Ancestor，在搜索时，一个栈保持树的访问顺序，另一个栈开始同样按顺序压结点，一但出现后向边，退栈至back点，在递归回到back点时再通过第一个栈将所有的该强连通子图的点标记。PKU2762没有割顶的无向图称做块。把每个块缩成一个点，就得到一棵树，它的边就是桥。四、可遍历性问题可行性遍历问题是一个很实际的问题，按一定顺序走遍图的所有顶点或者所有边。H

10、amiltion回路问题，旅行商问题(TSP)，欧拉回路问题，中国邮递员问题，骑士周游问题。Hamiltion回路问题，TSP属于NP问