图论相关算法

图论相关算法图的组织形式点、边（有向、无向）、权（容量、费用）矩阵、邻接表广度优先搜索通常用队列(先进先出,FIFO)实现

Q={起点s};标记s为己访问; while(Q非空){

取Q队首元素u;u出队;

所有与u相邻且未被访问的点进入队列;

标记u为已访问; }广度优先搜索由BFS得到的路径是原图中从S到T的边数最少的路径广度优先搜索树不唯一广度优先搜索双向广度优先搜索适用于已知出发点和结束点的BFS减少不必要的状态，搜索加速分析：搜索分支因子为r（每次可扩展状态数），需要k层，总状态数为rk，双向，前后各rk/2，总状态数2×rk/2哈希判重广度优先搜索无向图的连通分量无向图的连通分量是指，在连通分量里面的任意两个点之间都有路。易知从某个点v开始进行一次BFS，遍历到的所有点和v就在同一个连通分量内。广度优先搜索例题：无向单位边权值图，300000个点，编号1~n，列出所有中心点的编号中心点：到图中其他所有点的最长距离最小的点广度优先搜索解法：广搜，遍历原图，生成BFS树求树的直径，即树的最长路直径的中间节点（1个或者2个）为中心点广度优先搜索树的直径求法：选任意点开始BFS选BFS中深度最大的一个点为直径的一个端点从该端点出发再BFS最深的节点为另一端点，且深度为直径长度深度优先搜索相关概念递归实现结点颜色：白色（开始），灰色（发现），黑色（结束）一个结点总是从白色变为灰色，再变为黑色当所有点都变为黑色时，遍历结束时间戳(timestamp):d[u]表示一个结点开始被访问的时间，f[u]表示一个结点结束访问的时间深度优先搜索inttimestamp=0;dfs(intp){ timestamp=timestamp+1;

col[p]=GREY;

d[p]=timestamp; for(每个与p相邻的点i) if(col[i]==WHITE)dfs(i); timestamp=timestamp+1;

f[p]=timestamp;

col[p]=BLACK;}深度优先搜索每个顶点的d[u]<f[u]DFS中，v是u的子孙

d[u]<d[v]<f[v]<f[u]在搜索中发现u时可以从u出发沿一条完全由白色顶点组成的路径到达vm条边的连通图，DFS中顺序标号每条边为1~m，则任意与顶点u关联的所有边（边数>=2）的标号的GCD为1深度优先搜索割点与割边如果从图中删去某点和与该点相关联的边后，图不再连通，那么这个点叫做割点(cutpoint)。如果从图中删去某条边后，图不再连通，那么这条边叫做割边或桥(bridge)。深度优先搜索思路dep[u]记录节点u在DFS树中的深度low[u]记录节点u的子孙所能达到的最浅深度u为割点

u为根，且有大于1个儿子u不为根，且u的某个儿子v有low[v]>=dep[u](u,v)为割边

