简单图论大学习

零、前言

作者是 xxs ，图论学得不多，文章有错误还请指出。

一、图的存储与遍历

存储

存图有多种方法，都不复杂，很容易实现。

1.邻接矩阵

直接使用二维数组 graph[N][N] 来存，它虽然代码简单，查询较快，但是有时候很浪费空间，而且数据范围有较大的限制，并不常用。

2.邻接表

顾名思义，邻接表就是 每个节点值储存它直接可以到的其他节点 。

它的空间浪费比邻接矩阵小得多，但是，在找邻居的时候，要遍历它的整个邻接表，速度比邻接矩阵慢。

3.链式前向星

它其实就是用链表实现的邻接表。

主体一个 head[u] 数组，指向 u 的邻居存的地址。
和一个 struct Edge{int to,nxt}; ，其中， to 指邻居编号， nxt 指下一个邻居的地址。

具体代码如下：

struct Edge{int nxt,to;}e[N*2];
int head[N*2];
void init(){
    cnt=0;
    for(int i=0;i>u>>v;
    addedge(u,v);
    addedge(v,u);
}

4.Vector 直接存边

这个方法是最常用的一个。

直接用 vector e[N] 存边就可以了。

struct Edge{int to,w;};
vector e[N];
...

遍历

这里只介绍后两种常见方法的遍历方法，前两种请读者自行探讨。

链式前向星

for(int i=head[u];~i;i=e[i].nxt){
    ...
}

Vector 直接存边

for(auto it:e[u]){
    ...
}

那么，学会存图和遍历后，来做一下几道模板题来练一练吧：

• 图的存储与出边的排序
• 图的遍历

二、拓扑排序

首先，你要了解拓扑在干什么：

给一个有向无环图(DAG)的所有节点排序————OI_WIKI

那么，拓扑排序之后，就一定有：

• 每个顶点仅出现一次；
• 对于有向边 A->B，在序列中都必有 A 在B前。

操作还是比较简单的：

• 1.找到入度为 \(0\) 的点并输出；
• 2.将所有与该点连接的边删除，邻居入度减 \(1\)；
• 3.重复步骤 1~2 ,直到没有任何点入度为 \(0\) 为止。

\({\color{red}注意：有环图是不能进行拓扑排序的！！}\)

学了拓扑，还是做一道模板题吧：
【模板】拓扑排序/家谱树

三、欧拉路

欧拉路其实就是一个简单的一笔画问题。

它的定义是：从图中某一个点出发，遍历整个图，图中每一条边通过且仅通过一次。
欧拉回路就是起点和终点一样的欧拉路。

一般关于欧拉路的问题基本上就是：

• 是否有欧拉路。
• 打印欧拉路。

通常是通过处理度来解决问题的。

其中，度数为奇数的为奇点，度数为偶数的为偶点。

1.存在性判断

无向图

若全是偶点，存在欧拉回路，显然。
若有 \(2\) 个奇点，存在欧拉路，一个是起点，另一个是终点。

有向图

和无向图差不多，我们将一个点的度数记作入度减去出度。

若所有点度数为零，才会存在欧拉回路。
若仅有一个点度数为 \(1\)，一个点度数为 \(-1\)，其余点的度数为零，才存在欧拉路，\(1\) 的为起点，\(-1\) 的为终点。

2.输出欧拉回路

法1：DFS

法2：栈

习题

• Luogu:P7771 【模板】欧拉路径
• UVa:10054 The Necklace
• POJ:1780 Code

四、连通性问题

关于连通性：

• 连通：对于无向图的两点 \(u,v\) ，若存在途径使得 \(v_0=u\) 且 \(v_k=v\)，则称 \(u,v\) 连通。
• 连通图：任意两点连通的无向图称为连通图。

1.无向图

一些定义：

• 割点：对于 \(G=(V,E)\)，\(x \in V\),若删去 \(x\) 以及关联的边后，图分裂为两个及以上不相连的子图，则称 \(x\) 为 \(G\) 的割点。
• 割边（桥）：同上。

首先，我们要会求割点和割边：

很明显考虑 Tarjan\(^0\) 算法。

求割点 【模板】割点（割顶）

依赖一下两个主要的数组：

• 追溯值 \(low_x\) ：定义为以 \(x\) 为根的搜索树上的点以及通过一条不在搜索树上的边能达
  到的结点中的最小编号。
• 时间戳 \(dfn_x\) ：定义为 \(x\) 按访问顺序的编号。

//-------Tarjan部分
void Tarjan(int u){
    dfn[u]=low[u]=++Time;
    int son=0;
    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(son>=2&&u==root)cnt+=!is_cut[u],is_cut[u]=1;
}
//--------主函数部分
for(int i=1;i<=n;i++)
    if(!dfn[i])root=i,Tarjan(i);

求割边 【模板】割边（桥）

和割点很像：

void Tarjan(int u,int f){
    dfn[u]=low[u]=++cnt;
    for(int i=head[u];i;i=dis[i].nxt){
        int v(dis[i].to);
        if(v==f) continue;
        if(!dfn[v]){
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){
            	e[++tot][0]=u;e[tot][1]=v;
            }
        }else low[u]=min(low[u],dfn[v]);
    }
}

