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:: 去掉，并引入对应函数的头文件即可。

  • 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」

  1. 整数的两倍不超过 0x7fffffff，即 int 能表示的最大正整数。
  2. 整数的每 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\) 中边的集合。

例如：

「由于在 \(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;
}

图的遍历

定义&说明

图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。

——百度百科

重点有两个：

1. 每个顶点都要访问。
2. 每个顶点只访问一次。

因此，不论怎样实现图的遍历，都可以开一个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

• 过程

  1. 选择一个点作为起点。
  2. 将被选择的点标记为已访问。
  3. 遍历以被选择的点为起点的所有边，当找到一条终点末被访问的边
     时，访问该边的终点。
  4. 将终点作为已选择的点重复第 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\)」，则只能访问其本身，因为从该节点出发无法到达其他节点。
    • 即使要遍历的图是无向图也要这样做，因为图不一定连通！「极端情况是每个节点都没有连边。」
    • 因此要枚举每个节点作为起点，这样才一定可以访问到每个节点。

  • 时间复杂度

    访问 \(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 对每个节点的访问顺序。

  关于 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 实现的队列。这一点在「序——说明」已说明，后文不再赘述。】

• 过程

  1. 选择一个点作为起点。
  2. 将起点入队并标记为已访问。
  3. 若队列不为空，则队头出队，遍历以队头为起点的所有边。当遍历到一条终点未入队的边时，将终点入队并标记为已访问，继续遍历其他边。
  4. 重复第 \(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;
  }
  

  输入样例同前面「图论基础——图的存储」给出的例子。

拓扑排序

参考资料

• 李煜东《算法竞赛进阶指南》

返回顶部

bottom

原文地址：http://www.cnblogs.com/lingyunvoid/p/graph.html