点u的某个儿子v，有low[v]>dep[u]深度优先搜索dfs(int

k,intfather,intdepth){

col[k]=GREY;dep[k]=depth;tot=0; for(每个与k相邻的点i){ if(i!=father&&col[i]==GREY)

low[k]=min(low[k],dep[i]); if(col[i]==WHITE){

dfs(i,k,depth+1); tot=tot+1;

low[k]=min(low[k],low[i]); if((k为根&&tot>1)||(k不为根&&low[i]>=dep[k])) k为割点; if(low[i]>dep[k])then(k,i)为割边; } }

col[k]=BLACK;}深度优先搜索例题：某公司拥有N台计算机，并将他们组成局域网，现在要求寻找该局域网中的关键点（即割点），并求出一旦处于该关键点的计算机崩溃，原局域网将会分成多少个子网深度优先搜索SampleInput125431323435012233445510122334466325510深度优先搜索SampleOutputNetwork#1:SPFnode3leaves2subnetsNetwork#2:NoSPFnodesNetwork#3:SPFnode2leaves2subnetsSPFnode3leaves2subnets深度优先搜索解法：求割点，计算删除该点使连通分量增加数对于DFS森林，对每个割点记录一个cnt值，若有一个儿子v使得low[v]>=dep[u]则使cnt[u]++，则有如下性质： 对每个非根割点，删除该节点会增加cnt[u]个连通分量对每个根割点，删除该点会使图的连通分量增加其儿子数-1个拓扑排序图的结点存在一个拓扑序：如果图中有边(u，v)，则u必定排在v的前面拓扑排序在有向无环图(DAG)上进行拓扑序列不一定唯一拓扑排序利用DFS，当节点u已经扩展完成，将标记颜色置为黑时，将u加入已排序列的顶部，搜索完成时，节点序列为拓扑序经过拓扑排序的顶点以与其完成时刻相反的顺序出现拓扑排序算法(1)计算每个点的入度，入度为0的点加入队列Q(2)从Q中取出一个点p，输出(3)所有与p相邻的点的入度减1。如果新得到了入度为0的点，则加入队列Q。(4)转步骤(2),直到所有点都输出完毕如果在执行过程中发现找不到入度为0的点,说明图中存在环拓扑排序13245678(不唯一)如何生成最小字典序的拓扑序列？可以使用最小堆维护当前入度为0的节点21348756强连通分量有向图的强连通分量（SCC）指：对于强连通分量里面的任意两个节点u和v，都存在u到v和v到u的路强连通分量思路：对原图G进行DFS，记录各点的结束时间，把原图G的所有边反向为GT，在GT以各点结束时间递减的顺序DFS，则每棵树都是一个强连通分量即第一遍DFS生成拓扑序，以拓扑序做第二次DFS强连通分量缩点操作生成一个新的有向图Gscc，将每个强连通分量作为新图的一个点，原图连通分量内部的边删除，连通分量之间的边保留新图必定有拓扑序，即不会出现有向环(DAG)Gscc称为原图的核心DAG强连通分量强连通分量例题：队长要向所有人通知某件事情，因为人数众多，他想出了一个省力的方法：他只通知队中的某些人，然后让这些人去通知所有他们认识的人，这些新被通知的人又去通知更多的人……直到最后队中的所有人都被通知到。给定队长通知每个人所需的花费，现在他想求出一种方案，使得花费最少，并且保证最终所有人都能被通知到。强连通分量SampleInput4330201040122123SampleOutput60强连通分量解题：同一个强连通分量里，只要有一人被通知即可缩点后得到的DAG中，如果一个点被通知，则它的所有后继结点都会被通知。故只需通知入度为0的点在入度为0的每个点所表示的连通分量中，通知花费最少的那个人，即为最优解强连通分量例题：给一个有向图G，添加最少的边数使得G中各点能两两互通（即每对点a和b，a能到b，b也能到a），求最少的边数强连通分量解题：对原图求强连通分量，形成新的DAG图Gscc对Gscc计算入度为0的点的个数为x对Gscc计算出度为0的点的个数为y答案为max(x,y)，即从出度为0的点向入度为0的点连max(x,y)条边欧拉路欧拉路：经过图中每条边恰好一次的路欧拉回路：起点和终点相同的欧拉路欧拉路无向图存在欧拉路的条件如果图连通，且所有的点都是偶数度，则有欧拉回路。如果图连通，且恰有两点是奇数度，则有欧拉路。且欧拉路的起止点为这两个奇数度点。对重边、自环的情况仍适用。欧拉路有向图存在欧拉路的条件如果图连通，且每个点的入度等于出度，则存在欧拉回路。如果图连通，且恰有一点u的出度比入度大1，另有一点v的出度比入度小1，其余的出度等于出度，则存在欧拉路，起点为u，终点为v。对重边、自环的情况仍适用。欧拉路套圈算法voidEuler(intstart){ for(inti=1;i<=E;i++){ if(!visit[i]&&from==start){

visit[i]=1;

Euler(to); path[++top]=i; } }}倒序path[]为欧拉路欧拉路例题：给定一组单词，问这些单词能否连成一串，使得前面一个单词的最后一个字母和后面一个单词的第一个字母相同。欧拉路SampleInput 6 aloha arachnid dog gopher rat tiger 3 oak maple elmSampleOutputaloha.arachnid.dog.gopher.rat.tiger

