图论

图论入门图的基本概念二元组G(V,E)称为图(graph)。V为结点(node)或顶点(vertex)集。E为图中结点之间的边的集合。点，用数字0…n-1表示点对(u,v)称为边(edge)或称弧(arc)对于边(u,v)∈E–u和v邻接(adjacent)–e和u、v关联(incident)子图(subgraph):边的子集和相关联的点集图的基本概念有向图：边都是单向(unidirectional)的,因此边(u,v)是有序数对.有时用弧(arc)专指有向边带权图：可以给边加权(weight),成为带权图,或加权图(weightedgraph).权通常代表费用、距离等,可以是正数,也可以是负数稠密性：边和V(V-1)/2相比非常少的称为稀疏图(sparsegraph),它的补图为稠密图(densegraph)路径和圈一条路径(path)是一个结点序列,路上的相邻结点在图上是邻接的如果结点和边都不重复出现,则称为简单路径(simplepath).如果除了起点和终点相同外没有重复顶点和边,称为圈(cycle).不相交路(disjointpath)表示没有除了起点和终点没有公共点的路.更严格地–任意点都不相同的叫严格不相交路(vertex-disjointpath)–同理定义边不相交(edge-disjointpath)路注意:汉语中圈和环经常混用(包括一些固定术语).由于一般不讨论自环(self-loop),所以以后假设二者等价而不会引起混淆连通性如果任意两点都有路径,则称图是连通(connected)的,否则称图是非连通的.非连通图有多个连通分量(connectedcomponent,cc),每个连通分量是一个极大连通子图(maximalconnectedsubgraph),完全图和补图完全图:N个顶点的图，有N(N-1)/2个节点对于(u,v),若邻接则改为非邻接,若非邻接则改为邻接,得到的图为原图的补图完全图=原图∪补图团：完全子图生成树树：N个点，N-1条边的连通图（无环连通图）生成树:包含某图G所有点的树一个图G是树当且仅当以下任意一个条件成立–G有V-1条边,无圈–G有V-1条边,连通–任意两点只有唯一的简单路径–G连通,但任意删除一条边后不连通图例图的表示方法介绍两种图的表示方法：邻接矩阵与邻接表V*V的二维数组A，A[i][j]=0,若(i,j)不相连，A[i][j]=1,若(i,j)相连邻接矩阵无向图的邻接矩阵是对称的优点：查找/删除某条边是O(1)的缺点–遍历某一点的邻居是O(V)的–空间复杂度很大，O(V*V)每个结点的邻居形成一个链表邻接表优点–快速遍历某点所有邻居–占用存储空间小，是O（边数）的，在稀疏图上的效率远胜邻接表缺点：查找/删除边不是常数时间邻接表一、宽度优先遍历(BFS)二、深度优先遍历(DFS)图的遍历算法给定图G和一个源点s,宽度优先遍历按照从近到远的顺序考虑各条边.算法求出从s到各点的距离宽度优先的过程对结点着色.–白色:没有考虑过的点–黑色:已经完全考虑过的点–灰色:发现过,但没有处理过,是遍历边界依次处理每个灰色结点u,对于邻接边(u,v),把v着成灰色并加入树中,在树中u是v的父亲(parent)或称前驱(predecessor).距离d[v]=d[u]+1整棵树的根为s宽度优先遍历(BFS)题目大意：给出N*M个格子，给出K个已经被淹没的格子，其他格子都是干的，求最大的湖的面积（一个格子的面积视为1），如果两个湿的格子四联通（上下左右），则视为这两个格子同属于一个湖输入格式：第一行N，M，K接下来K个格子的坐标AvoidTheLakes（NOI题库2405）Input3453222312311Output4样例解释#....##.##..新发现的结点先扩展得到的可能不是一棵树而是森林,即深度优先森林(Depth-firstforest)特别之处:引入时间戳(timestamp)发现时间d[v]:变灰的时间结束时间f[v]:变黑的时间1=d[v]f[v]=2|V|深度优先遍历(DFS)初始化:time为0,所有点为白色,dfs森林为空对每个白色点u执行一次DFS-VISIT(u)时间复杂度为O(n+m)深度优先遍历(DFS)括号结构性质对于任意结点对(u,v),考虑区间[d[u],f[u]]和[d[v],f[v]],以下三个性质恰有一个成立:–完全分离–u的区间完全包含在v的区间内,则在dfs树上u是v的后代–v的区间完全包含在u的区间内,则在dfs树上v是u的后代DFS树的性质定理(嵌套区间定理):在DFS森林中v是u的后代当且仅当d[u]d[v]f[v]f[u],即区间包含关系.由区间性质立即得到.DFS树的性质一条边(u,v)可以按如下规则分类–树边(TreeEdges,T):v通过边(u,v)发现–后向边(BackEdges,B):u是v的后代–前向边(ForwardEdges,F):v是u的后代–交叉边(CrossEdges,C):其他边，可以连接同一个DFS树中没有后代关系的两个结点,也可以连接不同DFS树中的结点判断后代关系可以借助定理1边的分类当(u,v)第一次被遍历,考虑v的颜色–白色,(u,v)为T边–灰色,(u,v)为B边(只有它的祖先是灰色)–黑色:(u,v)为F边或C边.此时需要进一步判断d[u]d[v]:F边(v是u的后代,因此为F边)d[u]d[v]:C边(v早就被发现了,为另一DFS树中)时间复杂度:O(n+m)定理:无向图只有T边和B边(易证)边分类算法–if(d[v]==-1)dfs(v);//树边,递归遍历–elseif(f[v]==-1)show(“B”);//后向边–elseif(d[v]d[u])show(“F”);//前向边–elseshow(“C”);//交叉边d和f数组的初值均为-1,方便了判断实现细节实现细节DAG:有向无环图拓扑顺序：拓扑排序算法对图G使用DFS算法,每次把一个结点变黑的同时加到链表首部ANEXAMPLE定理1:有向图是DAG当且仅当没有返祖边–如果有返祖边,有环(易证)–如果有环c,考虑其中第一个被发现的结点v,环中v的上一个结点为u,则沿环的路径vu是白色路径,u是v的后代,因此(u,v)是返祖边定理2:该算法正确的得到了一个拓扑顺序的逆序拓扑排序算法一、有向图:SCC划分的Kosaraju算法(有兴趣的同学自己看吧)二、有向图:SCC划分的Tarjan算法三、无向图:割顶和桥的判定图的连通性算法有向图中,u可达v不一定意味着v可达u.相互可达则属于同一个强连通分量(StronglyConnectedComponent,SCC)有向图和它的转置的强连通分量相同所有SCC构成一个DAGSCC的概念Tarjan算法是基于对图深度优先搜索的算法每个强连通分量为搜索树中的一棵子树搜索时，把当前搜索树中未处理的节点加入一个堆栈回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。tarjan算法(参考byvoid博客)定义：–DFN(u)为节点u搜索的次序编号(时间戳)–Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。dfn与low函数算法伪代码tarjan(u){DFN[u]=Low[u]=++Index//为节点u设定次序编号和Low初值Stack.push(u)//将节点u压入栈中foreach(u,v)inE//枚举每一条边if(visnotvisted)//如果节点v未被访问过tarjan(v)//继续向下找Low[u]=min(Low[u],Low[v])elseif(vinS)//如果节点v还在栈内Low[u]=min(Low[u],DFN[v])if(DFN[u]==Low[u])//如果节点u是强连通分量的根repeatv=S.pop//将v退栈，为该强连通分量中一个顶点printvuntil(u==v)}算法演示算法演示算法演示算法演示完整代码voidtarjan(inti){intj;DFN[i]=LOW[i]=++Dindex;instack[i]=true;Stap[++Stop]=i;for(edge*e=V[i];e;e=e-next){j=e-t;if(!DFN[j]){tarjan(j);if(LOW[j]LOW[i])LOW[i]=LOW[j];}elseif(instack[j]&&DFN[j]LOW[i])LOW[i]=DFN[j];}……完整代码if(DFN[i]==LOW[i]){Bcnt++;do{j=Stap[Stop--];instack[j]=false;Belong[j]=Bcnt;}while(j!=i);}}voidsolve(){inti;Stop=Bcnt=Dindex=0;memset(DFN,0,sizeof(DFN));for(i=1;i=N;i++)if(!DFN[i])tarjan(i);}N头奶牛(N≤10000)M对关系（a,b），表示a认为b是受欢迎的关系具有传递性，即若(a,b),(b,c)→(a,c)询问有多少头奶牛是被其他所有奶牛认为是受欢迎的PopularCows(POJ2186)求出所有的强连通分量每个强连通分量缩成一点，则形成一个有向无环图DAG。DAG上面如果有唯一的出度为0的点，则改点能被所有的点可达。那么该点所代表的连通分量上的所有的原图中的点，都能被原图中的所有点可达，则该连通分量的点数就是答案。DAG上面如果有不止一个出度为0的点，则这些点互相不可达，原问题无解，答案为0；PopularCows(POJ2186)对于无向连通图G–割顶是去掉以后让图不连通的点–桥是去掉以后让图不连通的边割顶与桥low[u]为u及其的后代所能追溯到的最早(最先被发现)祖先点v的pre[v]值类似有向图的计算方式,注意无向图只有T和B边low[u]=dfn[u]=cnt++;for(u的不等于u的邻居v){//不考虑自环if(pre[v]==-1){//白色点dfs-visit(v);if(low[u]low[v])low[u]=low[v];}elseif(low[u]dfn[v])low[u]=dfn[v];}无向图的LOW函数在一棵DFS树中根root是割顶当且仅当它至少有两个儿子其他点v是割顶当且仅当它有一个儿子u,从u或者u的后代出发没有指向v祖先(不含v)的B边,则删除v以后u和v的父亲不连通,故为割顶割顶判定算法:对于DFS树根,判断度数是否大于1对于其他点u,如果不是根的直接儿子,且low[u]=dfn[P[u]],则它的父亲v=P[u]是割点割顶的判定Network(POJ1144)voiddfs(intu,intdep){dfn[u]=low[u]=dep;for(inti=0;iadj[u].size();i++){intv=adj[u][i];if(!dfn[v]){dfs(v,dep+1);if(u==rt)rt_son++;else{low[u]=min(low[u],low[v]);if(low[v]=dfn[u])cut[u]=true;//由后继节点搜不到比该点更早的点，则该点是割点}}elselow[u]=min(low[u],dfn[v]);}}题目大意：给定一个无向图，求有多少点是割点边(u,v)为桥当且仅当它不在任何一个简单回路中发现T边(u,v)时若发现v和它的后代不存在一条连接u或其祖先的B边,则删除(u,v)后u和v不连通,因此(u,v)为桥桥的判定算法:发现T边(u,v)时若LOW[v]d[u](注意不能取等号),则(u,v)为桥桥的判定Byteotia有n个