第三章 图论与搜索一

普通 DFS 与 BFS

概述

DFS：深度优先搜索（Depth-First-Search）

BFS：宽度优先搜索（Breadth-First-Search）

DFS和BFS的对比

• DFS使用栈（stack）来实现，BFS使用队列（queue）来实现
• DFS所需要的空间是树的高度h，而BFS需要的空间是2^h （DFS的空间复杂度较低）

DFS不具有最短路的特性，BFS具有最短路的特性

DFS

DFS中的2个重要概念：

• 回溯：回溯的时候，一定要记得恢复现场
• 剪枝：提前判断某个分支一定不合法，直接剪掉该分支

DFS经典问题：

acwing - 842: 排列数字acwing - 843: n-皇后问题

BFS

算法框架

1. 插入一个初始状态到queue中
2. while(queue非空)
 2.1 把队头拿出来
 2.2 扩展队头
3. end

BFS经典问题：

acwing - 844: 走迷宫

树与图的存储

首先，树是一种特殊的图（无环连通图）。所以，这里只说图的存储即可。

首先，图分为2种，有向图和无向图。

有向图中2个点之间的边是有方向的，比如a -> b，则只能从a点走到b点，无法从b点走到a点。

无向图中2个点之间的边是没有方向的，比如a - b，则可以从a走到b，也可以从b走到a

通常，我们可以将无向图看成有向图。比如上面，对a到b之间的边，我们可以建立两条边，分别是a到b的，和b到a的。

所以，我们只需要考虑，有向图如何存储，即可。通常有2种存储方式:

• 邻接矩阵

  用一个二维数组来存，比如g[a,b]存储的就是a到b的边。邻接矩阵无法存储重复边，比如a到b之间有2条边，则存不了。（用的较少，因为这种方式比较浪费空间，对于有n个点的图，需要n2的空间，这种存储方式适合存储稠密图）

• 邻接表

  使用单链表来存。对于有n个点的图，我们开n个单链表，每个节点一个单链表。单链表上存的是该节点的邻接点（用的较多）

树与图的深度优先遍历

acwing - 846: 树的重心

树与图的宽度优先遍历

acwing - 847: 图中点的层次

拓扑排序

图的宽度优先搜索的应用，求拓扑序（拓扑序是针对有向图的）

1. 什么是拓扑序：将一个图的很多节点，排成一个序列，使得图中的所有边，都是从前面的节点，指向后面的节点。则这样一个节点的排序，称为一个拓扑序。
2. 若图中有环，则一定不存在拓扑序。
3. 可以证明，一个有向无环图，一定存在一个拓扑序列。有向无环图，又被称为拓扑图。

对于每个节点，存在2个属性，入度和出度。

• 入度，即，有多少条边指向自己这个节点。
• 出度，即，有多少条边从自己这个节点指出去。

所有入度为0的点，可以排在当前最前面的位置。

算法框架

将所有入度为0的点入队。
while(queue非空) {
	t = queue.pop(); // 获取队头
	枚举t的全部出边 t->j
	  删掉边t->j, j节点的入度减一
	  if(j的入度为0) 将j入队
}

练习题：acwing - 848: 有向图的拓扑序列