图论1

· · 算法·理论

一、图的基础知识

是一种抽象的图形，由 点 和 边 构成。 其中，边可以有方向也可以没有，

对于图来讲，边有向为 有向图 ，无向为 无向图 。

那么其实无向图可以看作是每两个点间有方向不同的重边的有向图 ，换而言之，无向图是特殊的有向图 。

边一般连接两个点，但也可以连接同一个点，也就形成了 自环 ，两条无向边也可以连接相同的两个点，即 重边 。

连接图 ： 指图中任意一点都有路径可以同向图中其他的任意一点，但不一定点两两相连。当点的数量为 n 时，边的最小数量为 n-1.

完全图 ： 指图中任意两点有直接的边相连，当点的数量为 n 时，无向图边的数量为 \Large\frac{n\times{(n-1)}}{2}；有向图的数量为 n\cdot (n-1) 。

简单图 ： 指无重边和自环的图。

二分图

拓扑次序( Topological Order )的序列，简称拓扑序列，是一种线性序列，只存在于有向图中。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y) ， x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

由定义可知，若一个有向图存在环，则此图一定不存在拓扑序列；反之亦然，若一个图存在拓扑序列，则此图一定不存在环。同时可以证明，一个有向无环图一定存在拓扑序列，因此，有向无环图也被称为拓扑图。

根据下述定义，则有性质定理：

一个DAG至少有一个出度为 0 的点和一个入度为 0 的点。

度数一般指点所连的边的数量，在无向图中，“点的度数”即指点所连边的数量；在有向图中，点的度数分为 入度 和 出度，入度指当前点作为终点的边的数量，出度指当前点作为起点的边的数量。

树也是一种图形，对于图来讲，一个简单无向无环的连接图就是树，所以说

树是特殊的图。

二、图的程序储存

一般来讲，有两种储存方式，邻接矩阵和邻接表。

邻接矩阵是一种时间复杂度相对较低的储存方式，是相对于边来储存。

具体为将二维数组的两个下标看做一条边的两端，如 a[i][j] 表示一条从 i 点到 j 点的边的存在或权重。

这种方式是不常用的，因为其空间复杂度为 O(n^2) ，其次，邻接矩阵无法储存有重边的图。

邻接矩阵多数情况下适用于无重边的稠密图（边的数量大于点的数量的二次方的图）。

邻接表是一种空间复杂度相对较低的储存方式，是相对于点来储存。

具体为使用vector数组来储存，第 i 个vector储存 i 点可以到达的点的编号的集合，若边有权重，可采用结构体vector。当然，数组模拟vector也是可以的。

这种方式相对更常用，尽管时间复杂度稍微高一点，但不起决定性影响，程序总体的时间复杂度仍取决于算法。

邻接表用于稀疏图。

三、图的连通

当图为无向图时：

已知 G 为无向图，若 \forall u,v ，满足 u 到 v 存在路径，则称 G 为连通图。

当图为有向图时，情况会十分复杂。有向图的连通性分为：强连通、单向连通、弱连通。

强连通：任意两点u,v都有简单路径可以相互到达，即对于 u 到 v 和 v 到 u 都有简单路径。

单向连通：任意两点u,v都有简单路径可以单向到达，即对于 u 到 v 或 v 到 u 有简单路径。

弱连通：把有向图的所有边改为无向边，此时称为原图的基图。若基图为连通图，则称原图为弱连通图。

自然，会有强连通分量指有向图中的一部分强连通，特别地，强连通图只有一个强连通分量，即其本身。

更多内容在《更详细严谨的定义与解释》。

四、最短路：

一般情况下，难点在识别出题型和建图方式，所以所谓的算法不难。

那么常用的算法在这里：《最短路》。

算法选择

在上面的文章里也说了，这些算法没用优劣之分，只是其思想不同、做法不同导致了时间复杂度不同，在做题的过程中，要根据实际情况选择可行的算法，表面上看起来十分符合题意的算法不一定是正解。

