作者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