1.概念题,比较麻烦,几个概念以前数据结构课没接触过
2.
没扫描仪...用手画不如杀了我得了...
用文字大概说明吧
按DFS定义,顺序是
q 4 8 10 9 3 6 7 2 5
数字含义是按图上字母顺序编号,比如q应该编为1号,t应该编为4号
然后对边来说
q->w为正向边(注:以下F表正向边,B表反向边,C表交叉边,T表树边)
w->s,y->q,z->x为B
r->y,u->y为C
其它为T
3.比较简单
(u(v(y(xx)y)v)u)(w(zz)w)
4.证明:
(1)由定理22.8
u是v的祖先,所以d[u]<d[v]<f[v]<f[u]成立时,(u,v)必然为树边或者前向边
反之,若(u,v)是树边或前向边,则
d[u]<d[v]<f[v]<f[u]显然成立(不清楚的话画画P333的图b)
(2)没等号的情况跟上题类似,有等号的情况没想通...
(3)
因为d[v]<f[v]<d[u]<f[u]
由此画出括号图,显然为交叉边...(好像有点勉强...)
OR
由d[v]<f[v]<d[u]<f[u]不满足(1)(2)中条件,所以不能为反向,树边或前向边,由此应为交叉边...(好像更勉强...求达人)
5.
6.代码题PASS掉
7. 郁闷了我,写一半maxthon挂掉...郁闷
从v搜.再搜P
8.没想出来
9.P334页有讲
if color[v]==WHITE
then (u,v)= T
if color[v]==GRAY
then (u,v)=B
if color[v]==BLACK
then (u,v)=C
10.
即使有入边也有出边,当u被探查以后已经被标为GRAY||BLACK,不会继续加入另一棵树
11.我实在写不出来数学的严格证明...当面讲应该能讲清楚...唉,数学差了害死人啊
12.看见星号直接跳过,过段时间来看