***欧拉路解法：先判断连通性每个单词相当于在首字母和尾字母之间连一条边得到一个最多26个点的有向图求欧拉路汉密尔顿路汉密尔顿路：经过图中每个点恰好一次的路汉密尔顿回路：起点和终点相同的汉密尔顿路常见方法：状态压缩DP汉密尔顿路对于点数较少的情况，可以用状态压缩的DP来做。比如用opt[mask][k]表示已经访问过mask表示的结点集合，并且最后位于点k的最优解。状态转移方程为：opt[mask][k]=min(opt[mask-{k}][i]+cost[i][k])i是所有与k相邻的点，mask-{k}指从mask除去k最短路径单源最短路径DijkstraBellman-FordSPFA任意两点间Floyd最短路径复杂度：Dijkstra:O(V2)或O(E+VlgV)Bellman-Ford:O(EV)Floyd:O(V3)SPFA:期望复杂度O(E)最短路径算法选择：编程复杂度：Bellman-Ford<Floyd<Dijkstra时间复杂度：Dijkstra<Bellman-Ford使用范围：有负权边需要使用Bellman-Ford如果是稀疏图，即使是求任意两点间最短路径，也最好选用堆优化的Dijkstra最短路径单源最短路径的核心松弛操作If(d[j]>d[i]+cost[i][j])d[j]=d[i]+cost[i][j];最短路径Dijkstra最短路径Bellman-Ford主体思想：对图中每条边做|V|-1次松弛操作，即可确定最短路径，当有负权值时，再对所有边做一次松弛操作，若dis值仍有变化则表明存在负环最短路径bool

Bellman(intn,intm){ /*bellman,returnfalsewhenthereisanagetivecircle*/

intu,v,w,i,j;

boolflag;

for(i=1;i<=n;i++){ flag=0;

for(j=0;j<m;j++){ u=edge[j].from,v=edge[j].to,w=edge[j].value;

if(dis[v]>dis[u]+w){

dis[v]=dis[u]+w; flag=1; } }

if(!flag)break;

if(i==n&&flag)returnfalse; } returntrue;}最短路径SPFA作为一种动态逼近的方法，是一种迭代模式，不仅仅可以用在最短路中，可以解决带环的DP问题最短路径

Q={s};d[s]=0; while(Q非空){

取队首元素u;u出队; for(与u相邻的点v){ if(d[v]>d[u]+cost[u][v]){

d[v]=d[u]+cost[u][v]; if(v不在队中)thenv入队; }//若某个点入队次数达到|v|说明有负环

} }可以用循环队列实现，队列中元素个数不超过|V|最短路径例题：最小平均环路图的每条边有两个权值a和b，在图上找一个环，使得对于环上的所有边（∑a/∑b）最小最短路径解法：二分答案设答案为k，使各边的边权值为k×b[i]–a[i]，在新图中用Bellman-Ford或者SPFA判断是否含有负环若有负环，则k×b[i]–a[i]<0即k<∑a/∑b，即可再扩大k最短路径例题：有向图，N个节点编号1~N，M条边，权值均为正，现给定k个可替换条件，可以将M条件中的k条边权值替换为0，求在至多替换k条边的情况下，节点1到节点N的最短路径最短路径解法：多层图建立一个多层图，有k+1层，每层都为原图，只有相邻层之间可建边，且相邻层间只能建立由低层到高层的边，若图中有边（i，j）权值为p，则建立下层节点i到上层节点j的权值为0的边第0层（最下一层）节点1到第k层（最上一层）节点N的最短路径为所求差分约束差分约束系统是一组形如x-y<=C的不等式

x1–x2<=0 x1–x5<=-1 x2–x5<=1 x3–x1<=5 x4–x1<=4 x4–x3<=-1 x5–x3<=-3 x5–x4<=-3差分约束松驰操作if(d[v]>d[u]+cost) thend[v]=d[u]+cost;在最短路算法执行完毕后，对所有的边(u,v)都有

d[v]<=d[u]+cost

变形得