以P1828 [USACO3.2] 香甜的黄油 Sweet Butter为例，

这道题表面上是多源多汇的，我们可能需要求出任意两点之间的最短距离，好像适合 \text{floyd} 算法，但实际上可以发现 1\leq N \leq 500，即最坏情况下时间复杂度可以飙到 O(n^3)\approx O(1.25\times 10^8)，无限接近于超时。所以不能用 \text{floyd} 算法。

那么依次考虑其他算法：

  1. 朴素\text{dijkstra} 算法：O(n\cdot n^2) ，超时。
  2. 堆优化\text{dijkstra} 算法：O(n\cdot (m+n)\cdot \log n)\approx 8.741639\times 10^6，可过。

一般不考虑 \text{Bellman ford} 算法。显然，选择堆优化\text{dijkstra} 算法最稳。

建图

以P5767 [NOI1997] 最优乘车为例，显然我们真正需要的图肯定跟题目描述的不一样（以样例为例，下图1）

但是我们可以这么想，对于一条路线上的任意一点 u 来讲，可以到达同一条路线上后面的任意一点 v ，此时坐着同一辆车，我们假设这样连一条边权为 1 的边，即从一个点到任何一个只用坐一辆车就能到达的点，如下图2。

可以自行模拟，这样下来，答案便是 上图最短距离-1。

那么一切都好说了。

离奇的事：经过测试，该题使用 \text{dijkstra}、\text{heap}-\text{dijkstra}都可行，甚至朴素的 BFS 也行，但问题在于 BFS 的时间复杂度、空间复杂度、代码码力要优于前两者，不知具体原因。

当然，有可能是数据问题。

一种可能的原因是，转化后的图边权只为 1 （BFS 显然具有可行性），这导致了前两者的负优化。

算法混用

以AcWing 340.通信线路为例。

看这里：题解。

再看看这个：AcWing 342.道路与航线。

然后：题解。

分层图||拆点

其实没有那么复杂，联系DP，分层就是增设不同的状态维度，状态即为点，状态之间的转移便是边。

以luogu P4011 孤岛营救问题为例，别看其他解释用立体模型来解释分层图多么多么复杂，他不过是一个多维度状态转移，具体地讲，在每个点上，我可以拿起钥匙，也可以不拿起钥匙，这取决于最短距离，即dis[i][00001(2)]=min(dis[i][00001(2)],dis[i][00000(2)]);其中，i表示点，00001、00000表示二进制压缩下的钥匙表示。也要注意，不应当忘了给st状态加维。

样例代码：代码1。

大佬的说法。

最短路计数

方式就是边找最短路边找最短路数：在每个点更新其相连的点的最短距离的同时，比较两种方案，相同时把cnt加一。

对比《背包DP·7.背包问题求最优方案数》。

有意思的一点是，BFS 和 \texttt{dijkstra} 算法都可以边找最短路边找最短路数，而 \texttt{spfa} 算法不行。

这是因为“边找最短路边找最短路数”需要保证更新顺序须是按照最短路建立的一颗树，这里我们称为最短路树，此时这棵树是拓扑序之一，当按此序更新时，任意点的后效性才会被消除，那么此时统计最短路数才是正确的。

然而，可以发现，BFS 和 \texttt{dijkstra} 都满足一颗最短路树（在使用正确的情况下），但是，\texttt{spfa} 的点可以反复入队，这意味着前面的点具有后效性，不满足最短路树。

但是 \texttt{spfa} 算法还是可以用的，我们先把最短距离求出来，同时记录路径，然后按照路径经行任意搜索（或者DP也可以，主要看理解）统计路径数即可。

说起后效性，当然离不开DP，我们知道DP只有保证无后效性时才能使用，然而其实拓扑序列便是一个原图内不具备后效性的点序列构成的新图，即无回路。

当然，DP和图论是紧密相连的，但是又是相互区别，有时只是一点点相距，有时又站在两个极端，这一点本身就很难说清。

