Question

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

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

单连通图没有正向边