系列文章目录

文章目录

• 一、DFS是什么？
• 二、DFS的基本框架
• 三、DFS-tree
• 四、图的基本知识

一、DFS是什么？

    DFS(Depth First Search) ，即 深度优先搜索 ，是一种遍历图的方式，对于下图（设从u开始访问）

若先访问了v点：

则下一步会访问v的子节点w点：
发现无路可走，则回溯回v，再回到u，之后前往x。
总结一下，dfs会在搜索到新点时优先访问以改点为起点的子节点，并在所有子节点访问完成后回溯，可以看出，dfs和递归殊途同归。
相反地，有BFS(Breath First Search)广度优先搜索，用bfs访问上例时访问顺序为：u,v,x,w，程序会访问完当前节点的所有子节点（不访问孙子节点），在依次访问孙子节点，一层一层向下搜。这里不细表。

二、DFS的基本框架

dfs需要用到递归思想，上代码：

//存图方式：vector(g[N])
void dfs(int u){//u:当前节点
	vis[u]=true;
	for(int& v:g[u]){//访问u连到的每个节点
		if(!vis[v]) dfs(v);
	}
}

当然，若是想发挥点作用，还需要许多补充。
和大部分递归代码一样，dfs的代码一般也超不过20行，只是重在理解。

三、DFS-tree

我们可以根据上面的代码将一个图改造成一个有向无环图（即树），这里先讨论无向图，对于：
可以dfs出：
注意其中绿边和蓝边的区别：

• 树边：dfs-tree树上的实边
• 回边：由子节点回到祖宗 (姑且这么叫) 节点，不应该在树上的虚边。
  注意：不存在连向非祖先的回边。

四、图的基本知识

这里主要讨论的是无向图。

• 表示一个图： G ( V , E ) G (V,E) G(V,E) ，其中， V V V和 E E E都是集合，表示顶点和边。
  顺带一提， ∣ S ∣ |S| ∣S∣表示集合S的 .size()
• 连通：我们称无向图G连通，当对于图上任意两点u,v，都可以找到至少一条 路径 使二点能互相到达。如：

• （无向图的） 连通分量：无向图的极大连通子图，即只要再加入任何一个点都会是该子图不再连通。
• 桥(即割边)：删掉该边后图的连通分量个数会增加，如：

  则A-E是一个桥。

马上我们会用tarjan算法求图的桥。