10月25日上午曹文《图的相关算法》

图论图的基本概念图的基本概念二元组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（边数）的，在稀疏图上的效率远胜邻接矩阵缺点：查找/删除边不是常数时间邻接表前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.用len[i]来记录所有以i为起点的边在数组中的存储长度.用head[i]记录以i为边集在数组中的第一个存储位置.链式前向星那么排完序后就得到:编号:1234567起点u:1112344终点v:2353415head[1]=1len[1]=3head[2]=4len[2]=1head[3]=5len[3]=1head[4]=6len[4]=2链式前向星但是利用前向星会有排序操作,如果用快排时间至少为O(nlog(n))如果用链式前向星,就可以避免排序.我们建立边结构体为：structedge{intnext,to,w};其中edge[i].to表示第i条边的终点,edge[i].next表示与第i条边同起点的下一条边的存储位置,edge[i].w为边权值。另外还有一个数组head[i],它是用来表示以i为起点的第一条边存储的位置，实际上你会发现它是以i为起点的所有边的最后输入的那个编号。head[]数组一般初始化为-1。链式前向星voidadd(intu,intv,intw){edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}我们在遍历以u节点为起始位置的所有边的时候是这样的:for(inti=head[u];~i;i=edge[i].next)链式前向星•一、宽度优先遍历(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:该算法正确的得到了一个拓扑顺序的逆序拓扑排序算法图的最短路问题SSSP的Spfa算法SSSP的Dijkstra算法差分约束系统Floyd-warshall算法给定带权图和一个起点s,求s到所有点的最短路(边权和最小的路径)最短路有环吗•正环:何必呢,删除环则得到更短路•负环:无最短路,因为可以沿负环兜圈子单源最短路问题(SingleSourceShortestPath)最优性原理:若最短路uv经过中间结点w,则uw和wv的路径分别是u到w和w到v的最短路意义:贪心、动态规划最优性原理最短路的表示•s到所有点的最短路不需要分别表示•最短路树:到每个点都沿着树上的唯一路径走•实际代码:记录每个点的父亲pred[u]即可•输出最短路:从终点沿着pred[u]递推回起点最短路的表示松弛（RELAX）操作•一条边(u,v)被称为紧的(tense),如果dist(u)+w(u,v)dist(v)•可以松弛：dist(v)=dist(u)+w(u,v),pred(v)=u结论•存在紧的边，一定没有正确的求出最短路树•不存在紧的边，一定正确的求出最短路树SPFA算法SPFA算法伪代码voidSPFA(){initialize-single-source(G,s);//初始化源点s以及其他点initialize-queue(Q);//初始化队列enqueue(Q,s);//源点s入队while(!empty(Q)){u=dequeue(Q);//取出队首元素for(intv:adj[u]){//遍历每个相邻的节点tmp=d[v];relax(u,v);//松弛操作if((tmp!=d[v])and(!vinQ))//判断是否要入队enqueue(Q,v);//加入队尾}}}SPFA算法优点：•如其名，快速。期望的时间复杂度：O(ke)，其中k为所有顶点进队的平均次数，可以证明k一般小于等于4。有兴趣自己GOOGLE解决•写起来很方便缺点：在网格图上的效率很低，接近O（n^2）POJ3259-Wormholes题目大意：虫洞问题，现在有n个点，m条边，代表现在可以走的通路，比如从a到b和从b到a需要花费c时间，现在在地上出现了w个虫洞，虫洞的意义就是你从a到b花费的时间是-c(时间倒流,并且虫洞是单向的)，现在问你从某个点开始走，能否回到从前POJ3259-Wormholes提示：•SPFA其实是Bellman-ford算法的优化•而Bellman-ford可以用来判断一张图中是否存在负环•判断方法为：如果一个点被松弛了n次，那么图中就存在负环POJ3259-Wormholes题解：按照题目意思建图，判断图中是否存在负环，存在即可回到过去。把顶点集合V分成两组：（1）S：已求出的顶点的集合（初始时只含有源点V0）（2）V-S=T：尚未确定的顶点集合Dijkstra算法（仅适用于无负权边的情况）将T中顶点按递增的次序加入到S中，保证：（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点距离：从V0到此顶点的最短距离T中顶点距离：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度Dijkstra算法（仅适用于无负权边的情况）正确性证明算法流程Dijkstra算法Dijkstra算法使用了一个优先队列•INSERT(line3),每个结点一次•EXTRACT-MIN,每个结点一次•DECREASE-KEY(line8,在RELAX过程中),一共|E|次直接实现:O(V2)二项堆:O(ElogV)Fibonacci堆:O(E+VlogV)时间复杂度在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点