图论在竞赛中的应用.ppt

图论在竞赛中的应用 福州大学 包能辉 2006.6.14 图论问题 图论是数学的一个分支，它以图为研究对象，研究节点和边组成的图形的数学理论和方法。 图论问题与程序设计联系紧密，经典的图论模型以及相关算法已成为竞赛中不可或缺的知识。 竞赛中主要遇到的图论问题 图的连通性 可遍历性问题 生成树问题 最短路 网络流 匹配 竞赛中图论应用关键在于图论模型的建立 一、图的相关数据结构 邻接矩阵（很常用） 邻接表、压缩邻接数组 前向星、后向星 关联矩阵（几乎不用） 邻接表 用数组直接实现（耗空间） 链表实现 用STL中的动态数组vector vector int graph[N]; 压缩邻接数组，可以加一个表f[i],表示第i个点后接的边在大数组中的起始下标。不适合有点边的删除和增加的题目。缺点是点的输入必须有一定规律。前向星弥补了这个缺点。 一般在点多边少时使用 前向星 压缩邻接数组的扩展 struct graphtype { int a, b; bool operatr( const graphtype x) const { return ax.a; } } graph[M]; sort(graph,graph+m); 与压缩邻接数组相类似，可以加个表f[i]; 二、图的基本算法 DFS BFS DFS 深度优先的时候可以记下许多用的信息。许多连通性问题，都可以用BFS高效的解决。 判断图是否连通 无向图的割顶和桥 环的检测 DFS框架 int c[MAX]; //遍历标志,c[i]=0未遍历,1已遍历未检查,2已遍历已检查 int depth[MAX]; //深度 int graph[MAX][MAX]; //邻接矩阵 int Cut[MAX]; //Cut[i]==1 割点 int Brige[MAX][MAX]; //Brige[i][j]==1 (i,j)为桥 int Root; //根节点 int Ancestor[MAX];//Ancestor[k]为k及k的子孙相连的辈分最高的祖先 void findnode(int k,int kfather,int deep) { int i,tot; //tot为顶点k的儿子数量 c[k]=1;depth[k]=deep; Ancestor[k]=deep;tot=0; for (i=0;in;i++) { if (graph[i][k]i!=kfatherc[i]==1) Ancestor[k]=min(Ancestor[k],depth[i]); if (graph[i][k] c[i]==0) { findnode(i,k,deep+1);tot++; Ancestor[k]=min(Ancestor[k],Ancestor[i]); //求割点 if ((k==Roottot1)||(k!=RootAncestor[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是图的割顶。 如果y是x的儿子并且AncestoryDx(注意不是=)，则(x,y)是图的桥。 zju2588 有向图的极大强连通分支 Kosarajus Algorithm 有向图做DFS，记下后序遍历编号dfn。 改变有向图中所有边的方向 从最大的dfn 开始再DFS, 每次DFS 找到一个极大连通分支 2-sat 问题(xi + xj)... 构造边(－xi， xj) 和(－xj ，xi) 求极大连通子图 PKU2723 Tarjans Algorithm 只需要修改一下基本的DFS过程，只遍历一次，用到一个栈。Tarjan用到了Ancestor数组，类似桥的算法。该点通过后向边所能回到Ancestor的点，那么就可以说是个环，那么经过的点必是强连通的。 Gabow‘s Algorithm 思想同Tarjan，不过没有了Ancestor数组，取而代之的另一个栈。因为并没必要所有结点的Ancestor ，在有哪些信誉好的足球投注网站时，一个栈保持树的访问顺序，另一个栈开始同样按顺序压结点，一但出现后向边，退栈至back点，在递归回到back