作者aldreamp (小孟)
看板EE_DSnP
标题[问题] 请问大家讲义中DFS的fbList是用来做什麽的?
时间Tue Jan 11 17:09:42 2011
我在看讲义Topic 10的slide 30 DFS的 pseudocode
我可以了解dfsList用来存放按照post order traversal所经过的点
那想请问大家 fbList是用来存放麽用的呢?
-----------
void
Graph::dfsTraversal(const List<Node*>& srcList)
{
Node::setGlobalRef();
for_each_source(node, srcList)
node->dfsTraversal(_dfsList, _fbList);
}
// post order traversal
void Node::dfsTraversal
(List<Node *>& dfsList, list<Node*>&
fbList)
{
for_each_sucecessor(next, _successors) {
if (!next->isGlobalRef()) {
next->setToGlobalRef();
next->setActive();
next->dfsTraversal(dfsList, fbList);
next->unsetActive();
}
else if (next->isActive())
fbList.push_back(this, next);
}
dfsList.push_back(this);
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.94.109
1F：→ MrOrz:facebookList (被拖走 01/11 18:27
2F：推 TommyKSHS:我跟楼上想的一样 XXD 01/11 18:36
3F：推 MrOrz:看起来是当图里有圈圈的时候，纪录圈圈「接合」的地方 01/11 18:40
4F：→ MrOrz:一个 node 只有「正在遍历其子节点」的时候，isActive()为真 01/11 18:41
5F：→ MrOrz:所以撞到一个 isActive() 为真的点，代表侦测到圈了 01/11 18:42
6F：→ aldreamp:喔喔谢谢 01/16 16:57