# 一、綜述
深搜策略:在深搜過程中,對于最新發現的頂點,如果它還有以此為起點的而未探測到的邊,就沿此邊繼續探測下去。當頂點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的路徑

### 22.3-9
貌似不用改
### 22.3-10

### 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 強聯通分支