d[v]–d[u]<=cost;容易看出，上式即为差分约束系统的标准形式。差分约束解不等式组问题转化为图论问题：不等式组中的每个变量作为图中的一个点对于每个不等式Xi–Xj<=k，在图中加入一条边(j,i)，边权值为k为了执行最短路算法，我们加入一个源点V0，并使V0到每个点有一条权值为0的边。以V0为起点，执行Bellman-Ford算法，算法结束时各个点的d[]值即为一个可行解。如果算法检测到负环，说明原不等式组无解差分约束若题目中为>，<可以通过+1，-1来转变成为>=，=<当某些点有明显的<=性质时，可以计算和值，使得Si–Si-1产生<=形式，构造求解实际问题中有些不等关系较隐蔽，注意不要遗漏如果把所有的Xi同时加一个值，不等式组仍然成立生成树最小生成树：Prim(O(ElogV))Kruskal(O(ElogE)+O(alpha*E))算法的选择：从图的稀疏程度考虑从问题对边的限制考虑最小生成树Prim算法：(1)任意选定一点s，设集合S={s}(2)从不在集合S的点中选出一个点j使得其与S内的某点i的距离最短，则(i，j)就是生成树上的一条边，同时将j点加入S(3)转到(2)继续进行，直至所有点都己加入S集合。最小生成树50461321025142422161850461210251422161231228最小生成树Kruskal算法：将边按权值从小到大排序后逐个判断，如果当前的边加入以后不会产生环，那么就把当前边作为生成树的一条边。最终得到的结果就是最小生成树。并查集最小生成树50461321025142416181250461321025141222222816生成树其他生成树问题：最小树形图有向图的最小生成树次小生成树假设T为G的最小生成树集合，并设T’为T的最小生成树，那么次小生成树是集合T’-T中权值最小的生成树生成树其他生成树问题：最小度限制生成树对于一个加权的无向图，存在一些满足下面性质的生成树：某个特殊的结点的度等于一个指定的数值。最小度限制生成树就是满足此性质且权值和最小的一棵生成树最优比率生成树已知一个完全图，每条边有两个参数（dis和c），求一棵生成树，使(∑xi×ci)/(∑xi×disi)最小，其中xi当第i条边包含在生成树中时为1，否则为0二分图所有点可以分成两个集合X和Y，使得所有的边的一端在X集合，另一端在Y集合二分图的充要条件：图中不含奇环二分图的判定：用BFS或DFS对点进行黑白染色，检查是否出现矛盾二分图最大匹配二分图的最大匹配指找到尽可能多的边，使得它们之间没有相同的端点二分图最大匹配交错路对于一个匹配M，如果能找到一条奇数长度的路，使得路的第一、三、五……边不属于M，而第二、四、六……边属于M，那么这条路叫做交错路。交错路可以“增广”，即通过适当修改得到更长的路。一个匹配是最大匹配当且仅当不能再找到交错链为止二分图最大匹配交错路增广示例(1-2-3-4-5-6-7-8)12345678二分图最大匹配匈牙利算法一个匹配为最大匹配

匹配中不存在交错路利用BFS或者DFS实现寻找交错路以每个节点为起点找一次增广路即可求得最大匹配，寻找增广路的复杂度为O（E），总的复杂度为O（VE）二分图最大匹配bool

