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

最后更新于:2022-04-01 07:36:07

# 一、综述 深搜策略:在深搜过程中,对于最新发现的顶点,如果它还有以此为起点的而未探测到的边,就沿此边继续探测下去。当顶点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://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-02-02_56b02bd37eab8.jpg) ### 22.3-9 貌似不用改 ### 22.3-10 ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/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 单连通图没有正向边
';