top
back
序
noip 迫在眉睫,图论算法久未谋面……
不是在沉默中爆发,就是在沉默中灭亡……
终于,我痛下决心,在一个风雨交加的夜晚,向图论宣战!
说明
-
部分图片或文字来源于网络,侵删。
-
整理过程中难免有纰漏,还请多多包涵~
-
从下一行开始,标红且加粗的文字一般带有可以访问的链接。
若链接失效或对笔记本身有建议或意见,请私信我或在评论中@我哦~
-
大部分与图有关的图片由图论画图神器csacademy生成,使用方法可以参考这篇文章:图论画图神器——CS Academy。
-
如无特殊说明,默认用链式前向星存图。
head
数组为表头,in
、out
数组为入度、出度,cnt_edge
为边数。边的其他信息【如to
「终点」、val
「边权」等】统一存储在class Edge
中。详细解释见后文「图论基础——图的存储——链式前向星」。 -
由于缺省源过长,因此多数代码只给出核心部分。如不另说明,头文件请自己补全。
namespace ly
中用到的函数/容器和namespace std
中对应函数/容器用法基本相同,仅为优化常数而重新实现一遍。「原理:内联+传址引用+auto
/函数模板/类模板,同时省去STL
中杂七杂八的东西。」缺省源见:缺省源。大体来说:-
namespace ly::algorithm
一些简单 STL 函数的重新实现,如
max
、min
、swap
等。本人习惯随用随写。例如ly::min
的简单实现:namespace algorithm { auto min=[](const auto &x,const auto &y)->auto{return x<y?x:y;}; }using namespace algorithm;
- 若想使用 STL 中原来的函数,直接将代码中的
ly::
去掉,并引入对应函数的头文件即可。
- 若想使用 STL 中原来的函数,直接将代码中的
-
namespace ly::DS
一些简单 STL 容器的重新实现,如
stack
、queue
、deque
、list
、heap
等。- 其中
heap
对应 STL 中的priority_queue
,声明时可以指定是大根堆/小根堆「默认大根堆」。如ly::DS::heap<int>h1(0),h2(1);
声明了两个int
类型的堆,其中h1
是小根堆、h2
是大根堆。 - 用法和 STL 基本相同,如
q.push(x)
、h.top()
、s.size()
等使用效果与 STL 基本相同。 - 更多细节详见我之前的博客:数据结构模板整合。
- 若想使用 STL 中原来的容器,直接将代码中的
ly::DS::
去掉,并引入对应容器的头文件即可。
- 其中
-
-
代码中出现的
read
、write
、put
等函数定义在我自己的namespace ly::IO
中,作用是优化输入、输出,详见我之前的一篇博客:最全快读、快写模板「持续更新」 。简单来讲:
-
read
可以一次读入一个或多个不同类型的变量。【形如
read(x)
、read(a,b,c,d,...)
】 -
write
可以一次输出一个或多个不同类型的变量。-
若输出多个变量,
write
会自动用空格分隔并在结尾回车。【形如
write(a,b,c,d,...)
】 -
若只有一个变量,
write
只会输出该变量本身。【形如
write(x)
】
-
-
put
可以一次输出一种类型的变量-
后面可以接一个参数 0 或 1 表示输出空格或换行。
【形如
put(x,0)
】 -
不加参数默认输出换行。
【形如
put(x)
】
-
-
-
代码中出现的
INT_MAX
、INT_MIN
、LONG_MAX
、LONG_MIN
定义在头文件<climits>
中,比较常用。但有时为了防止爆int
,会选用0x3f3f3f3f
而不是INT_MAX
作为最大值,因为它是满足以下两个条件的最大整数:「参考——《算法竞赛进阶指南》P3」- 整数的两倍不超过
0x7fffffff
,即int
能表示的最大正整数。 - 整数的每 8 位「每个字节」都是相同的。
这样,当我们需要把一个数组中的数值初始化成正无穷时,为了避免加法算数上溢或者繁琐的判断,可以使用
memset(a,0x3f,sizeof(a))
。「当然,
memset
有时会导致 TLE。例如开一个1e6
大小的数组a
,使用memset(a,0,sizeof(a))
就等价于for(int i=0;i<1e6;++i) a[i]=0
,显然有很多不必要的时间浪费。当n
比1e6
小很多时,建议改为for(int i=1;i<=n;++i) a[i]=0
,常数小一些。」 - 整数的两倍不超过
-
码风问题。
本人习惯 等价形式 if(x)
if(x!=0)
if(!x)
if(x==0)
if(~x)
if(x!=-1)
if(x&1)
if(x%2==1)
if(!(x&1))
if(x%2==0)
if(x^y)
if(x!=y)
x?y:z;
if(x) y;else z;
x<<1
x*2
x>>1
x/2
a[++b]=c
b++,a[b]=c
a[b++]=c
a[b]=c,b++
return a,b,c;
a,b;return c;
其他习惯:
ll x;
等价于long long x;
,在缺省源中有#define ll long long
。- 习惯将数组最大值设为
maxn
等等,#define maxn 1010
等价于constexpr auto maxn=1010;
,在 Debug心得&笔记——⑰不同命名空间的宏定义冲突 中有较为详细的解释。
图论基础
图的定义
图由顶点的有穷非空集合和顶点之间边的集合组成,表示为 \(G(V,E)\),其中 \(G\) 表示一个图,\(V\) 是图 \(G\) 中顶点的集合,\(E\) 是图 \(G\) 中边的集合。
例如:
![](图的定义示意图.png)
「由于在 \(OI\) 中,图的术语没有标准化,因此,称顶点为点、节点、结点、端点等都是可以的。名称不重要,理解才是关键。」
图的分类
-
无向图
- 无向边:没有方向的边,用无序偶对 \((u,v)\) 表示,在图中表示为连接 \(u\) 点和 \(v\) 点的线段。
- 如果图中所有的边都是无向边,则称该图为无向图。
- 度:与无向图中一点 \(u\) 相连的边数叫做点 \(u\) 的度。
-
有向图
- 有向边:具有方向的边,也称为弧。用有序偶 \(<u,v>\) 表示,在图中表示为从 \(u\) 点指向 \(v\) 点的箭头。
- 如果图中所有边都是有向边,则称该图为有向图。
- 入度:有向图中一点 \(u\) 作为图中边的终点的次数之和叫做点 \(u\) 的入度。
- 出度:有向图中一点 \(u\) 作为图中边的起点的次数之和叫做点 \(u\) 的出度。
- 有向无环图:没有环的有向图,又称 DAG。
-
简单图
- 无重边「同一条边重复出现」且无自环「存在顶点到其自身的边」的图称为简单图。
如上面左、右两图都不是简单图。「左图有重边,右图有自环。」
-
连通图
-
无向连通图
在无向图 \(G\) 中,如果从顶点 \(u\) 到顶点 \(v\) 有路径,则称 \(u\) 和 \(v\) 是连通的。如果图中任意两个顶点都是连通的,则称 \(G\) 是连通图。
-
强连通图
在有向图 \(G\) 中,如果 \(\forall u,v\in V,u\ne v\),从 \(u\) 到 \(v\) 和从 \(v\) 到 \(u\) 间都存在路径,则称 \(G\) 是强连通图。
-
-
完全图
-
无向完全图
-
在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。
-
一个有 \(n\) 个顶点的无向完全图,有 \(\frac{n(n-1)}2\) 条边。
-
-
有向完全图
- 在有向图中,如果任意两个顶点之间都存在方向互为相反的两条有向边,则称该图为有向完全图。
- 一个有 \(n\) 个顶点的有向完全图,有 \(n(n-1)\) 条边。
-
-
二分图
设 \(G=(V,E)\) 是一个无向图,如果顶点 \(V\) 可分割为两个互不相交的子集 \((A,B)\),并且图中的每条边 \((i,j)\) 所关联的两个顶点 \(i\) 和 \(j\) 分别属于这两个不同的顶点集,则称图 \(G\) 为一个二分图。
「如上面的二分图,可以将顶点分为 \(1\)~\(4\) 和 \(5\)~\(8\) 两部分,每部分中的顶点没有连边。」
特殊的图——树
-
树的定义和性质
- 树是任意两个顶点间有且只有一条路径的图。
- 树是点数比边数多 \(1\) 的连通图。
-
树的亿些概念
-
树的每个元素称为节点。有一个特定的节点被称为根节点或树根。
-
设 \(T_1,T_2,...,T_k\) 是树,它们的根节点分别为 \(n_1,n_2,...,n_k\)。用一个新节点 \(n\) 作为 \(n_1,n_2,...,n_k\) 的父亲,则得到一棵新树,节点 \(n\) 就是新树的根。我们称 \(n_1,n_2,...,n_k\) 为一组兄弟节点,它们都是节点 \(n\) 的子节点,\(T_1,T_2,...,T_k\) 为节点 \(n\) 的子树。
-
空树:空集合也是树,称为空树。空树中没有节点。
-
子节点:一个节点含有的子树的根节点称为该节点的子节点。
-
父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点。
-
兄弟节点:具有相同父节点的节点互称为兄弟节点。
-
节点的度:一个节点含有的子节点的个数称为该节点的度。
-
叶节点:度为 \(0\) 的节点称为叶节点。
-
分支节点:度不为 \(0\) 的节点称为分支节点。
-
树的度:一棵树中,最大的节点的度称为树的度。
-
节点的祖先:从根到该节点所经分支上的所有节点。
-
节点的子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
-
森林:由 \(m(m\ge0)\) 棵互不相交的树组成的集合称为森林。
-
-
二叉树
- 每个节点最多有两个子树的树是二叉树。
- 满二叉树:在一棵二叉树中,如果所有分支节点都存在左子树和右子树,且所有叶子都在同一层上,这样的二叉树称为满二叉树。「感性理解为一个完整的三角形。。。」
- 完全二叉树:除最后一层外,其他各层的节点数都达到最大个数,且最后一层的节点都连续集中在最左边。
图的存储
说明:设待存图的点数为 \(n\),边数为 \(m\)。输入为第一行 \(n,m\),接下来 \(m\) 行,每行 \(3\) 个正整数 \(x,y,w\),表示 \(x\) 到 \(y\) 连边,边权为 \(w\)。下面举个栗子。
输入:
9 10
1 2 1
1 3 2
2 4 3
2 5 4
3 5 5
3 6 6
6 7 7
7 8 8
7 9 9
8 9 10
这样建好的图有两种情况:无向图和有向图。
-
邻接矩阵【适合存稠密图】
-
用一个二维数组 \(a\) 存储边。
-
\(a[i][j]=\text{INF}\) 表示不存在点 \(i\) 向点 \(j\) 的边,\(a[i][j]=w\) 表示存在点 \(i\) 向点 \(j\) 的边且边权为 \(w\),\(a[i][i]=0\) 表示无自环。
-
空间复杂度 \(O(n^2)\)。
-
代码实现
#define maxn 1010 #define INF 0x3f3f3f3f int n,m,x,y,w,a[maxn][maxn]; signed main() { read(n,m); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i^j) a[i][j]=INF; for(int i=1;i<=m;++i) read(x,y,w),a[x][y]=w; return 0; }
- 其中,
i^j
表示i!=j
。 - 关于为什么不用
memset
「其实这里用不用影响不大」,见「序——说明」。
- 其中,
-
注意
存储无向图时要正反双向建边:
a[x][y]=a[y][x]=1
。 -
优点:写法简单。
-
缺点:空间复杂度过高。
-
-
邻接链表「
vector
存图,因为几乎不用故不再详细整理。」- 优点:建图步骤较为简单。
- 缺点:常数大!!!
-
链式前向星【适合存稀疏图】「强烈推荐!!!」
-
建立 \(n\) 个链表,链表中的元素是图中的边。可以用数组或结构体/类模拟链表。
-
「可以这样想象,有 \(n\) 个链表,表头是 \(1\)~\(n\) 即每个节点的编号,第 \(i\) 个表中的元素是所有以节点 \(i\) 作为起点的边的编号。各个元素按照加边的顺序存储。」
-
to
数组:to[i]
表示 \(i\) 号边的终点。 -
val
数组:val[i]
为第 \(i\) 条边的边权。 -
head
数组:head[i]
表示从第 \(i\) 个节点出发的第一条边在edge
和to
数组中的存储位置,初始时为 \(0\)。 -
next
数组:从相同节点出发的下一条边在edge
和to
数组中的存储位置。 -
根据以上各数组的意义,设
maxn
表示最大节点个数 \(+1\),maxm
表示最大边数 \(+1\),则head
数组的大小至少要开到maxn
,to
、val
、next
数组的大小至少要开到maxm
。「无向图注意maxn
要 \(\times2\)」 -
cnt
:当前存的是第几条边。从编号 \(1\) 开始存,存到编号 \(m\)。 -
add_edge(int x,int y,int w)
:加边函数。-
x
、y
、w
分别表示边的起点、终点、边权。 -
作用是从
x
向y
连一条边权为w
的边。 -
实现:
-
先将
cnt++
。 -
然后通过
to[cnt]=y
记录终点。 -
val[cnt]=w
记录边权。 -
next[cnt]=head[x]
记录以x
为起点的上一条边的编号,以便于以后访问以x
为起点的每一条边。「虽然这样存储,访问是倒序的,但不影响结果。」
-
head[x]=cnt
更新以x
为起点的上一条边的编号。「后面再添加以
x
为起点的边时,可以保证该边正确接到表头为x
的链表后面。」
-
-
-
数组实现
#define maxn 1010 #define maxm 1010 #define next nxt int n,m,x,y,w; int cnt,head[maxn],val[maxm],to[maxm],next[maxm]; inline void add_edge(int x,int y,int w) { to[++cnt]=y; val[cnt]=w; next[cnt]=head[x]; head[x]=cnt; } signed main() { read(n,m); for(int i=1;i<=m;++i) read(x,y,w),add_edge(x,y,w); return 0; }
-
其中,因为
next
在c++
中属于保留字,直接使用会报错:error: reference to 'next' is ambiguous
,可以用#define next nxt
解决。
将用到的
val
、to
、next
这些与边有关的变量统一存入结构体/类中,可以更加一目了然。同时可以很轻松避免命名冲突的问题。「由于
head
存的是每个节点而不是边的信息,因此要放到结构体/类的外面。类似的有每个节点的入度、出度等也要放在外面。」-
结构体实现
#define maxn 1010 #define maxm 1010 int n,m,x,y,w; int cnt,head[maxn]; struct Edge { int val,to,next; }edge[maxm]; inline void add_edge(int x,int y,int w) { edge[++cnt].to=y; edge[cnt].val=w; edge[cnt].next=head[x]; head[x]=cnt; } signed main() { read(n,m); for(int i=1;i<=m;++i) read(x,y,w),add_edge(x,y,w); return 0; }
-
类实现
#define maxn 1010 #define maxm 1010 int n,m,x,y,w; int cnt,head[maxn]; class Edge { public: int val,to,next; }edge[maxm]; inline void add_edge(int x,int y,int w) { edge[++cnt].to=y; edge[cnt].val=w; edge[cnt].next=head[x]; head[x]=cnt; } signed main() { read(n,m); for(int i=1;i<=m;++i) read(x,y,w),add_edge(x,y,w); return 0; }
当然,写多了你可以像我一样:「存图的部分用空行分开,大概能增加代码可读性……」
#define maxn 1010 #define maxm 1010 int n,m,x,y,w; int cnt_edge,head[maxn]; class Edge{public:int val,to,next;}edge[maxm]; inline void add_edge(int x,int y,int w){edge[++cnt_edge].to=y,edge[cnt_edge].val=w,edge[cnt_edge].next=head[x],head[x]=cnt_edge;} signed main() { read(n,m); for(int i=1;i<=m;++i) read(x,y,w),add_edge(x,y,w); return 0; }
核心代码只有不到五行,十分简洁。「这里用
cnt_edge
是为了避免与其他变量重名。」- 空间复杂度 \(O(n+m)\)。
- 优点:太多,不说了。
- 缺点:不易上手,但多写几遍就会了。似乎也没啥其他缺点了。
-
由于树是一种特殊的图,因此在存储方式上二者本质并无区别。唯一比较特殊的就是树的输入中 \(m=n-1\)。下面用链式前向星实现树的存储「其实把上面改改就好了」:
#define maxn 1010
int n,x,y,w;
int cnt_edge,head[maxn];
class Edge{public:int val,to,next;}edge[maxn];
inline void add_edge(int x,int y,int w){edge[++cnt_edge].to=y,edge[cnt_edge].val=w,edge[cnt_edge].next=head[x],head[x]=cnt_edge;}
signed main()
{
read(n);
for(int i=1;i<n;++i) read(x,y,w),add_edge(x,y,w);
return 0;
}
图的遍历
定义&说明
图的遍历是指从图中的任一顶点出发,对图中的所有顶点访问一次且只访问一次。
——百度百科
重点有两个:
- 每个顶点都要访问。
- 每个顶点只访问一次。
因此,不论怎样实现图的遍历,都可以开一个bool
类型的 vis
数组存储每个顶点是否已被访问的状态,vis[i]==0
表示顶点 \(i\) 未被访问,vis[i]==1
表示顶点 \(i\) 已被访问。当 vis[i]==1
且再遍历到顶点 \(i\) 时,直接跳过即可。
输入同前面「图论基础——图的存储」:
设待存图的点数为 \(n\),边数为 \(m\)。输入为第一行 \(n,m\),接下来 \(m\) 行,每行 \(3\) 个正整数 \(x,y,w\),表示 \(x\) 到 \(y\) 连边,边权为 \(w\)。
样例相同:
9 10 1 2 1 1 3 2 2 4 3 2 5 4 3 5 5 3 6 6 6 7 7 7 8 8 7 9 9 8 9 10
这里我们假设存的是有向图:「无向图中的边可以看作成对出现的双向边。」
深度优先遍历
「Depth-First-Search,简称 DFS」
深度优先遍历,就是在每个点 \(x\) 上面对多条分支时,任选一条边走下去,执行递归,直至回溯到点 \(x\) 后,再考虑走向其他的边。
——李煜东《算法竞赛进阶指南》P93
过程
- 选择一个点作为起点。
- 将被选择的点标记为已访问。
- 遍历以被选择的点为起点的所有边,当找到一条终点末被访问的边
时,访问该边的终点。 - 将终点作为已选择的点重复第 2~4 步,当不存在未访问的点时,遍历结
束。
邻接矩阵实现
#define maxn 1010
#define INF 0x3f3f3f3f
int n,m,x,y,w,a[maxn][maxn];
bool vis[maxn];
void dfs(int i)
{
vis[i]=1;
put(i,0);
for(int j=1;j<=n;++j)
if(!vis[j]&&a[i][j]^INF)
dfs(j);
return;
}
signed main()
{
read(n,m);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i^j) a[i][j]=INF;
for(int i=1;i<=m;++i) read(x,y,w),a[x][y]=w;
for(int i=1;i<=n;++i) if(!vis[i]) dfs(i);
return 0;
}
-
建图不再解释,见前面「图论基础——图的存储——邻接矩阵」。
-
dfs(i)
的作用是从节点 \(i\) 开始,遍历以 \(i\) 为起点的每一条边。 -
遍历方式是枚举所有节点,访问每一个与 \(i\) 相连的节点 \(j\)。
-
为了保证每个节点只访问一次,我们用
vis
数组记录每个节点是否被访问的状态。- 若
vis[j]==1
,说明节点j
已经被访问过,不用再访问。 - 若
vis[j]==0
,说明节点j
未被访问,dfs(j)
递归访问j
即可。 - 每次开始执行
dfs(i)
时,此时i
被第一次访问,也是唯一一次访问。令vis[i]=1
并输出i
,表示i
此时被访问。
- 若
-
那
for(int i=1;i<=n;++i) if(!vis[i]) dfs(i);
的作用是什么呢?直接看之前的图。如果只访问 \(1\) 个节点:
- 假设只访问节点 \(1\)「即
dfs(1)
」,自然可以实现图的遍历,因为从节点 \(1\) 出发可以到达任何一个其他节点。 - 但如果只访问节点 \(4\)「或只访问节点 \(5\),或只访问节点 \(9\)」,则只能访问其本身,因为从该节点出发无法到达其他节点。
- 即使要遍历的图是无向图也要这样做,因为图不一定连通!「极端情况是每个节点都没有连边。」
- 因此要枚举每个节点作为起点,这样才一定可以访问到每个节点。
- 假设只访问节点 \(1\)「即
-
时间复杂度
访问 \(n\) 个节点,对访问到的每个节点 \(i\) 都要枚举 \(n\) 个节点 \(j\)。因此总时间复杂度 \(O(n^2)\)。
时间戳
样例输出:
1 2 4 5 3 6 7 8 9
可以发现,每个点确实只被访问了 \(1\) 次。
特殊地,如果该图是一颗树,则通过这种方法「在刚进入递归时记录该点编号」依次给这 \(n\) 个节点 \(1\)~\(n\) 的整数标记,该标记就被称为时间戳,记为 \(dfn\)。
对 dfs
简单修改即可求出 dfn
数组:
int cnt,dfn[maxn];
void dfs(int i)
{
vis[i]=1,dfn[i]=++cnt;
put(i,0);
for(int j=1;j<=n;++j)
if(!vis[j]&&a[i][j]^INF)
dfs(j);
return;
}
dfs 序
如果我们在对每个点的访问结束前再次输出其编号:
void dfs(int i)
{
vis[i]=1,put(i,0);
for(int j=1;j<=n;++j)
if(!vis[j]&&a[i][j]^INF)
dfs(j);
put(i,0);
return;
}
则会输出这样的结果:
1 2 4 4 5 5 2 3 6 7 8 9 9 8 7 6 3 1
特殊地,如果该图是一颗树,则通过这种方法「在刚进入递归和递归结束前分别记录该点编号」生成的长度为 \(2n\) 的节点序列被称为树的 DFS 序。
按照输出的序列画一下图:
![](图的遍历-dfs-邻接矩阵.png)
这便是用邻接矩阵实现的 dfs 对每个节点的访问顺序。
关于 DFS 序:
DFS 序的特点是:每个节点 \(i\) 的编号在序列中恰好出现两次。设这两次出现的位置为 \(l[i]\)、\(r[i]\),那么闭区间 \([l[i],r[i]]\) 就是以 \(i\) 为根的子树的 DFS 序。这是我们在很多与树相关的问题中,可以通过 DFS 序把子树统计转化为序列上的区间统计。
——李煜东《算法竞赛进阶指南》P94
链式前向星实现
「前面邻接矩阵实现中 dfs
参数用的 i
,这样 for
循环中用变量 j
,a[i][j]
符合习惯。但在链式前向星中没有 a[i][j]
的形式。当 x
作为递归参数时,循环变量用 i
,令 y=edge[i].to
,这样 <x,y>
构成一条有向边,比较符合习惯。因此下面链式前向星的递归参数用 x
。」
「当然,还是根据个人偏好而定。」
#define maxn 1010
#define maxm 1010
int n,m,x,y,w;
int cnt_edge,head[maxn];
class Edge{public:int val,to,next;}edge[maxm];
inline void add_edge(int x,int y,int w){edge[++cnt_edge].to=y,edge[cnt_edge].val=w,edge[cnt_edge].next=head[x],head[x]=cnt_edge;}
bool vis[maxn];
void dfs(int x)
{
vis[x]=1,put(x,0);
int y;
for(int i=head[x];i;i=edge[i].next)
if(!vis[y=edge[i].to]) dfs(y);
return;
}
signed main()
{
read(n,m);
for(int i=1;i<=m;++i) read(x,y,w),add_edge(x,y,w);
for(int i=1;i<=n;++i) if(!vis[i]) dfs(i);
return 0;
}
-
可以类比前面的邻接矩阵实现。
-
与邻接矩阵实现的主要区别在于枚举顶点的方式不同。
-
邻接矩阵
对于当前的顶点 \(i\),直接枚举所有顶点 \(j\),先判断顶点 \(j\) 是否已访问过「这点二者相同」,再判断 \(i\)、\(j\) 之间是否有连边。
-
链式前向星
由于链式前向星本身存的就是每个顶点连的边的信息,因此对于当前的顶点 \(x\),以 \(x\) 为表头的链表存储的就是以 \(x\) 为起点的所有边的信息。【这里不懂的回去看看「图论基础——图的存储——链式前向星」】
一开始接触这一过程可能不是很好理解,所以重新思考我们的目的是什么:当前已经访问节点 \(x\) 了,接下来要访问所有与 \(x\) 相连的节点。
我们可以枚举与 \(x\) 相连且以 \(x\) 为起点的边「设边的编号为 \(i\)」,这样边的终点「
edge[i].to
」不就是我们要找的节点吗?现在问题转化为如何求出与 \(x\) 相连的边的编号。链式前向星模拟的 \(n\) 个链表存储的不就是以每个顶点为起点的所有边的编号吗?
以顶点 \(x\) 为起点的上一条边「这里上一条的含义是上一次加入」的编号即为
head[x]
,这就是我们找到的第一条边的编号。令
i=head[x]
,由于edge[i].next
的含义是在第 \(i\) 条边之前加入的上一条与第 \(i\) 条边同起点「起点也是 \(x\)」的边的编号,因此,第edge[i].next
条边是我们找到的第二条满足条件的边。接下来,不断令i=edge[i].next
,则第edge[i].next
条边同样满足条件。直到edge[i].next
的值为 \(0\),此时我们已经找不到上一条满足条件的边,edge[i]
即为我们第一个插入的起点为 \(x\) 的边,循环终止。这个过程中遇到的每个
i
都是起点为 \(x\) 的边的编号,因此对于每个i
,edge[i].to
都是对应边的终点,即我们一开始要找的与 \(x\) 相连的节点。如果edge[i].to
未被访问过,对其用dfs(edge[i].to)
递归访问即可。这就有了:
for(int i=head[x];i;i=edge[i].next) if(!vis[edge[i].to]) dfs(edge[i].to);
有时访问每个
i
时要进行额外的操作,每次都写一遍edge[i].to
未免有些麻烦,我们可以定义一个变量int y=edge[i].to
,直接if(!vis[y]) dfs(y);
即可,变得十分简洁。「而且,
<x,y>
恰好构成一条有向边,这种形式符合习惯。」容易发现,此过程中我们只枚举了满足起点为 \(x\) 的边,并没有枚举每一条边,因此显然优于邻接矩阵的遍历方式。
-
-
时间复杂度
我们已经知道链式前向星实现的时间复杂度优于邻接矩阵实现,那么其时间复杂度到底是多少?
容易发现,这段
dfs
代码访问每个点和每条边恰好 \(1\) 次「如果是无向边,正反向各访问一次」,其时间复杂度为 \(O(n+m)\)。 -
访问顺序
上面的代码输入样例后,输出如下:
1 3 6 7 9 8 5 2 4
和邻接矩阵实现的输出结果不同?
不会是写错了吧?其实,两种实现方式都是正确的,因为都保证了每个节点只被访问一次。
邻接矩阵是按照 \(1\)~\(n\) 的顺序枚举顶点 \(j\),而链式前向星是按照加入起点为 \(i\) 的边的倒序枚举边的编号 \(j\)。
枚举顺序不同,导致了访问节点的顺序不同,输出结果不同。
我们不妨再看一下在对每个点的访问结束前再次输出其编号的结果。
1 3 6 7 9 9 8 8 7 6 5 5 3 2 4 4 2 1
再次按照输出的序列画一下图:
这便是用链式前向星实现的 dfs 对每个节点的访问顺序。
图的连通块划分
在「图论基础——图的遍历——链式前向星——深度优先遍历——邻接矩阵实现」中,我们已经提及了 for(int i=1;i<=n;++i) if(!vis[i]) dfs(i);
的作用,且提到过图不连通的情况。
先给出连通块的定义:
若在无向图的一个子图中,任意两个节点之间都存在一条路径「可以互相到达」,并且这个子图是“极大”的「不能再扩张」,则称该子图为无向图的一个连通块。一张不连通的无向图由 \(\ge2\) 个连通块组成,而一张无向连通图整体是一个连通块。
——李煜东《算法竞赛进阶指南》P96
如果只调用 dfs(x)
,那么只能访问从 \(x\) 到达的所有点和边。因此,对一张图进行多次深度优先遍历,可以划分出该图中的各个连通块;对一个森林进行多次深度优先遍历,可以划分出森林中的每棵树。
设 cnt
为无向图包含连通块的个数,v
数组标记了每个点属于哪个连通块。
「其实不用再开一个 v
数组,直接将原来的 vis
数组改为 int
类型,直接当作 v
数组来用就可以,这也不影响其记录每个节点是否被访问的功能。」
代码如下:
#define maxn 1010
#define maxm 1010
int n,m,x,y,w,cnt;
int cnt_edge,head[maxn];
class Edge{public:int val,to,next;}edge[maxm];
inline void add_edge(int x,int y,int w){edge[++cnt_edge].to=y,edge[cnt_edge].val=w,edge[cnt_edge].next=head[x],head[x]=cnt_edge;}
bool vis[maxn];
void dfs(int x)
{
vis[x]=cnt;
int y;
for(int i=head[x];i;i=edge[i].next)
if(!vis[y=edge[i].to]) dfs(y);
return;
}
signed main()
{
read(n,m);
for(int i=1;i<=m;++i) read(x,y,w),add_edge(x,y,w);
for(int i=1;i<=n;++i) if(!vis[i]) cnt++,dfs(i);
return 0;
}
树的遍历
和图的遍历几乎一模一样,但不需要 for(int i=1;i<=n;++i) if(!vis[i]) dfs(i);
。设根节点编号为 \(x\),只需调用一次 dfs(x)
即可。
树的深度
树中各个节点的深度是一种自顶向下的统计信息。起初,我们已知跟节点的深度为 \(0\)。若节点 \(x\) 的深度为 \(d[x]\),则它的子节点 \(y\) 的深度就是 \(d[y]=d[x]+1\)。在深度优先遍历的过程中结合自顶向下的递推,就可以求出每个节点的深度 \(d\)。
——李煜东《算法竞赛进阶指南》P94
代码实现:「设根节点为 \(1\)」
#define maxn 1010
int n,x,y,w;
int cnt_edge,head[maxn],d[maxn];
class Edge{public:int val,to,next;}edge[maxn];
inline void add_edge(int x,int y,int w){edge[++cnt_edge].to=y,edge[cnt_edge].val=w,edge[cnt_edge].next=head[x],head[x]=cnt_edge;}
bool vis[maxn];
void dfs(int x)
{
vis[x]=1;
int y;
for(int i=head[x];i;i=edge[i].next)
if(!vis[y=edge[i].to]) d[y]=d[x]+1,dfs(y);//从父节点 x 向子节点 y 递推,计算深度
return;
}
signed main()
{
read(n);
for(int i=1;i<n;++i) read(x,y,w),add_edge(x,y,w);
dfs(1);
return 0;
}
树的重心
当然,也有许多信息是自底向上进行统计的,比如以每个节点 \(x\) 为根的子树大小 \(size[x]\)。对于叶子节点,我们已知“以它为根的子树”大小为 \(1\)。若节点 \(x\) 有 \(k\) 个子节点 \(y_1\)~\(y_k\),并且以 \(y_1\)~\(y_k\) 为根的子树大小分别是 \(size[y_1],size[y_2]...,size[y_k]\),则以 \(x\) 为根的子树大小就是 \(size[x]=size[y_1]+size[y_2]+...+size[y_k]+1\)。
对于一个节点 \(x\),如果我们把它从树中删除,那么原来的一棵树可能会分成若干个不相连的部分,其中每一部分都是一棵子树。设 \(\text{max}\_\text{part}(x)\) 表示在删除节点 \(x\) 产生的子树中,最大的一棵的大小。使 \(\text{max\_part}\) 函数取到最小值的节点 \(p\) 就称为整颗树的重心。
——李煜东《算法竞赛进阶指南》P95
直接求重心可能有些棘手,我们不妨先考虑如何求出 size
数组。
#define maxn 1010
int n,x,y,w,size[maxn];
int cnt_edge,head[maxn];
class Edge{public:int val,to,next;}edge[maxn];
inline void add_edge(int x,int y,int w){edge[++cnt_edge].to=y,edge[cnt_edge].val=w,edge[cnt_edge].next=head[x],head[x]=cnt_edge;}
bool vis[maxn];
void dfs(int x)
{
vis[x]=1,size[x]=1;//x 的子树包含 x 本身
int y;
for(int i=head[x];i;i=edge[i].next)
if(!vis[y=edge[i].to]) dfs(y),size[x]+=size[y];//从子节点 y 向父节点 x 递推,计算子树大小
return;
}
signed main()
{
read(n);
for(int i=1;i<n;++i) read(x,y,w),add_edge(x,y,w);
dfs(1);
return 0;
}
设全局变量 ans
为重心对应的 max_part
,pos
为重心的编号。「将 ans
初始化为总节点个数 n
即可。」
利用求出来的 size
数组,很容易求得树的重心:
#define maxn 1010
int n,x,y,w,ans=n,pos,size[maxn];
int cnt_edge,head[maxn];
class Edge{public:int val,to,next;}edge[maxn];
inline void add_edge(int x,int y,int w){edge[++cnt_edge].to=y,edge[cnt_edge].val=w,edge[cnt_edge].next=head[x],head[x]=cnt_edge;}
bool vis[maxn];
void dfs(int x)
{
vis[x]=1,size[x]=1;
int y,max_part=0;//删掉 x 后分成的最大子树的大小
for(int i=head[x];i;i=edge[i].next)
if(!vis[y=edge[i].to])
{
dfs(y),size[x]+=size[y];
max_part=ly::max(max_part,size[y]);
}
max_part=ly::max(max_part,n-size[x]);//别忘了还有节点 x 的祖先!
if(max_part<ans) ans=max_part,pos=x;//更新重心
return;
}
signed main()
{
read(n);
for(int i=1;i<n;++i) read(x,y,w),add_edge(x,y,w);
dfs(1);
put(pos);
return 0;
}
-
注:代码中的
ly::max
用法与std::max
基本相同,「序——说明」中已作过解释。namespace ly
中,简单实现如下:namespace algorithm { auto max=[](const auto &x,const auto &y)->auto{return x>y?x:y;}; }using namespace algorithm;
类似的函数「如
ly::min
、ly::swap
等等」后文不再解释。
总体来说,链式前向星的思维复杂度稍高,但编程复杂度与邻接矩阵相差不大。由于其存储、访问的时间、空间复杂度远优于邻接矩阵,除有特殊说明外「如 Floyed、Prim、传递闭包等算法一般用邻接矩阵实现」,后文统一使用链式前向星存图。
广度优先遍历
「Breadth-First-Search,简称 BFS」
广度优先遍历是一种按照层次顺序进行访问的方法,需要一个队列实现。
【这里的队列我用的是 namespace ly::DS
中的已封装的手写队列,常数较小,与 STL 中的 queue
用法基本相同。也可以将代码中的 ly::DS::
去掉,引入头文件 <queue>
,直接使用 STL 实现的队列。这一点在「序——说明」已说明,后文不再赘述。】
过程
- 选择一个点作为起点。
- 将起点入队并标记为已访问。
- 若队列不为空,则队头出队,遍历以队头为起点的所有边。当遍历到一条终点未入队的边时,将终点入队并标记为已访问,继续遍历其他边。
- 重复第 \(2\)~\(3\) 步,当队列为空时,遍历结束。
代码实现
很显然,这个过程非常适合用链式前向星实现。
代码如下:
#define maxn 1010
#define maxm 1010
int n,m,x,y,w;
int cnt_edge,head[maxn];
class Edge{public:int val,to,next;}edge[maxm];
inline void add_edge(int x,int y,int w){edge[++cnt_edge].to=y,edge[cnt_edge].val=w,edge[cnt_edge].next=head[x],head[x]=cnt_edge;}
bool vis[maxn];
ly::DS::queue<int>q;
void bfs(int x)
{
q.push(x),vis[x]=1;
int y;
while(!q.empty())
{
x=q.front(),q.pop(),put(x,0);
for(int i=head[x];i;i=edge[i].next)
if(!vis[y=edge[i].to]) vis[y]=1,q.push(y);
}
}
signed main()
{
read(n,m);
for(int i=1;i<=m;++i) read(x,y,w),add_edge(x,y,w);
for(int i=1;i<=n;++i) if(!vis[i]) bfs(i);
return 0;
}
输入样例同前面「图论基础——图的存储」给出的例子。
拓扑排序
参考资料
- 李煜东《算法竞赛进阶指南》