CLRS算法书中BFS的疑问 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

CLRS算法书中BFS的疑问

CLRS算法书中BFS的疑问# JobHunting - 待字闺中

h*e2012-04-12 07:04

1 楼

书中声称结点不涂成灰色也不会影响算法的正确性。
我觉得这是有问题的：最短路径的长度不会有问题，但是要是
要打印出最短路径就会有问题。如下是一个简单的3个结点的
有向图：
R
/ \
/ \
v v
Y 假定BFS开始，所有结点都是白色。
从R开始，R->U, 然后R->Y，R涂成黑色。Y和U的父结点都是R。
现在到U，因为U没有涂成灰色，Y的父结点就变成U了。最后
在打印R到U的最短路径就变成R->U->Y。这显然是错的。
各位大虾看看我什么地方想错了吗？

h*e2012-04-12 07:04

2 楼

自己顶一下。没有人帮忙看看吗？

l*82012-04-12 07:04

3 楼

我觉得你说的没问题。

【在 h****e 的大作中提到】

: 书中声称结点不涂成灰色也不会影响算法的正确性。
: 我觉得这是有问题的：最短路径的长度不会有问题，但是要是
: 要打印出最短路径就会有问题。如下是一个简单的3个结点的
: 有向图：
: R
: / \
: / \
: v v
: Y : 假定BFS开始，所有结点都是白色。

f*22012-04-12 07:04

4 楼

没看太明白。。。详细说说书中原话？

h*e2012-04-12 07:04

5 楼

谢谢longway2008的支持。
flyinocean12，下面是书中的BFS算法，s是开始结点。
BFS(G, s)
1 for each vertex u in G.V - {s}
2 u.color = WHITE
3 u.d = INFINITY
4 u.parent = NIL
5 s.color = GRAY
6 s.d = 0
7 s.parent = NIL
8 Q = {};
9 ENQUEUE(Q, s)
10 while Q<>{}
11 u = DEQUEUE(Q)
12 for each v in G.Adj[u]
13 if v.color==WHITE
14 v.color = GRAY
15 v.d = u.d + 1
16 v.parent = u
17 ENQUEUE(Q,v)
18 u.color = BLACK
然后练习题是这么说的：
Ex 22.2-3
Show that using a single bit to store each vertex color suffices by arguing
that the BFS procedure would produce the same result if lines 5 and 14 were
removed.

l*82012-04-12 07:04

6 楼

只需要 BLACK and WHITE. GRAY can be replaced by BLACK.

【在 h****e 的大作中提到】

: 谢谢longway2008的支持。
: flyinocean12，下面是书中的BFS算法，s是开始结点。
: BFS(G, s)
: 1 for each vertex u in G.V - {s}
: 2 u.color = WHITE
: 3 u.d = INFINITY
: 4 u.parent = NIL
: 5 s.color = GRAY
: 6 s.d = 0
: 7 s.parent = NIL

h*e2012-04-12 07:04

7 楼

明白了。多谢！

【在 l*********8 的大作中提到】

: 只需要 BLACK and WHITE. GRAY can be replaced by BLACK.

l*82012-04-12 07:04

8 楼

you're welcome

【在 h****e 的大作中提到】

: 明白了。多谢！

r*l2012-04-12 07:04

9 楼

my solution:
When line 5 and 14 are removed. Only need a bool value u.color;
Algorithm can modify as described, and also give the same result: (only
changes in the line numbered shows below)
2 u.color = True
5 u.color = False
13 if v.color == True
18 u.color = False

c*t2012-04-12 07:04

10 楼

ls各位，如果vertex没有color field,是不是需要用visited hashset 代替？

【在 r****l 的大作中提到】

: my solution:
: When line 5 and 14 are removed. Only need a bool value u.color;
: Algorithm can modify as described, and also give the same result: (only
: changes in the line numbered shows below)
: 2 u.color = True
: 5 u.color = False
: 13 if v.color == True
: 18 u.color = False