图论学习总结

ShiRoZeTsu · 2023-09-26 21:14:27 · 个人记录

本文是笔者 2023 CSP-S 复习写的博客，主要是总结知识点用，如有遗漏或不准确，还请海涵。

图论

OI 中关于图论的考查内容很多，很杂，很广泛。这里从浅入深地，循序渐进地讲解一些图论知识。

Part1 初识图论

什么是图？

图，是由若干个结点，结点之间有若干条边的数学模型。

不妨举个例子。

这是一个 7 个结点的图，图中共有 7 条边。

借助此图，我们来介绍一些关于图的概念。

• 图的连通性：如果一个图中任意两点都直接或间接相连，则这个图是一个连通图（如上例）。
• 点的度数：对于一个点，与其相连的边数即为其度数。比如点 4 的度数是 2，点 5 的度数是 5。
• 有向图与无向图：对于一个图，如果其边有方向，则为有向图；否则为无向图。

如上例，这个图就是一个无向图。

现在我们来给这些边加上方向：

如图，每条边都有一个方向，因此这个图是一个有向图。

当然，在有向图中，我们一般会把边分为两种：

• 入边：对于一个点 v，一条指向 v 的边，是 v 的一条入边。
• 出边：对于一个点 v，一条从 v 出发的边，是 v 的一条出边。

相应地，我们也把度数分成两种：

• 入度：对于一个点 v，v 的入边数，即为点 v 的入度。
• 出度：对于一个点 v，v 的出边数，即为点 v 的出度。

如上图，点 5 的入度为 1，出度为 4；点 2 的入读为 2，出度为 1。

此外，若有向图中存在一个点，可以从一条路径出发，走回到自己，那么我们称这个是一个有环图。

比如点 2 可以走 2 -> 4 -> 5，那这就构成了一个环，这个图就是一个有环图。

对于一个有向无环图，我们简称为DAG。

Part2 图的存储

如何存储一个图？

不难发现，在最普通的图中，我们所需要存储的信息即为边的连接情况。

以有向图为例。

还用刚刚这个图：

邻接矩阵

我们可以记录两个点之间是否有边：开一个二维数组，用 a[u][v] 来表示是否存在一条从 u 走到 v 的边。

显然，a[5][2] = true，a[1][3] = false。

代码示例：

for(int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    a[u][v] = true;
}

这样的方法称之为邻接矩阵，不过这种方法耗空间，耗时间，费时还费力，几乎不会使用。

所以我们可以考虑第二个方案。

vector 存图

每个点都开一个 vector，来存储这个点相邻的可以到达的点。

比如遇到了一条边 u 到 v，那么我们就让 edge[u].push_back(v)，其中 edge[u] 表示点 u 的 vector。

这样，空间的浪费会大大减少，时间效率也可以有很大的提高。

代码示例：

for(int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    edge[u].push_back(v);
}

在遍历每个点的出边时：

//比如要遍历 u 的所有出边：
for(int i = 0; i < edge[u].size(); i++) {
    int v = edge[u][i];
    //v 代表一条出边的末端点
}

但这依然不是我们最常见的存图方式。

链式前向星

这个可以说是最最常用的存图方式了，请务必将板子一字不差地背下来。

链式前向星的基本思路是开 n 个链表，第 i 个链表代表第 i 个点的出边集合。

每个点的出边维护一个向下的指针，每个点再维护一个头指针。

没看懂没有关系，可以直接背板子，板子很短。

代码示例：

struct edge {
    int to, nxt;
    //to 表示这条边的终点，nxt 表示下一条边的指针
} e[maxm];

int tot, head[maxn];
//tot 表示当前边的总数，head[i] 表示第 $i$ 个点出边的头指针
void add(int u, int v) {
    e[++tot].to = v;
    e[tot].nxt = head[u];
    head[u] = tot;
}

在遍历每个点的出边时：

//比如要遍历 u 的所有出边：
for(int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    //v 代表一条出边的末端点
}

使用这种方法的优点是，空间小，时间小，灵活，操作方便。相较于上两种方法，这种方法是最快的。

