图论算法总结及图论建模

图论算法总结图的基本概念图的基本概念二元组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)相连图1图1的邻接矩阵表示邻接矩阵无向图的邻接矩阵是对称的优点：查找/删除某条边是O(1)的缺点•遍历某一点的邻居是O(V)的•空间复杂度很大，O(V*V)每个结点的邻居形成一个链表邻接表图2图2的邻接表表示优点•快速遍历某点所有邻居•占用存储空间小，是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)proceduretarjan(u:longint);varp:node;v:longint;beginf[u]:=false;inc(top);stack[top]:=u;instack[u]:=true;p:=head[u];inc(time);dfn[u]:=time;low[u]:=time;whilep^.keyudobeginv:=p^.key;iff[v]thenbegintarjan(v);low[u]:=min(low[u],low[v]);endelsebeginifinstack[v]thenlow[u]:=min(low[u],dfn[v]);end;p:=p^.next;end;iflow[u]=dfn[u]thenbegininc(s);whilestack[top]udobegininstack[stack[top]]:=false;jd[stack[top]]:=s;top:=top-1;end;instack[stack[top]]:=false;jd[stack[top]]:=s;top:=top-1;end;end;1.2.beginread(n);fori:=1tondobeginnew(head[i]);head[i]^.key:=i;head[i]^.next:=nil;end;read(m);s:=0;fori:=1tomdobeginread(edgex[i],edgey[i]);new(p);p^.key:=edgey[i];p^.next:=head[edgex[i]];head[edgex[i]]:=p;end;fillchar(f,sizeof(f),true);fillchar(instack,sizeof(instack),false);top:=0;time:=0;fori:=1tondoiff[i]thentarjan(i);fillchar(s1,sizeof(s1),0);fori