# 一、综述
深搜策略:在深搜过程中,对于最新发现的顶点,如果它还有以此为起点的而未探测到的边,就沿此边继续探测下去。当顶点v的所有边都已被探测过后,搜索将回溯到发现顶点v有起始点的那些边。
时间戳:当顶点v第一次被发现时记录下第一个时间戳d[v],当结束检查v的邻接表时,记录下第二个时间戳f[v]。v在d[v]时刻前是白色的,在时刻d[v]和f[v]之间是灰色的,在时刻f[v]之后是黑色的。
括号定理,后裔区间的嵌套,白色路径定理
边的分类:(1)树边(2)反向边(3)正向边(4)交叉边
对无向图G进行深度搜索时,G的每一条边,要么是树边,要么是反向边。
# 二、代码
### 1.Link_Graph.h
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter22/section22_3.cpp
### 2.main.cpp
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter22/section22_3Test.cpp
### 3.测试数据
书P335,图22-6
10 14
q s
s v
v w
w s
q w
q t
t y
y q
t x
x z
z x
u y
r y
r u
### 4.输出结果
见22.3-2
# 三、练习
### 22.3-1
关键是“任何时刻”
有向图
| | WHITE | GRAY | BLACK |
|-----|-----|-----|-----|
| WHITE | TBFC | BC | C |
| GRAY | TF | TFB | TFC |
| BLACK | | B | TFBC |
无向图
| | WHITE | GRAY | BLACK |
|-----|-----|-----|-----|
| WHITE | TB | TB | |
| GRAY | TB | TB | TB |
| BLACK | | TB | TB |
### 22.3-2
q:1 16
r:17 20
s:2 7
t:8 15
u:18 19
v:3 6
w:4 5
x:9 12
y:13 14
z:10 11
q->s: 树边
q->t: 树边
q->w: 正向边
r->u: 树边
r->y: 交叉边
s->v: 树边
t->x: 树边
t->y: 树边
u->y: 交叉边
v->w: 树边
w->s: 反向边
x->z: 树边
y->q: 反向边
z->x: 反向边
### 22.3-3
(u(v(y(xx)y)v)u)(w(zz))w)
### 22.3-6
[算法导论-22.3-6-用栈实现DFS](http://blog.csdn.net/mishifangxiangdefeng/article/details/7839628)
### 22.3-7
参考1楼所给的答案:
V={w,u,v}
E={(w,u), (u,w), (w,v)}
有一条从u到v的路径,即u->w->v
DFS的顺序为w,u,u,v,v,w,d[u]=2,d[v]=4,d[u]<d[v]
得到的森林中,u和v都是w的后裔
### 22.3-8
如图所示,(1)有一条从u到v的路径
![](https://box.kancloud.cn/2016-02-02_56b02bd37eab8.jpg)
### 22.3-9
貌似不用改
### 22.3-10
![](https://box.kancloud.cn/2016-02-02_56b02bd392fe1.gif)
### 22.3-11
联通分支的数量用ceil表示,代码修改如下:
~~~
void Link_Graph::DFS()
{
int u, ceil = 0;
//对每个顶点初始化
for(u = 1; u <= n; u++)
{
V[u].color = WHITE;
V[u].p = NULL;
}
//时间戳初始化
time = 0;
//依次检索V中的顶点,发现白色顶点时,调用DFS_Visit访问该顶点
for(u = 1; u <= n; u++)
{
if(V[u].color == WHITE)
{
ceil++;
DFS_Visit(u, ceil);
}
}
}
void Link_Graph::DFS_Visit(int u, int ceil)
{
int v;
Edge *e;
//将u置为灰色
V[u].color = GRAY;
//使全局变量time增值
time++;
//将time的新值记录为发现时间
V[u].d = time;
e = V[u].head;
while(e)
{
v = e->end;
//如果顶点为白色
if(V[v].color == WHITE)
{
//递归访问顶点
V[v].p = u;
DFS_Visit(v, ceil);
//树边
e->type = TREE;
}
else if(V[v].color == GRAY)
{
//反向边
e->type = BACK;
}
else if(V[v].color == BLACK)
{
//正向边
if(V[u].d < V[v].d)
e->type = FORWARD;
//交叉边
else
e->type = CROSS;
}
e = e->next;
}
//以u为起点的所有边都被探寻后,置u为黑色
V[u].color = BLACK;
V[u].ceil = ceil;
//并将完成时间记录在f[u]中
time++;
V[u].f = time;
}
~~~
### 22.3-12
单连通图没有正向边
- 前言
- 第6章 堆排序
- 6-3 Young氏矩阵
- 第7章 快速排序
- 第8章 线性时间排序
- 第9章 排序和顺序统计学算法导论
- 算法导论 9.1-1 求第二小元素
- 第10章 10.1 栈和队列
- 第10章 10.2 链表
- 第10章 10.3 指针和对象实现
- 第10章 10.4 有根树的表示
- 第11章-散列表
- 第12章 二叉查找树
- 第13章 红黑树
- 第14章 14.1 动态顺序统计
- 算法导论-14-1-最大重叠点
- 算法导论-14-2-Josephus排列
- 第14章 14.3 区间树
- 第15章 动态规划
- 第16章 贪心算法
- 第18章 B树
- 第19章-二项堆
- 第20章 斐波那契堆
- 第21章 用于不相交集合的数据结构
- 第22章 图的基本算法 22.1 图的表示
- 第22章 图算法 22.2 广度优先搜索
- 第22章 图算法 22.3 深度优先搜索
- 第22章 图的基本算法 22.4 拓扑排序
- 第22章 图的基本算法 22.5 强联通分支