但是这启示我们，当图论遇到问题时，可以借鉴DP，反之亦然。

那么这里有一道练手的废物：luogu P1144 最短路计数。

次短路 AcWing 383.观光

难度是不是一下就上去了？（指你从来不知道这道题）

是的，这是次短路，但是还是很简单，因为只是第二小。

注意题意转化，那么这里有《蒟蒻作者的题解与解析》。

\texttt{floyd} 算法专题

这里讲讲一些 \texttt{floyd} 在题中被当成工具的题目。话不多说，看看例题。

例题1：luogu P1522 [USACO2.4] 牛的旅行 Cow Tours。

其实题目不难，我们需要把各个连通块的直径算出来，此时可以用 \texttt{floyd} 来枚举得到直径，之后枚举连通块的连接，即选择两个互不相通的点来连接，然后求新连通块的直径。

具体地，为了简化代码和思路，我们需要准备并查集和 \texttt{floyd} ，当得到所以点之间的dis[i][j]时，再枚举每个点可以到达相通点的最短距离的最大值maxd[i]，同时，用并查集来合并相连的点。然后统计每个并查集的具体点，针对每个连通块求直径（即枚举最大的maxd[i]），然后在考虑连边。
连边之后，新连通块的直径应该是以下数据的最大值（设连接gru[find(i)]和gru[find(j)]连通块的点i和j）：

  1. gru_d[find(i)]。
  2. gru_d[find(j)]。
  3. maxd[i]+get_dist(i,j)+maxd[j]。

为什么呢？3.很好想，但为什么有1.2.呢？举个例子：

假如说现连接 1 和 6 ，而他们的距离是 1 ,从图上不难看出，连接后直径应该是 105 (从 8 到 4 )，其直径是左边连通块的直径，而非 101 （从 8 到 3）。
最后，烦人的输入与精度问题，结束。

注意，AcWing 上也有着道题，但是因为翻译不同，所以答案不同，上述解适应lugu。证据。

样例代码：代码2。

显然，由于 \texttt{floyd} 算法枚举了任意两点，所以利用 \texttt{floyd} 的外套，我们便可以在 O(n^3) 的时间内对一个图做传递闭包。

void floyd(){
    for(int k=1;k<=n;k++)
        for(int j=1;j<=n;j++)
            for(int i=1;i<=n;i++)
                d[j][i]|=d[j][k]&&d[k][i];//注意这里是"或"（|）
}

这有什么用呢？（蒟蒻作者认为作用不大）如这道P1347 排序。

一点直接的想法是，在每次加入关系时，都做一次传递闭包，利用传递闭包的结果判断关系是否矛盾或确定。

具体地讲，设d[i][j]（bool）表示节点i和j的关系（把每个变量当作节点，大小关系当作边），即i>j时为true，反之为false，当存在矛盾时，必存在d[i][i]=true（i>j,j>k,k>i即为矛盾，在传递闭包时，就会d[i][k]|=d[i][j]&&d[j][k]、d[k][i]=1、d[i][i]|=d[i][k]&&d[k][i]）;同时，当所有关系确定时，那么任意的i、j都满足d[i][j] || d[j][i] == true 。
最后输出时，每次找出最小的一个节点（变量），那么这个节点i满足任意j都d[i][j]==false。

最后时间复杂度 O(m\cdot n^3)

\scriptsize\text{另提一点，这道题有}O(m\cdot n^2)\text{的做法，即}\textbf{量增算法}\text{，那便是对于每加上一条边（增加一个关系）只围绕} \scriptsize\text{这新加的边去更新其他点的连接关系。} \scriptsize\text{具体地讲，对于新加A>B的关系，枚举X、Y,d[X][B]=d[X][A],d[B][X]=d[A][X],d[X][Y]=d[X][A]\&\&d[B][Y]} \scriptsize\text{这样的时间复杂度 }O(m\cdot n^2)。

