《算法导论》22.3 深度优先搜索（含C++代码）

一、相关概念

1、就是尽量“深入”搜索，一旦v的所有出发边都被发现，搜索就会回溯到v的前驱结点（v是经过该结点才被发现的），来搜索这个前驱结点的出发边。这个过程持续到源结点可以达到的所有结点为止。
2、class="superseo">深度优先搜索的前驱子图形成一个由多棵深度优先树构成的深度优先森林。

3、像广度优先搜索算法一样，深度优先搜索算法在搜索过程中也是对结点进行涂色来指明结
点的状态。每个结点的初始颜色都是白色，在结点被发现后变为灰色，在其邻接链表被扫描完成后变为黑色。该方法可以保证每个结点仅在一棵深度优先树中出现，因此，所有的深度优先树是不相交的(disjoint)。
4、除了创建一个深度优先搜索森林外，深度优先搜索算法还在每个结点盖上一个时间戳。每
个结点v有两个时间戳：第一个时间戳v.d记录结点U第一次被发现的时间(涂上灰色的时候)，第二个时间戳v.f记录的是搜索完成对U的邻接链表扫描的时间(涂上黑色的时候)。
5、伪代码中u.d为发现结点u的时刻；u.f为完成对结点u处理的时刻。因为每一个结点都只有一次被发现和一次被完成的事件，因此时间戳都是介于1~2|V|之间的整数。对于每个结点u，有u.d u在u.d之前为白色，u.d和u.f之间为灰色，u.f之后为黑色。

DFS(G)
//进行初始化
for each vertex u ∈ G.V
	u.color = WHITE
	u.π = NIL
time = 0	//置时间为0
for each vertex u ∈G.V	//对于每一个结点，发现有结点颜色为白色，那么就进行“visit”
	if u.color == WHITE
		DFS-VISIT(G,u)

DFS-VISIT(G,u)
time = time + 1	//白色结点已经被发现，更新（更新是发现时和结束时各更新一次）
u.d = time
u.color = Gray
for each v ∈ G:Adj[u]	//递归访问结点v
	if v.color == WHITE	
		v.π = u
		DFS-VISIT(G,v)
u.color = BLACK	//将u赋为黑色，因为已经结束，递归中也会逐步这么返回
time = time + 1	//更新时间
u.f = time	//记录时间

二、深度优先搜索的性质

1、最基本的性质：前驱子图形成一个多棵树构成的森林，因为深度优先树的结构和DFS-VISIT递归调用结构完全对应。
2、括号化结构，比如左括号代表开始，右括号代表结束。

三、边的分类

对于在图G上运行深度优先搜索算法所生成的深度优先森林G_π，我们可以定义4种边的类型:
1.树边:为深度优先森林G_π中的边。如果结点v是因算法对边(u，v)的探索而首先被发现，则(u, v)是一条树边。
2.后向边:后向边(u, v) 是将结点u连接到其在深度优先树中(一个)祖先结点v的边。由于有向图中可以有自循环，自循环也被认为是后向边。
3.前向边:是将结点u连接到其在深度优先树中一个后代结点v的边(u,v)。
4.横向边:指其他所有的边。这些边可以连接同一棵深度优先树中的结点，只要其中一个结点不是另外一个结点的祖先，也可以连接不同深度优先树中的两个结点。

四、C++代码

#include 
using namespace std;
#include 
#include 
#include 
#include 

//枚举三种颜色
enum Color{white=0,gray,black};

//定义定点
struct Vertex
{
	enum Color color;
	int d; //开始时间
	int f;	//结束时间
	Vertex* pre;//前驱结点
	char name;
	Vertex(char n):name(n),color(white),d(0),f(0),pre(NULL){}
};

//定义图
struct Graph
{
	vector<Vertex*>v;	//顶点集合
	map<char, list<Vertex*>>Adj;//邻接链表
};

//初始化图以及邻接链表
Graph Init_graph()
{
	Graph G;
	G.v = { new Vertex('u'),new Vertex('v'),new Vertex('w'),new Vertex('x'),new Vertex('y'),new Vertex('z') };
	//初始化邻接链表
	G.Adj['u'] = { G.v[1],G.v[3]};
	G.Adj['v'] = { G.v[4] };
	G.Adj['w'] = { G.v[4] ,G.v[5] };
	G.Adj['x'] = { G.v[1] };
	G.Adj['y'] = { G.v[3] };
	G.Adj['z'] = { G.v[5] };
	return G;
}

void Dfs_visit(Graph g, Vertex* u, int time);
//深度优先搜索
Graph Dfs(Graph g)
{
	int time = 0;
	for (int i = 0; i < g.v.size(); i++) {
		if (g.v[i]->color == white) {//发现白色结点就开始访问
			Dfs_visit(g, g.v[i], time);
		}
	}
	return g;
}

//递归访问，上一个函数的子函数
void Dfs_visit(Graph g, Vertex* u, int time)
{
	time = time + 1;
	u->d = time;//记录开始时间
	u->color = gray;//更新颜色
	char n = u->name;
	//深层次递归遍历
	for (Vertex* v : g.Adj[n]) {
		if (v->color == white) {
			v->pre = u;
			Dfs_visit(g, v, time);
		}
	}
	u->color = black;//结束对u的访问,u所有可以到的都访问了
	time = time + 1;
	u->f = time;
}

//打印路径
void print_path(Graph g, Vertex* ve, Vertex* v)
{
	//如果v和ve相等，那么直接打印
	if (v == ve) {
		cout << v->name << " ";
	}
	else if (v->pre == NULL) {
		cout << "Can't find the path..." << endl;
	}
	else {
		print_path(g, ve, v->pre);
		cout << v->name << " ";
	}
}

int main()
{
	Graph g = Init_graph();
	Dfs(g);
	print_path(g, g.v[0], g.v[3]);
	return 0;
}