简单图论大学习

一、图的存储与遍历存储存图有多种方法都不复杂很容易实现。1.邻接矩阵直接使用二维数组graph[N][N]来存它虽然代码简单查询较快但是有时候很浪费空间而且数据范围有较大的限制并不常用。2.邻接表顾名思义邻接表就是每个节点值储存它直接可以到的其他节点。它的空间浪费比邻接矩阵小得多但是在找邻居的时候要遍历它的整个邻接表速度比邻接矩阵慢。3.链式前向星它其实就是用链表实现的邻接表。主体一个head[u]数组指向u的邻居存的地址。和一个struct Edge{int to,nxt};其中to指邻居编号nxt指下一个邻居的地址。具体代码如下点击查看代码4.Vector 直接存边这个方法是最常用的一个。直接用vectorEdge e[N]存边就可以了。struct Edge{int to,w;}; vectorEdge e[N]; ...遍历这里只介绍后两种常见方法的遍历方法前两种请读者自行探讨。链式前向星for(int ihead[u];~i;ie[i].nxt){ ... }Vector 直接存边for(auto it:e[u]){ ... }那么学会存图和遍历后来做一下几道模板题来练一练吧图的存储与出边的排序图的遍历二、拓扑排序首先你要了解拓扑在干什么给一个有向无环图(DAG)的所有节点排序————OI_WIKI那么拓扑排序之后就一定有每个顶点仅出现一次对于有向边A-B在序列中都必有A在B前。操作还是比较简单的1.找到入度为 0 的点并输出2.将所有与该点连接的边删除邻居入度减 13.重复步骤 1~2 ,直到没有任何点入度为 0 为止。注意有环图是不能进行拓扑排序的注意有环图是不能进行拓扑排序的注意有环图是不能进行拓扑排序的学了拓扑还是做一道模板题吧【模板】拓扑排序/家谱树三、欧拉路欧拉路其实就是一个简单的一笔画问题。它的定义是从图中某一个点出发遍历整个图图中每一条边通过且仅通过一次。欧拉回路就是起点和终点一样的欧拉路。一般关于欧拉路的问题基本上就是是否有欧拉路。打印欧拉路。通常是通过处理度来解决问题的。其中度数为奇数的为奇点度数为偶数的为偶点。1.存在性判断无向图若全是偶点存在欧拉回路显然。若有 2 个奇点存在欧拉路一个是起点另一个是终点。有向图和无向图差不多我们将一个点的度数记作入度减去出度。若所有点度数为零才会存在欧拉回路。若仅有一个点度数为 1一个点度数为 −1其余点的度数为零才存在欧拉路1 的为起点−1 的为终点。2.输出欧拉回路dfs 即可。习题Luogu:P7771 【模板】欧拉路径UVa:10054 The NecklacePOJ:1780 Code四、连通性问题关于连通性连通对于无向图的两点 , 若存在途径使得 0 且 则称 ,连通。连通图任意两点连通的无向图称为连通图。1.无向图一些定义割点对于 (,)∈,若删去 以及关联的边后图分裂为两个及以上不相连的子图则称 为 的割点。割边桥同上。首先我们要会求割点和割边很明显考虑 Tarjan 算法。求割点 【模板】割点割顶依赖一下两个主要的数组追溯值 定义为以 为根的搜索树上的点以及通过一条不在搜索树上的边能达到的结点中的最小编号。时间戳 定义为 按访问顺序的编号。void Tarjan(int u){ dfn[u]low[u]Time; int son0; for(auto v:e[u]){ if(dfn[v]){ low[u]min(low[u],dfn[v]); continue; } son; Tarjan(v); low[u]min(low[u],low[v]); if(low[v]dfn[u]u!root)cnt!is_cut[u],is_cut[u]1; } if(son2uroot)cnt!is_cut[u],is_cut[u]1; }求割边 【模板】割边桥和割点很像void tarjan(int u,int fa){ dfn[u]low[u]idx; for(int v:g[u]){ if(!dfn[v]){ tarjan(v,u); low[u]min(low[u], low[v]); if(dfn[u]low[v])add_bridge(u,v); } else if(v!fa)low[u]min(low[u],dfn[v]); } }习题Luogu:P3469 [POI 2008] BLO-BlockadeHDU:2460 NetworkLuogu:P1173 [NOI2016] 网格(hehe)割点和割边可以引出以下这些更为重要的定义点双连通图不存在割点的无向连通图称为点双连通图。边双连通图不存在割边的无向连通图称为边双连通图。点双连通分量一张图的极大点双连通子图称为点双连通分量v-DCC简称点双。边双连通分量一张图的极大边双连通子图称为边双连通分量e-DCC简称边双。但是实际上点双的定义是有歧义的而笔者采用的是接下来的这一个 OI_WIKI 版本的定义笔者以后的代码书写也参考接下来的版本。在一张连通的无向图中对于两个点 和 如果无论删去哪一个点不能删 和 自己都不能使它们不连通我们就说 和 点双连通。——OI_WIKI求边双 【模板】边双连通分量边双连通分量的求法很简单。并不比求割边的代码长太多依旧依赖一下两个主要的数组追溯值 时间戳 在求割边的时候我们已经对所有割边进行了标记。所以我们只要再次 DFS 不访问割边对每一各连通块进行标记则可以得到边双。边双缩点考虑一道例题POJ:3352 Road Construction这道题我们考虑缩点。我们先找出图中的边双将它们都看成一个个的点这样会形成一棵树。那么问题就变成了一棵树上增加多少条边可以将其变成一个边双。答案是叶子节点个数加一再除以二。原因求点双 【模板】点双连通分量点双联通分量的求法就没有边双那么简单了。虽然割边不隶属于任何边双但是割点是有可能隶属于多个点双的。所以此时我们就应该在跑 Tarjan 的过程中维护一个栈。当一个节点第一次被访问时入栈。当dfn[x]low[y]成立时不断弹栈直至 被弹出。而且刚刚弹掉的节点和 构成一个 v-DCC 。习题边双Luogu P2860 [USACO06JAN] Redundant Paths G点双Luogu:P3225 [HNOI2012] 矿场搭建POJ:2942 Knights of the Round TableLuogu:P5058 [ZJOI2004] 嗅探器2.有向图一些定义强连通若一张有向图的节点两两互相可达则称这张图是强连通的。强连通分量即极大的强连通子图称为SCC。首先我们要了解DFS 生成树。我们在一个有向图上选一点 从 开始遍历每一个点只遍历一次这样就会构成一棵树即 DFS 生成树。这棵树上会有这么几种边树边每次由⼀个已遍历的点到达未遍历的点就形成了⼀条树边。返祖边也叫做回边指向该节点的祖先。横叉边搜索时遇到⼀个已访问的节点但这个节点并不是该节点的祖先。前向边访问时遇到⼦树中的节点时形成的。举个栗子如图图中的红边即为返祖边紫边为横插边黄边为前向边其余为树边。求强连通分量有很多方法由于作者很菜本文只介绍 1 种。Tarjan 算法 【模板】强连通分量这个算法依旧是用栈来处理。DFS 流程很简单我们把当前节点 入栈。若 则开始弹栈直到 被弹出去。弹出去的点构成一个 SCC。代码void dfs(int u){ dfn[u]low[u]Dfn; in_stack[u]1; s[num]u; for(int ihead[u];i;ie[i].nxt){ int ve[i].to; if(!dfn[v]){ dfs(v); low[u]min(low[u],low[v]); } else{ if(in_stack[v])low[u]min(low[u],low[v]); } } if(low[u]dfn[u]){ cnta; ans[cnta].push_back(u); while(s[num]!u){ belong[s[num]]cnta; in_stack[s[num]]0; ans[cnta].push_back(s[num]); num--; } num--; belong[u]cnta; in_stack[u]0; } }习题Luogu:P3387 【模板】缩点Luogu:P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 GLuogu:P1726 上白泽慧音Luogu:P11676 [USACO25JAN] DFS Order PLuogu:P2863 [USACO06JAN] The Cow Prom SLuogu:P2515 [HAOI2010] 软件安装Luogu:P5163 WD与地图(请谨慎尝试。。。)HDU:3394 RailwayHDU:1530 Maximum Clique五、2-SAT定义给你 个布尔方程每个方程和两个变量相关比如 ∨表示 , 至少满足一个如果看不懂去学学集合然后判断是否有可行的方案显然是有多种的一般题目只要求出一种就行。讲个故事举一个栗子吧从前机房里面有Tri,tty,hzk三个 OIer他们对于考试 std 代码的码风有这样那样的要求Tri我要求代码当中满足下列条件之一1.代码不打空格。¬2.不用快读。¬3.大括号换行。tty我要求代码当中满足下列条件之一1.代码打空格。2.用快读。3.大括号不换行。¬hzk我要求代码当中满足下列条件之一1.代码打空格。2.用快读。¬3.大括号换行。于是我们可以把三位 OIer 的要求简化为一下这个式子(¬∨¬∨)∧(∨∨¬)∧(∨¬∨)。接下来我们只需要给 ,, 三个量赋布尔值就可以解决三位 OIer 的要求。2-SAT 就是每个 OIer 只有两个条件比如剔除 ,¬ 的存在就变成了(¬∨¬)∧(∨)∧(∨¬)。解决方法由于这个东西划分在了图论模块所以我们用图论解决。我们用强连通分量。对于每一个量 我们建两个点 ,¬。对于每一个 ∨ 的关系我们建两条边 ¬→∧¬→。你可以将其理解为若 假则 真若 假则 必真。然后按照箭头的方向建有向边即可。那么上面三位 OIer 的要求就可以画成以下这么个图同一强连通分量内的变量值一定是相等的。所以就有黄色的两个布尔值相等橙色的两个也相等。这样就可以解决问题了。但是如果 和 − 在同一个强连通分量里这个东东就无解很显然吧。。。对每个变量取所在强连通分量拓扑序较大的那个对应点就能构造出一组合法解。后面这个求出解的过程并不是那么显然的可能要动fei一yi动fei脑子具体的论证比较麻烦但学学也不是不行。想学点击查看这一篇 Luogu 的文章六、最短路为表述简便记 为点数 为边数起点为 终点为 。1.Floyd-Warshall 算法简称 Floyd代码比暴力还简单这就意味着效率很低但是这个算法可以解决多对多的最短路问题而接下来讲的很多都是只能一对多。设f[k][i][j]表示由若干个编号不超过 的节点中转后从 到 的最短路。那么易得转移方程为f[k][i][j]min(f[k-1][i][j],f[k-1][i][k]f[k-1][k][j])但是我们注意到第一维似乎并没用于是乎就变成了下面的代码【模板】Floyd代码for(int k1;kn;k) for(int i1;in;i) for(int j1;jn;j) f[i][j]min(f[i][j],f[i][k]f[k][j]);习题Luogu:P3416 [USACO16DEC] Moocast S(一道应该够了。。。)2.Dijkstra 算法Dijkstra 算法简称“迪杰斯特拉算法”在大多最短路问题中是最为常用和高效的是一种“一对多”的最短路算法即单源最短路径算法。它的思想可以概括为“Dijktra BFS 贪心”。学习它之前我们得了解一下松弛操作对于边 (,)松弛操作对应下面的式子()min((),()(,))。算法流程也不算太难比较好理解1. 定义两个集合已经确定了最短路的点集还未确定最短路的点集。2. 初始化 0其余 ∞。3. 在 集合中取一个 值最小的点 对其所有的出边进行松弛操作即对于 (,,)让 min(,)。4. 重复步骤 2 和 3直到 为空集。时间复杂度为 (2)。所以整个算法的流程就是和这张图差不多