有时，一个图上的点可能有点权（就是这个点上带一个数字），一个图上的边也可能有边权（就是这条边上带一个数字）。

遇到边权时，链式前向星的板子可以写成这样：

struct edge {
    int to, w, nxt;
} e[maxm];

int tot, head[maxn];
void add(int u, int w, int v) {
    e[++tot].to = v;
    e[tot].w = w;
    e[tot].nxt = head[u];
    head[u] = tot;
}
//w 代表边权

如果是点权的话，直接开一个数组记录每个点点权，即可。

Part3 图的遍历

如何将整个图都扫一遍呢？

常见的方法是 dfs（深度优先搜索） 和 bfs（广度优先搜索）。

• dfs

  不妨假设 1 为整个图的起点（即 1 的入度为 0），假设这个图是一个 DAG。

  那么 dfs 就很好写了：

  void dfs(int u) {
      for(int i = head[u]; i; i = e[i].nxt) {
          int v = e[i].to;
          dfs(v);
      }
  }

• bfs

  可以类推 dfs 的写法，写出 bfs：

  void bfs() {
      queue<int> q;
      q.push(1);
      while(!q.empty()) {
          int u = q.front(); q.pop();
          for(int i = head[u]; i; i = e[i].nxt) {
              int v = e[i].to;
              q.push(v);
          }
      }
  }

应用

我们来找几个例题吧。

例 1. 给定一个 n 个点，m 条边的有向无环连通图，保证 1 号点入度为 0，求图中以每个点为起点的路径数（自己到自己也算一条路径）。

不妨开一个数组 cnt，用 cnt_u 来表示以点 u 为起点的路径数。

如果存在一条边 u 到 v，那么以点 v 为起点的路径，点 u 也能走，所以 cnt[u] += cnt[v] 就可以了 。

dfs 即可。

主要程序：

void dfs(int u) {
    cnt[u] = 1;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        dfs(v);
        cnt[u] += cnt[v];
    }
}

例 2. 给定一个 n 个点，m 条边的有向连通图，保证 1 号点入度为 0，请判断这个图是不是一个 DAG。

上一题直接给定了一个 DAG，而这道题让我们判断是不是 DAG，实际上就是判断这个图有没有环。

我们还是拿最开始的那张图。

让我们动手从 1 开始模拟一下 dfs 的过程。

• 当前结点：1；
• 走路径 1 -> 2，当前结点：2；
• 走路径 2 -> 4，当前结点：4；
• 走路径 4 -> 5，当前结点：5；
• 走路径 5 -> 2，当前结点：2；

停！

我们从 2 走到了 5，现在又走到了 2，而 2 此时还在栈中。

这说明什么？

我们已经找到了一个环。

也就是说，这个图不是一个 DAG。

总结方法就是，如果我们 dfs 走到了一个还正在递归的结点，这说明找到了环，那么我们此时就可以返回 false 了。

可以开一个数组 vis，当 vis_u = 0 时，表示 u 还没有遍历；当 vis_u = 1 时，表示 u 已经全部遍历完；当 vis_u = -1 时，表示 u 正在递归。

主要参考代码

bool dfs(int u) {
    if(vis[u] == -1) return false;
    //u 正在递归，出现了环
    if(vis[u] == 1) return true;
    //u 已经走过，不用再走了
    vis[u] = -1;
    //将 u 设置为正在递归

    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(!dfs(v)) return false;
    }
    vis[u] = 1;
    //u 已经递归完毕
    return true;
}

Part4 图的更细的分化

图只分为有向图和无向图吗？

显然不仅仅是这样。

也许你见过下面这样的图：

这种类似于一个倒悬的树的图，我们称之为树。

一棵树有什么呢？

它有树根，有子树，还有叶子，有......

有很多。我们一一来介绍。