样例代码：代码3。

例题3：luogu P6175 无向图的最小环问题。

最小环，顾名思义，就是一个图中边权之和最小的环。

在这里，\texttt{floyd} 算法展现出了巨大的思路优势——暴力枚举了每两个点，用以下模板为例：

void floyd(){
    memcpy(d,g,sizeof d);
    for(int k=1;k<=n;k++)
        for(int j=1;j<=n;j++)
            for(int i=1;i<=n;i++)
                d[j][i]=min(d[j][k]+d[k][i],d[j][i]);
}

其中，在每个k 的循环内部，d[i][j]表示在当前k下，从i走到j且只经过编号不超过k或说编号属于1到k-1的部分点的路径（或者没有），倘若此时存在边d[j][k]和d[k][i],那么显然，这里出现了一个环，那么对于 \texttt{floyd} 来讲，图中任意环都会以上述方式在循环中遍历，此时不断比较即可。

int g[N][N];//邻接矩阵 
int d[N][N];//Floyd数组 
int ans=inf;
void floyd(){
    memset(d,0x3f,sizeof d);
    for(int i=0;i<N;i++)    d[i][i]=0;
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i!=j && j!=k && i!=k)//不加爆 0  
                    ans=min(ans,d[i][j]+g[i][k]+g[k][j]);
                //i连k，k连j，存在由1~k-1的节点组成的路径d[i][j] 
                d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
            }
        }
    }
}

有个问题：为什么不是ans=min(ans,d[i][k]+d[k][j]+g[i][j]);?

一种解释是，此时d[i][k]与d[k][j]不一定是正解，即有后效性；但是还有另一种解释，即方便输出环。

好，该*的问题来了——如何把这个环输出？

回归 \texttt{floyd} 本身，我们发现，在每次更新时，d[i][j]保证了（存在解时）一条i经过k到j的路径，并且这条路径是用d[i][k]和d[k][j]来更新的，对于这两个范围更小的路径来讲，他们在更新的同时也对应一个k，结合DP的方案记录方式，这启示我们在更新时记录k，并在更新最小环时递归求解。

代码样例：代码4。

倍增类\texttt{floyd}的用法。

例题：P2886 [USACO07NOV] Cow Relays G。

题解：《蒟蒻作者的文章》。

五、最小生成树

最小生成树是有关图的连通性的问题之一，那么基础的使用算法在这里：《最小生成树》。

那么，先来到题练练手：P2330 [SCOI2005] 繁忙的都市。
考察对算法的理解，过于简单，不做解释。

然后双倍经验：P1547 [USACO05MAR] Out of Hay S。

正文开始。

最小生成树的一般考法——算法混用

性质包括：

  1. 任意一棵最小生成树一定\small\textbf{\color{orange}可以}包含无向图中权值最小的边。

  2. 给定一张无向图 G=(V,E),n=|V|,m=|E| 。从 E 中选出 k(k\leq n-1) 条边构成 G 的一个生成森林。若再从剩余的 m-k 条边中选 n-(k+1) 条边添加到森林中，使其成为 G 的生成树，并且选出的边的权值之和最小。则该生成树一定\small\textbf{\color{orange}可以}包含 m-k 条边中连接生成森林的两个不连通节点的权值最小的边。

上被标\small\textbf{\color{orange}橙}的“可以”是因为，最小边不一定只有一条，但一定不会全部包含，因该只有其中一条在解中。

过于简单，不解释。

练习 : luogu P1550 [USACO08OCT] Watering Hole G。

例题：P1991 无线通讯网。

首先，这道题用到了性质2，那么提示到这儿，已经可以做了。

代码样例：代码5。

例题：AcWing 346.走廊泼水节。

那么这道题其实没有那么难。
我们在 \text{kruskal} 算法中，所有边都是降序遍历的，为了保证所给最小生成树一定为解，我们先保证连通块内为完全图，那么在对所给边做 \text{kruskal} ，将两个连通块连接起来使之成为完全图时，连通块间连的构造边必大于所给边。

