第22章 图算法 22.3 深度优先搜索

# 一、综述 深搜策略：在深搜过程中，对于最新发现的顶点，如果它还有以此为起点的而未探测到的边，就沿此边继续探测下去。当顶点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 单连通图没有正向边