习题：

• Luogu:P3469 [POI 2008] BLO-Blockade
• HDU:2460 Network

割点和割边可以引出以下这些更为重要的定义：

• 点双连通图：不存在割点的无向连通图称为点双连通图。
• 边双连通图：不存在割边的无向连通图称为边双连通图。
• 点双连通分量：一张图的极大点双连通子图称为点双连通分量（v-DCC\(^1\)），简称点双。
• 边双连通分量：一张图的极大边双连通子图称为边双连通分量（e-DCC\(^2\)），简称边双。

但是完全看不懂。

说简单一点就是：

在一张连通的无向图中，对于两个点 \(u\) 和 \(v\)，如果无论删去哪一条边都不能使它们不连通，我们就说 \(u\) 和 \(v\) 边双连通。——OI_WIKI

在一张连通的无向图中，对于两个点 \(u\) 和 \(v\)，如果无论删去哪一个点（不能删 \(u\) 和 \(v\) 自己）都不能使它们不连通，我们就说 \(u\) 和 \(v\) 点双连通。——OI_WIKI

\({\color{red}要注意的是，虽然割边不隶属于任何边双，但是割点是有可能隶属于多个点双的。}\)

求边双 【模板】边双连通分量

边双连通分量的求法很简单。并不比求割边的代码长太多，依旧依赖一下两个主要的数组：

• 追溯值 \(low_x\)
• 时间戳 \(dfn_x\)

在求割边的时候，我们已经对所有割边进行了标记。
所以我们只要再次 DFS ，不访问割边，对每一各连通块进行标记，则可以得到边双。

求点双 【模板】点双连通分量

点双联通分量的求法就没有边双那么简单了。虽然割边不隶属于任何边双，但是割点是有可能隶属于多个点双的。

所以此时我们就应该在跑 Tarjan 的过程中维护一个栈。

• 当一个节点第一次被访问时，入栈。
• 当 dfn[x]<=low[y] 成立时，不断弹栈，直至 \(y\) 被弹出。而且刚刚弹掉的节点和 \(x\) 构成一个 v-DCC 。

习题：

边双：

• Luogu:P11360 [CEOI 2015] 管道
• POJ:3352 Road Construction
• Luogu P2860 [USACO06JAN] Redundant Paths G

点双：

• Luogu:P3225 [HNOI2012] 矿场搭建
• POJ:2942 Knights of the Round Table
• Luogu:P5058 [ZJOI2004] 嗅探器

2.有向图

一些定义：

• 强连通：若一张有向图的节点两两互相可达，则称这张图是强连通的。
• 强连通分量：即极大的强连通子图，称为SCC\(^3\)。

首先，我们要了解 DFS 生成树。

我们在一个有向图上选一点 \(r\) ，从 \(r\) 开始遍历，每一个点只遍历一次，这样就会构成一棵树，即 DFS 生成树。

这棵树上会有这么几种边：

• 树边：每次由⼀个已遍历的点到达未遍历的点，就形成了⼀条树边。
• 返祖边：也叫做回边，指向该节点的祖先。
• 横叉边：搜索时遇到⼀个已访问的节点，但这个节点并不是该节点的祖先。
• 前向边：访问时遇到⼦树中的节点时形成的。

举个栗子，如图：

图中的红边即为返祖边，紫边为横插边，黄边为前向边，其余为树边。

求强连通分量有很多方法，由于作者很菜，本文只介绍 \(1\) 种。

Tarjan 算法

这个算法依旧是用栈来处理。

DFS 流程很简单：

• 我们把当前节点 \(u\) 入栈。
• 若 \(dfn_u=low_u\) ，则开始弹栈，直到 \(u\) 被弹出去。
• 弹出去的点构成一个 SCC。

习题

• Luogu:P3387 【模板】缩点
• Luogu:P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
• Luogu:P2863 [USACO06JAN] The Cow Prom S
• Luogu:P2515 [HAOI2010] 软件安装
• HDU:3394 Railway
• HDU:1530 Maximum Clique

注释

• \(^0\)：Robert E. Tarjan（罗伯特·塔扬），生于美国加州波莫纳，计算机科学家．Tarjan 发明了很多算法和数据结构。比如求各种连通分量的 Tarjan 算法、求 LCA 的 Tarjan 、并查集、Splay、LCT 也是 Tarjan 发明的。
• \(^1\)：\(vertex \ double \ connected \ component\) 的缩写。
• \(^2\)：\(edge \ double \ connected \ component\) 的缩写。
• \(^3\)：\(strongly \ connected \ components\) 的缩写。