U536107 2.15图论总结

# 图 ## 一、图是什么 图指的是**存在点和边的图形** 边是用来表示**点与点之间连接关系**的 点的数量至少为 $1$，边的数量可以为 $0$ 图分为 $2$ 种： - **有向图**，图内所有边都是有向边  - **无向图**，图内所有边都是无向边  在以后我们还可能学到**混合图**，即为图中所有边由有向边和无向边组成 ## 二、图的特殊组成部分 ### 1. 环 在图中从点 $1$ 出发，**可以回到自身**，说明该图存在一个 **$1$ 点上的环**，如下图：  还有**自环**，即**自己到自己**的环，表示如图：  ### 2. 重边 就是**同起点同终点存在多条边**，表示如图 ( 点 $1$ 与点 $2$ 之间有重边 )：  ## 三、图的度 **度**在**无向图**中表示对于某节点**直接连接的边的数量** 而在**有向图**中： - **入度：** 一个点的入度即**指向自己的边的数量** - **出度：** 一个点的出度即**从该点出发的边的数量** 简单好理解，不再附图 ## 四、图的存储方式 **写在前面：** 设我们讨论的图有 $n$ 个点，$m$ 条边 ### 1. 邻接矩阵 创建一个二维数组，```G[][]``` 如果输入表示 $a$ 到 $b$ **存在边**： - 若该边为有向边，则 ```G[a][b] = 1;``` - 若该边为无向边，则 ```G[a][b] = 1; G[b][a] = 1;``` 如果输入表示 $a$ 到 $b$ **不存在边**：则 ```G[a][b] = 0;``` 也可**用邻接矩阵存边权**：```G[a][b] = w; vis[a][b] = 1``` $\color{red}优点：$ 查询边时**方便** $缺点：$ ①不能**直接**存储重边情况 ②空间太大 $O(n*n)$ ,**只适合稠密图** ### 2. 邻接表 此类方法的本质是**用点之间的关系存储边** 创建 $n$ 个一维数组 ```vector G[]``` 如果输入表示 $a$ 到 $b$ **存在边**： - 若该边为有向边，则 ```G[a].push_back(b);``` - 若该边为无向边，则 ```G[a].push_back(b); G[b].push_back(a);``` 如果输入表示 $a$ 到 $b$ **不存在边**：则不做操作 $\color{red}优点：$ 可快速输出 $a$ 的所有直接边，无空间浪费，可存重边可自环 $缺点：$ 判断 $a->b$ 是否存在边时很慢，空间复杂度 $O(m log m)$ ## 五、图上搜索 ### 1. DFS深度优先搜索 其实我们依旧可以使用原来的**深搜**模版： ```cpp void dfs(/*节点参数*/) { if(/*到达边界*/) { // 更新答案 return ; } /* 此处可写剪枝优化或记忆化代码 */ vis[/*当前节点*/] = 1; // 打标记 for(/*所有下一个可能解*/) { if(vis[/*可能的下一个节点*/] == 1) continue; dfs(/*下一个可能节点*/); vis[/*可能的下一个节点*/] = 0; // 回溯（在一些题目中无需此操作） } return ; } ``` 但在图论中，我们要在开始搜索前**建图**（即存储图）。因为有两种图的存储方式，自然搜索也有**两种写法**。在解决问题时，我们要根据题目对**时间空间**的要求选择合适的存储方式和搜索写法。 ### 2. BFS广度优先搜索 和深搜一样，也可以借鉴以前的模版： ```cpp void bfs(/*起始节点参数*/) { queue q; // 在图论中，往往使用结构体来存储节点（假设有一 node 结构体） bool vis[]; // 标记数组 vis[/*起始节点*/] = 1; q.push(/*起始节点*/); while(q.size()) // 如果队列不为空，则还可以继续搜索 { node now = q.front(); // 取出当前节点 q.pop(); // 弹出即表示该节点已被考虑，在以后的搜索中不再使用该节点 if(/*到达目标*/) { // 输出答案 break; } for(/*遍历所有可以在当前节点的基础上一步走到的节点*/) { int nw;// 设下一节点有可能是 nw if(vis[nw]) continue;// 考虑过就不在考虑 if(/*题目还有其他不合法条件*/) continue; q.push(/*nw 节点的信息*/); vis[nw] = 1;// 标记 } } return ; } ``` ### 3. 举例分析 此处我们以 [P5318 【深基18.例3】查找文献](https://www.luogu.com.cn/problem/P5318) 举例进一步分析图上深广搜： ### 题意分析 题目大意为让我们根据输入来建图，并输出深搜和广搜的结果 ### 题目详解 总体而言，有以下几步 - 建图 - 深搜 - 广搜 **1. 建图** 明显，本题题面表示图为**有向图**，且如果有很多篇节点可以遍历，先搜编号较小的节点，由此，本题使用邻接表更好。不考虑重边、自环。开始建图： ```cpp int n, m; // 节点数 边数 int x, y; // 起点 终点 cin >> n >> m; for (int i = 1; i > x >> y; G[x].push_back(y); // 有向图 } for (int i = 1; i

无

无

无

# 附 深度优先搜索 [题单 1](https://www.luogu.com.cn/training/590444) [题单 2](https://www.luogu.com.cn/training/590451) 广度优先搜索 [题单 1](https://www.luogu.com.cn/training/710363)