上课信息

日期：2026/07/06

授课老师：MysGln

课堂笔记

有向图和无向图

区别：有向图的边有方向，无向图的边没有方向

A -- B
A --> B

教师补充：方向是规定了只能单向通过，之所以要区分有向图和无向图，是因为某些算法只适用于有向图或者无向图

例如拓扑排序，只适用于 $DAG$ （有向无环图），例如度的计算

（重点）度的计算及其性质

这里要区分有向图、无向图的计算方式

无向图的计算

一条无向边一定产生两个度的贡献。因此，在无向图中，所有顶点的度数之和等于边数的两倍。

应用：给定总度数求边数，或者反过来给定总边数求总度数

有向图的计算

一条有向边，会产生入度和出度，各加一。

入度：指向“我”的

出度：从“我”出去的

在有向图中，所有顶点入度之和等于边数，所有顶点出度之和也等于边数。

（重点）连通图及其连通分量

同样也区分有向图和无向图：

• 有向图的连通图被称为强连通图，强连通分量
  • 弱连通图：如果一个强连通图中的边变成无向边，可以成为连通，那么就可以称为弱连通图
• 无向图的连通图被称为连通图，连通分量

连通性

在无向图中，如果任意下、两个顶点之间都能通过若干条互相到达，就是说这个图是连通图

如果这个图是连通的，那么说明任意两个点之间都能沿边走到。

比如说：

A -- B -- C -- D

如果整个图不连通，被分割成若干个块，这若干个块中如果也能维持连通性（即相互之间可以互相到达），那么我们称这些块为连通分量（连通块）

A -- B C --D

结论：对于一个 n 个顶点的无向图要保证其连通性，至少需要 n - 1 条边（即链表、树的形式）。

变式一：给定一个图 G，里面有 n 个点，n - 1 条边，能否说明它的连通性？

答案：不能，因为无法判断是否所有顶点都被接在了一起，最坏的情况是 n - 1 条边都是自环 (U, U)

变式二：给定一个无向图 G，并且附带两个条件：

1. 图 G 是个连通图
2. 图 G 有 n 个顶点和 n - 1 条边

能否说明它一定是一棵树？

答案：可以。

经典例题：给定一个无向连通图 G，里面有 n 个顶点和 m 条边，我至少需要删多少条边才能使得它变成一个棵树？

答案：利用树的边数限制求解，答案为 $m - n + 1$

完全图和相应的计算

完全图：任意两个不同顶点之间都有一条边直接相连

A - B  A - C  A - D
B - C  B - D
C - D

计算公式：n 个顶点的简单无向完全图有 $C(n,2)$ 条边。

$$C(N,2) = \frac{N \times (N-1)}{2}$$

设问方式：给定一个简单无向图，求解最多能有多少条边？

看懂题目的暗示：简单图意味着没有重边和自环，所以边数不能无限增加

等价于在问一个 n 个顶点的简单无向完全图有多少条边，答案是确定的。

图的存储方式

通常来说有以下三种：

1. 邻接矩阵
2. 邻接表
3. 链式前向行

在复赛环节，用的最多是后两者，邻接矩阵一般只出现在初赛。

邻接矩阵

用二维数组来表示图的关系，即点与点之间是否存在边。

利用的是数组的 $O(1)$ 随机访问特性来实现，行和列分别表示点 u, v

代码定义，要记住它的名称和限制条件，显然二维数组不可能开太大，限制在 $5000$

int g[N][N]; // [点1][点2]

掌握常见的使用方式：

1. 判定 U, V 之间是否存在一条边，如果存在的话边权是多少

g[u][v] = 1; // 说明 u 和 v 之间存在一条边，边长可能为 1
g[u][v] = 0 / -1; // 说明不存在一条边
g[u][v] = 正整数; // 说明存在一条边且存在边长

2. 获得点 U 能到达的所有点 V，时间复杂度为 $O(N)$，必须全循环一次

for (int i = 1; i <= n; i++) {
  if (g[u][i] != 0) {
    cout << u << " -- " << i << endl; 
  }
}

3. 计算点 U 的度数（无向图）

int sum = 0;
for (int i = 1; i <= n; i++) {
  if (g[u][i] != 0) {
    sum++;  
  }
}

4. 计算点 U 的度数（有向图）

int in = 0, out = 0;
for (int i = 1; i <= n; i++) {
  out += (g[u][i] != 0);  
}
for (int i = 1; i <= n; i++) {
  in += (g[i][u] != 0);  
}
int tot = in + out;

邻接表

可以看成是若干个单链表的连接，每一个表头向后延伸的数据都表示从该点出发，能到达谁

[1] -- [?] -- [?]
 |
[2] -- [?]
 |
[3]

所以天然的，我们需要一个数据结构，支持动态向后追加元素 —— vector。

1. 定义一个邻接表，总点数为 N

// 无边权的图
vector<int> g[N]; // 开了 N 个vector<int>
// 有边权的图，用结构体或者pair来实现
// first -- v second -- w
// 更推荐反过来 first -- w, second -- v
// 好处是排序的时候，可以按照边权大小来排序
vector<pair<int,int>> g[N];

2. 加边操作

g[u].push_back(v); // 有向边
g[v].push_back(u); // 无向边 + 2 次不要忘记
// 有边权
g[u].push_back({w,v});
g[v].push_back({w, u});

3. 对顶点 U 全遍历

for (int i = 0; i < g[u].size(); i++) 

for (a uto it : g[u]) {
  
}

图的搜索

分为 DFS（深度优先搜索）、BFS （广度优先搜索）

初赛里面会给定一张图 G，询问下列哪种 DFS/BFS 顺序是对的

DFS

通常以递归函数的形式出现，特点是一条路走到黑再回头，走无可走，选无可选，才会回溯。

通常需要访问/标记作用的数组，命名通常为 vis

DFS 在统计最优答案的时候，最常用的方法是打擂法 —— 所有可能性都计算出来后才能知道最优结果。

// 全遍历图并染色
int color[N];
void dfs(int u, int col) {
  // 进入本层要做的事情  
  color[i] = col;
  // 开始查找以 u 为顶点，能到达的所有点 v
  for (auto u : g[u]) {
    if (color[v] == 0) { // 判断是否已经走过
      dfs(v, col); // 没有走过就走
    }
  }
  // 总结性操作通常在递归完成后实现，例如统计左右儿子信息
  // 这一步通常指的是底下信息已经计算完毕，回到本层的时候要做的事情
}

BFS

特点是：一次性扩展所有能走的路，需要借助队列这个数据结构

它可以求解边权为 1 的图的最短路，当我第一次到达终点的时候，一定是最优解。

边权为 1 可以认为是单次操作的代价，如果所有操作代价均相同，也可以考虑使用 BFS 来获得最少的操作次数。

相当于每次扩展，都能知道未来包不包含终点，所以不需要像 DFS 一样，我必须走完所有终点才能知道最短路。

int color[N];
void bfs(int start, int col) {
  queue<int> q;
  // 起点入队，作为启动
  q.push(start);
  color[start] = col;
  // 只要队列非空，一直进行
  while (!q.empty()) {
    // 1. 取出队首元素
    auto u = q.front();
    // 2. 出队队首元素
    q.pop();
    // 3. 扩展队首能到达的所有状态点 v
    for (auto v : g[u]) {
      if (color[v] == 0) {
        // 4. 合法情况入队，入队之后标记它已经入队
        color[v] = col;
        q.push(v);
      }
    }
  }
}