Bipartite_Dfs(intu){

for(inti=0;i<adj[u].size();i++){

if(!mark[adj[u][i]]){

mark[adj[u][i]]=1;

intt=match[adj[u][i]];

match[adj[u][i]]=u;

if(!t||Bipartite_Dfs(t))returntrue;

match[adj[u][i]]=t; } } returnfalse;}------------------------------------------------------------------------------------------------Clear(match);for(i=1;i<=n;i++){

Clear(mark);

if(Bipartite_Dfs(i))ans++;}二分图最大匹配可以在调用DFS增广之前利用贪心的策略做初始的基本匹配，若贪心解接近最终解则可提高效率常见模型：非攻击车：行列分为两部分，允许放车的格子连边骨牌覆盖：染色，相邻黑白格连边二分图最大匹配例题：给一个N×M的格子，其中‘X’表示不能走，‘E’表示出口，‘.’表示有一个人。所有人只能上下左右行走，且所有人都要选择一个出口走出去，但每个时刻每个出口只能走出去一个人，问是否所有人都能出去，如果是，求都能出去的最小时间二分图最大匹配解答：二分答案+最大匹配验证从每个‘E’出口BFS遍历每个‘.’人，计算编号为i的人到编号为j的出口的最短距离（也是最短时间），记录于cnt[i][j]二分最后时间k，将原总共d个出口拆成k×d个出口，若cnt[i][j]<=k，则i可以连边指向编号为j的出口拆成时间从cnt[i][j]到k的点二分图最大匹配解答：求二分图最大匹配若匹配值==总人数，right=mid–1否则，left=mid+1另外需要注意本身无法到达出口的情况二分图最小点覆盖点覆盖：求出一个点集，使得图中的所有边都至少有一个端点在该点集内。最小点覆盖：节点数最少的点覆盖二分图的最小点覆盖=二分图的最大匹配二分图最小点覆盖构造最小点覆盖求得最大匹配M后，图中已经不存在交错路。从右边未匹配的点开始，以寻找交错路的方式扩展节点，并标记路过的节点。取右边未标记的节点，左边标记的节点，则构成一组最小覆盖二分图最小点覆盖二分图最小点覆盖例题：有两台机器A，B及N个任务。每台机器有M种不同的模式，对每个任务i给定a[i]和b[i]，表示如果该任务在A上执行，需要设置模式为a[i]，如果在B上执行，需要模式为b[i]。任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次要求合理分配任务并合理安排顺序，使得机器重启次数最少二分图最小点覆盖SampleInput5510011112213314421522623724833943SampleOutput3二分图最小点覆盖解法：把两台机器的工作模式看成顶点，如果一个工作在第一台机器上用模式i完成，在第二台机器上用模式j完成，那么就用一条边把这两个顶点连接起来，这样对于所有的边，他们都有一个顶点是机器1的工作模式，另一顶点是机器2的工作模式，于是构成的图是个二分图。用最少的模式完成所有的工作，就相当于在图中用最少的点覆盖所有的边二分图最大独立集独立集：图的顶点集的子集，其中任意两个点在图中不相邻最大独立集：节点数最多的独立集二分图的最大独立集=顶点数–最大匹配数二分图最大独立集黑色节点为最大独立集二分图最大独立集理解：方式1：在总的点集中，去掉最少的点，使得剩下的点相互之间没有边，而用最少的点去覆盖所有的边就是最小点覆盖二分图的最大独立集=图的点数-最小点覆盖数方式2：在总的点集中，把最大匹配的两个端点都去掉，则剩余点构成一个独立集，再取最大匹配边的一个端点加入，仍为独立集二分图的最大独立集=图的点数-最大匹配数二分图最大独立集例题：学校里有一些男生和女生，其中某些人之间是恋爱关系。现在要求找出一个最大的集合，使得里面的任意两个人都没有关系二分图最大独立集SampleInput170:(3)4561:(2)462:(0)3:(0)4:(2)015:(1)06:(2)01SampleOutput15

SampleInput230:(2)121:(1)02:(1)0SampleOutput22二分图最大独立集解法：输入数据里面没有指明性别。必须先进行染色，区分出X集和Y集求二分图最大独立集二分图最小路径覆盖最小路径覆盖：用最少的不相交路径覆盖有向无环图的所有顶点把原图中的每个点i拆为两个，分别属于X集和Y集。对于原图中的有向边(i，j)，在新图中添加边(Xi，Yj)最小路径覆盖数=原图顶点数–新图最大匹配数二分图最小路径覆盖解释：原图的路径覆盖和新图的匹配间有对应关系：每条覆盖边都是匹配中的一条边，且只有路径的最后一个点没有被匹配上。路径要求不能相交，恰好对应于匹配中两匹配边不能有公共端点。二分图最小路径覆盖解释：于是求最大匹配后，不能被匹配上的点，即是路径的最后一个点。有多少个不能被匹配的点，就有多少条路径存在。路径数=原点数－匹配边数。因此我们使匹配边数最大，即是使路径数最小。二分图最小路径覆盖例题：某汽车运输公司需要安排他们的运送线路，已知从某地点X，坐标为（a，b），到某地点Y，坐标为（c，d）需要的时间为|a-c|+|b-d|分钟，现给出所有运送安排，求使用最少的车来完成该运送安排二分图最小路径覆盖SampleInput2208:00101191608:079161011208:00101191608:069161011SampleOutput12二分图最小路径覆盖解法：每条计划作为一个节点，令car[i].start=t1*60+t2;car[i].end=car[i].start+|car[i].a-car[i].c|+|car[i].b-car[i].d|;

