作者saladim (杀拉顶)
看板CSSE
标题[问题] 又是看书的问题
时间Sun Jul 24 22:23:03 2011
看书又看到卡住 请大家帮忙解惑阿~~~~
所看的书是 Algorithms in C++ by Robert Sedgwick, 第18章的DFS小节(18.4)
里面提到:
We refer to a link from v to w in a DFS tree that represents a tree edge
as :
A tree link if w is unmarked
A parent link if st[w] is v <----------问题在这点
请参考书上的图:
http://ppt.cc/Eg@y (抱歉....换成短网址)
我的问题在於 当走到 2-0 这个DFS TREE LINK时(有接到阴影的圆圈那个), 按照我的
理解应该是这样:
v = 2 , w = 0 st[0] = 0 , 所以2-0不是parent link!!!!
但是这个结论很明显的错了.
所以这边我的疑惑是没有一个可以自圆其说的方式来决定谁是v 谁是w, 能让我带入检查
的条件里面, 用以决定某条DFS TREE LINK是那种Link.......
上面举的例子只是提到parent link, 若是加上其他的link type, v/w的定义又好像
没有一个一致的定义使的我们可以遵循..............
可以帮忙提示哪边是思考的重点或是盲点吗?? 这边想了很久还没破关.....
感激不尽!!! 谢谢!!!
{若是单独去想或是用程式去想 都可以做的出来 可是想去想通这套系统.....)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.43.192.170
1F：推 micklin:看不到图...preview不给看啊, 不知道你说的地方在哪... 07/25 00:26
2F：→ firejox:短网址... 07/25 00:45
3F：→ firejox:st[w] 的v应该是指的是visit 07/25 00:46
4F：→ firejox:st的意思是state吧 07/25 00:48
书上定义st[w]为node w 的parent是哪个node
※ 编辑: saladim 来自: 114.43.192.170 (07/25 01:44)
5F：推 micklin:可以把全文写一写吗?搞不好书写错了.... 07/25 03:42
6F：→ firejox:应该是当走到2-0时v=0 w=2 st[w]=0 07/25 10:35
7F：→ firejox:他那个是以0先出发 07/25 10:35
8F：→ firejox:那段的意思是指v到w的这条边是属於DFS tree的其中一条 07/25 10:49
9F：→ firejox:要是w还没遍历 以及w的parent是v 才是tree的其中一条边 07/25 10:56