• 树根：也就是一棵树的根结点，一般习惯放在最上面。显然，一棵树最多有一个树根。例如图中的 1。
• 叶子：树上度数为 1 的非根结点，称为叶子，也叫叶结点。例如图中的 5, 6, 7, 8。
• 孩子/儿子：如果把根结点放在最上面的话，一个结点的孩子/儿子就是它下面相邻的结点。比如 4 的儿子有 7 和 8。
• 父亲：如果 v 是 u 的儿子，那么 u 就是 v 的父亲。例如 7 和 8 的父亲都是 4。除根结点外，每个结点有且仅有一个父亲。
• 祖先：对于结点 u，在 u 与根结点之间的路径上的点，都是 u 的祖先。换句话说，u 的父亲是 u 的祖先（有点诡异），u 的父亲的父亲（爷爷）也是 u 的祖先，u 的父亲的父亲的父亲也是 u 的祖先，u 的父亲的父亲的父亲的父亲也是 u 的祖先......
• 深度：一个结点 u 与根结点的路径上的点的数量，就是点 u 的深度。比如图中，7 和 8 的深度都是 3，4 的深度是 2。
• 子树：对于树上任意一个结点 u，如果以 u 为根结点新建一棵树，那么这棵树就是原树的一棵子树。

以上概念都是非常常用的，建议感性理解一下。

细心观察的你可能发现了，图中这棵树上的边都是没有方向的。也就是说，树实际上是一个无向图。

唉？那怎么区分一个无向图是不是树呢？

再观察一下这张图：

发现了什么没？

没有？可以翻一下上面对于树的一些概念的介绍：

除根结点外，每个结点有且仅有一个父亲。

想到了吗？

没错，除根结点外，每个点和父亲只有一条连边。

也就是说，如果一个连通的无向图有 n 个点，那么只要这个图有恰好 n-1 条边，那么这就是一棵树。

很好理解对吧。

那么就让我们做一些习题吧。

例 3. 给定一个 n 个点的树，令 1 为根结点，请求出每个结点的子树大小（即子树中共有多少个点）。

输入：第一行一个正整数 n，接下来 n-1 行，每行两个整数 u 和 v 表示 u 和 v 之间有一条边。

首先输入这个树。

唉？无向图怎么存边呢？

无向图，实际上就是双向都有，加边的时候正反各加一遍就好。

for(int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    add(u, v); add(v, u);
}

当然，你要注意，无向图中，链式前向星存边的数组要开 2 倍（因为每个边都正反加了两次）。

struct edge {
    int to, nxt;
} e[maxn<<1];

接下来祭出 dfs 大法。

由于指定了根结点是 1，所以直接 dfs(1) 就好了。

考虑 dfs 怎么写。

假如 u 是 v 的父亲，而 v 的子树大小我们已经求出来了，那么怎么求 u 的子树大小呢？

v 是 u 的儿子，那么 v 的子树，自然也是 u 的子树的一部分。（子树的子树）

所以用 sze 来表示每个结点子树大小的话，sze[u] += sze[v] 即可。

别忘了初始时设所有 sze 都为 1。（自己也算自己子树内的结点）

还有，因为这是无向图，而我们之前存边时，每个边正反存了两次。所以在 dfs 时，需要判断走的这条边有没有走到了父结点。

父结点刚走到你，你又走回来了。

void dfs(int u, int fa) {
    //fa 表示 u 的父结点
    sze[u] = 1;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(v == fa) continue;
        //不能走回父亲结点
        dfs(v, u);
        sze[u] += sze[v];
    }
}

最后输出即可。

关于树的其它知识点，我会在后面的文章写出来。

虽说还没有开写啦

还是回到我们的 DAG。

Part5 拓扑排序

实际上就是让图的遍历顺序合理一些。

先给出一个例题。

P1137 旅行计划

链接

形式化题意：给定一个 n 个点，m 条边的 DAG，求以每个点为终点的最长路径的长度。

一个朴素的想法是，用 ans_u 来表示点 u 的答案。如果存在一条边 u 到 v，那么 ans_v 就是 ans_u+1.....吗？

想一个例子：假如存在两条边，1 到 3 和 2 到 3，且 ans_1 = 1，ans_2 = 2。

此时 ans_3 应该是多少呢？

是 ans_1 + 1 = 1 + 1 = 2 吗？显然不是。