h****e
发帖数: 928 | 1 书中声称结点不涂成灰色也不会影响算法的正确性。
我觉得这是有问题的：最短路径的长度不会有问题，但是要是
要打印出最短路径就会有问题。如下是一个简单的3个结点的
有向图：
R
/ \
/ \
v v
Y <----- U
假定BFS开始，所有结点都是白色。
从R开始，R->U, 然后R->Y，R涂成黑色。Y和U的父结点都是R。
现在到U，因为U没有涂成灰色，Y的父结点就变成U了。最后
在打印R到U的最短路径就变成R->U->Y。这显然是错的。
各位大虾看看我什么地方想错了吗？ |
h****e
发帖数: 928 | |
l*********8
发帖数: 4642 | 3 我觉得你说的没问题。
【在 h****e 的大作中提到】
: 书中声称结点不涂成灰色也不会影响算法的正确性。
: 我觉得这是有问题的：最短路径的长度不会有问题，但是要是
: 要打印出最短路径就会有问题。如下是一个简单的3个结点的
: 有向图：
: R
: / \
: / \
: v v
: Y <----- U
: 假定BFS开始，所有结点都是白色。
|
f**********2
发帖数: 2401 | |
h****e
发帖数: 928 | 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*********8
发帖数: 4642 | 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****e
发帖数: 928 | 7 明白了。多谢！
【在 l*********8 的大作中提到】
: 只需要 BLACK and WHITE. GRAY can be replaced by BLACK.
|
l*********8
发帖数: 4642 | 8 you're welcome
【在 h****e 的大作中提到】
: 明白了。多谢！
|
r****l
发帖数: 50 | 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********t
发帖数: 5706 | 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
|
s*w
发帖数: 729 | 11 我看有人的 code 里面用 set visited;只保存 visited
【在 c********t 的大作中提到】
: ls各位，如果vertex没有color field,是不是需要用visited hashset 代替？
|
c********t
发帖数: 5706 | 12 嗯，俺就是那个意思。
【在 s*w 的大作中提到】
: 我看有人的 code 里面用 set visited;只保存 visited
|