建边若car[j].start-car[i].end>|car[i].c-car[j].a|+|car[i].d-car[j].b|则建立i到j的边答案=顶点数–最大匹配数二分图最优匹配二分图最优匹配（带权最大匹配）：二分图的每条边上带有权值，求一个匹配使得匹配边上的权值和最大。实际问题：每个工人操作不同机器的效率不同，如何合理分配机器，使得效率总和达到最佳？每对男女之间的好感度不同，如何配对使得总的好感度最高？二分图最优匹配KM算法：基本概念：可行顶标与相等子图可行顶标是一个关于节点的函数L且对于每条边(x，y)满足L(x)+L(y)>=w(x,y)相等子图是指只包含L(x)+L(y)=w(x,y)的边的子图。定理：如果相等子图有完备匹配（包含所有点的匹配），则该匹配是最大权匹配。二分图最优匹配KM算法的关键：通过适当地修改可行顶标从而使相等子图有完备匹配，于是就可以得到最优匹配。设顶点Xi的顶标为a[i]，顶点Yi的顶标为b[i]。初始时，a[i]为与Xi相关联的边的最大权值，b[j]=0，保证a[i]+b[j]>=w(i,j)成立。二分图最优匹配若相等子图中不包含完备匹配时，就适当修改顶标以扩大相等子图，直到找到完备匹配为止当从Xi寻找交错路失败后，得到一棵交错树，它的所有叶子节点都是X节点，取所有左侧点i在树中而右侧j不在树中的边(i,j)，计算d=min{a[i]+b[j]-w[i][j]}。交错树中所有左侧点顶标-d，右侧点顶标+d…二分图最优匹配对于图中所有的边(i,j)，可以看到若i和j都不在交错树中，边(i,j)仍不属于相等子图若i和j都在交错树中，边(i,j)仍然属于相等子图若i在交错树中，j不在交错树中，a[i]+b[j]减少，边(i,j)有可能加入到相等子图中每次更新顶标，至少有一条边新加入相等子图，匹配也就可能继续扩大二分图最优匹配例题：在一片花园中，有人（’H’），有屋（’m’），有空地（’.’），且人和屋子的数量一致，每个屋子只能住一个人，每个人只能上下左右四个方向行走，现在给你花园的现状，求使每个人都能进到屋子里的最小步数二分图最优匹配SampleInput

55HH..m...............mm..H78...H.......H.......H....mmmHmmmm...H.......H.......H....SampleOutput

1028二分图最优匹配解法：初始算出每个人到每个房子所需要的步数，X集为N个人，Y集为N个房子，若人i到房子j需要步数为c，则人i和房子j之间连边，权值为-c由于房子数和人数一致，可以使用KM算法求解求出的结果值再取负即为答案二分图最优匹配注意在使用KM算法时需要注意X集和Y集的节点数是否一致，否则需要补点补边算最大值时可以令边权为正，反之算最小值时可以令边权为负，最后结果再取负网络流网络流基本概念：源点(source,常记为s)汇点(sink,常记为t)容量(capacity,常用c(x,y)表示)流(flow,常用f(x,y)表示)网络流容量限制条件：对于所有边，有f(x,y)<=c(x,y)流量平衡条件：对于所有非s和t的点u，有∑v∈Vf(u,v)=0网络流问题：在满足上述两个限制条件的基础上，找到合适的f值，使得∑v∈Vf(s,v)最大易得∑v∈Vf(s,v)=∑v∈Vf(v,t)=网络流值F网络流网络流增广路算法涉及概念：容量：“不存在”的边容量为0流量：f(u,v)=-f(v,u)残量网络(residualnetworks)R(u,v)=c(u,v)–f(u,v)容量必为正，残量网络必为正，流量可正可负网络流可增广路(augmentingpath)：在残量网络中的一条s-t路我们可以沿着可增广路进行增广，从而扩大流量，而不破坏限制条件。当不能再找到可增广路时，我们就得到了一个网络流。网络流注意：负流量的意义R(x,y)=c(x,y)–f(x,y)如果从y到x的流量为正，则从x到y的流量为负。负流量对应反向的正的残量边，意味着我们可以把这个流“退回”一部分。网络