证明：我们设两个连通块为 G_1 和 G_2，所给的边（也是两个连通块以前与现在相连最短的边）为 e ,当构造的边 e' 满足 e'\leq e 时，在所有的边中，由于 G_1 和 G_2 的完全连同，所以必存在一个环并且包含 e',e，此时在最小生成树中用 e' 取代 e ，那么将得到一个等效的最小生成树或更优的最小生成树，并且也不满足 \text{kruskal} 的边的遍历顺序。

显然的，对于构造的边，只需要比所给边大 1 即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 6010;
int n;
struct node{
    int x,y,z;
    bool operator<(const node&o)const {
        return z<o.z;
    }
}eg[N];

int f[N],siz[N];//points' father,unions' number
int ans;

int find(int x){
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)   f[i]=i,siz[i]=1;
        for(int i=1;i<n;i++)
            scanf("%d%d%d",&eg[i].x,&eg[i].y,&eg[i].z);
        sort(eg+1,eg+n);
        ans=0;
        for(int i=1;i<n;i++){
            int x=find(eg[i].x),y=find(eg[i].y);
            if(x!=y){
                ans+=(siz[x]*siz[y]-1)*(eg[i].z+1);//build the lines
                siz[y]+=siz[x];//unions' renew
                f[x]=y;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

次小生成树

次小生成树的一般定义是：对于给定的带边权的图，把图的所有生成树按权值从小到大排序，第二小的称为次小生成树。

同时，有的时候，题目会把次小生成树定义为排位第二的，即有可能在权值上与最小生成树相同。

一般地，把前者称为严格次小生成树，后者为非严格次小生成树。

次小生成树的一般求法如下：

  1. 先求最小生成树，再枚举删去最小生成树中的边求解。一般先用 \text{kruskal} 求最小生成树，然后再依次枚举，即依照原序列做无排序的 \text{kruskal} ，时间复杂度在 O(m\cdot \log m+n\cdot m) 。

这种做法一般难以求得严格次小生成树，所以不那么常用。

  1. 先求最小生成树，然后依次枚举非树边（在最小生成树中的边称为树边，其余者称为非树边），然后将该边加入到树中，同时从树中去掉一条边，使得最终的图仍是一棵树。则一定可以求出自小生成树。

方法二的性质：设 T 为图 G 的一棵生成树，对于非树边 a 和树边 b ,插入 a 、删去 b 的操作记为 (+a,-b) 。如果 T+a-b 之后，仍然是一棵生成树，成 (+a,-b) 为 T 的一个可行变换。称由 T 经行的依次可行变换所得到的新的生成树集合称为 T 的领集。
则有定理：次小生成树一定在最小生成树的领集中。
翻译一下就是，次小生成树与最小生成树一定只有一条边不同。

证明略。

非严格次小生成树求法：

1.正常跑一遍 \text{kruskal} 算法得到最小生成树的边权和 W。
2.遍历每个未选进生成树中的边，假设这个边的端节点是 i 和 j，边权为 w'，那么求出生成树中 i 与 j 相连的权值最大的边（假设边权为 w）。用这条未选边去替换已有边，新生成树的权值就是 W+w'-w。
3.重复如上操作，不断对 W+w'-w 取最小值。最终得到的最小值就是答案。

严格次小生成树求法：

1.得到最小生成树的权值 W 。
2.遍历每个非树边，若变得权值 w' 严格大于生成树中该两点最大边权 w_1 ，则直接替换；否则，若 w'=w_1 且新取边的边权严格大于生成树中该两点的严格次大边权 w_2 ，就用 w_2 经行计算。这两种情况得到的生成树权值分别为 W+w'-w_1 和 W+w'-w_2 。
3.重复上述操作，取最小值。

例题：AcWing 1148.秘密的牛奶运输。

样例代码：代码6。

然而，实际上上面的代码虽然可以过，但不是正解，并且无法通过大数据，正解涉及 \textbf{LCA} 、倍增等，这里只作一个思路引领，那么正解在《图论2·LCA-最近公共祖先》。

六、欧拉回路与欧拉路径

8世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。后来大数学家欧拉把它转化成一个几何问题——一笔画问题。他不仅解决了此问题，且给出了连通图可以一笔画的充要条件。

——《七桥问题_百度百科》

  1. 欧拉回路：给定一张图，若存在一条从节点 S 出发的路径，恰好不重不漏地经过每条边一次（可以重复经过图中的节点），最终回到起点 S ，则称该路径为欧拉回路。存在欧拉回路的无向图称为欧拉图。
  2. 欧拉路径：给定一张图，若存在一条从节点 S 到节点 T 的路径，恰好不重不漏地经过每条边一次（可以重复经过图中的节点），则称该路径为 S 到 T 的欧拉路径，或者欧拉路。

欧拉图的判定

已知一张无向图（这里忽略有向图，其实只有有向图成为无向图时才谈得上欧拉路），

\textbf{此图为欧拉图}\Longleftrightarrow\textbf{此图连通，并且每个点的度数都是偶数}

欧拉路径的存在性判定

已知一张无向图，

\textbf{图中，存在欧拉路}\Longleftrightarrow\textbf{此图连通，并且图中恰好有两个节点的度数为奇数，其他节点的度数都是偶数}

这两个度数为奇数的就是欧拉路径的起点和终点。

一种朴素的做法是借助深度优先遍历和栈求欧拉回路的节点倒序，伪代码如下：

void dfs(int x)
    对于从 x 出发的每条边(x,y)
    如果该边没有被访问过
        把这条边标记为已访问
        dfs(y)
        把 y 入栈

int main()
    dfs(1)
    起点入栈
    倒序输出栈中所有节点

自行验证正确性。此时y入栈的时候是经过边的时候，也即若要在欧拉路径上把边的编号输出，则需要在y入栈时记录边。

当然，我们也可以这样：

void dfs(int x)
    对于从 x 出发的每条边(x,y)
    如果该边没有被访问过
        把这条边标记为已访问
        dfs(y)
    把 x 入栈

int main()
    dfs(1)
    倒序输出栈中所有节点

值得提醒的是，上述算法的时间复杂度为 O(NM) 。因为一个点会被重复遍历多次，每次都会扫描与它相连的所有的边——虽然我们明明知道大部分边已经访问过了。
假设我们采用邻接表储存无向图，我们可以在访问一条边 (x,y) 后，即使修改表头 head[x] ，令它指向下一条边。这样我们每次只需取出 head[x] ，就自然跳过了所有已经访问过的边。
另外，因为欧拉回路深搜的递归层数是 O(M) 级别的，容易造成系统栈溢出，我们可以用另一个栈，模拟机器递归的过程，把代码转化为非递归实现。时间复杂度 O(N+M) 。

int h[N],e[M],ne[M],idx;
inline void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int stk[M],top,ans[M];
int nu;
bool vis[M];
void dfs(){
    stk[++top]=1;
    while(top>0){
        int u=stk[top],i=h[u];
        while(i!=-1 && vis[i])  i=ne[i];
        if(i!=-1){
            stk[++top]=e[i];
            vis[i]=vis[i^1]=true;
            h[u]=ne[i];
        }else{
            top--;
            ans[++nu]=u;
        }
    }
}

int main(){
    memset(h,-1,sizeof h);
    …… 
    dfs();
    for(int i=nu;i>0;i--)   printf("%d",ans[i]);
    return 0;
}

还是留个完整的模板吧。嗯 \LongrightarrowP7771 【模板】欧拉路径

  1. P1333 瑞瑞的木棍
  2. P1341 无序字母对
  3. P2731 [USACO3.3] 骑马修栅栏 Riding the Fences：注意审题，不一定有500个点
  4. P1127 词链

图论2