DFS圖形記錄路徑（尋路）

Question

我已經實現了一個簡單的DFS（非遞歸），如果存在StartNode和EndNode之間的路徑，它將'測試'。它按預期工作（處理雙向/方向圖） - 但我無法弄清楚如何存儲路徑供以後使用。

目前我調試打印訪問節點，但它不是什麼應該存儲。

有人可以幫我解決一些問題 - 我應該存儲什麼以及在哪一點返回NodeStart到NodeEnd的節點列表？

這裏的例子圖表：

這裏是DFS遍歷功能：

bool DFS(CNavigationGraph *pNavGraph, CNavigationGraphNode* pFromNode, CNavigationGraphNode* pToNode) 
{ 
    assert(pNavGraph); 
    assert(pFromNode); 
    assert(pToNode); 

    std::vector<CNavigationGraphNode*> vpVisitedNodes; 
    std::vector<CNavigationGraphNode*> stack; 

    stack.push_back(pFromNode); 

    while(!stack.empty()) 
    { 
     CNavigationGraphNode  *pTop = stack.back(); 
     stack.pop_back(); 

     // Ok We've reached pToNode - means, path pFromNode to pToNode available 
     if(pTop == pToNode) 
     { 
      for(int a = 0; a < vpVisitedNodes.size(); a++) 
      { 
       CLogger::Instance()->Write(XLOGEVENT_LOCATION, "{VISITED} %s",vpVisitedNodes[a]->GetNodeName().data()); 
      } 
      return true; 
     } 

     // Add to visited list 
     vpVisitedNodes.push_back(pTop); 

     // Look for adjacent Nodes for pTop 
     std::vector<CNavigationGraphNode*> vpAdjacentNodes; 
     pNavGraph->GetAdjacentNodes(pTop->GetNodeName(), vpAdjacentNodes); 
     for(int x = 0; x < vpAdjacentNodes.size(); x++) 
     { 
      // Add to stack if not visited 
      if(IsVisited(vpVisitedNodes, vpAdjacentNodes[x]) == false) 
       stack.push_back(vpAdjacentNodes[x]); 
     } 
    } 

    // Path not found 
    return false; 
} 

這裏是調試輸出：節點1和節點3

之間

查找路徑

<main> [] DFS TRAVERSE TEST (DIRECTIONAL) 
<DFS> [] {VISITED} Node1 
<DFS> [] {VISITED} Node4 
<DFS> [] {VISITED} Node5 
<main> [] Path from Node1 to Node3 - YES 

查找路徑，而不是具有節點3和節點1

<main> [] DFS TRAVERSE TEST (DIRECTIONAL) 
<main> [] Path from Node3 to Node1 - NO 

Answer 1

如果我正確理解你的算法（它是一個DFS），
從起點 你先走一步到：

這是非常類似的想法在線程解釋了BFS第一個未訪問節點的方向。如果從該節點沒有到達目標的路由，則退後一步，嘗試轉到下一個未訪問節點，同時小心管理訪問的節點。

所有你需要補充的是一個堆棧到你總是推節點你正在服用的一個步驟， 從棧中彈出，如果你不得不退後一步。 該堆棧會將您的路線從start_node存儲到目標。它還可以幫助您確定退後的位置。

這裏是你的代碼，最後卻變得更長一點比我想過，但在這裏它是：

// I call fromNode: start_node, toNode: target_node. 

std::stack<CNavigationGraphNode*> DFS(CNavigationGraph *pNavGraph, CNavigationGraphNode* start_node, CNavigationGraphNode* target_node) 
{ 
    using namespace std; 

    stack<CNavigationGraphNode*> route; // route to target 
    unordered_set<CNavigationGraphNode*> visited_nodes; // hash set on who is visited 
    vector<CNavigationGraphNode*> adjacent_nodes; 

    CNavigationGraphNode* current_node = start_node; 
    while(current_node!=target_node) 
    { 
     pNavGraph->GetAdjacentNodes(current_node->GetNodeName(), adjacent_nodes); 

     // "for each"; you can use any form of looping through the neighbors of current_node. 
     bool found_non_visited = false; 
     for(auto node : adjacent_nodes) 
     { 
     if(visited_nodes.find(node) == visited_nodes.end()) 
     { 
      route.push(current_node); 
      visited_nodes.insert(node); 
      current_node = node; 
      found_non_visited = true; 
      break; 
     } 
     } 
     if(found_non_visited) 
     continue; 

     if(route.empty()) 
     return route; // empty route means no route found 
     current_node = route.pop(); 
    } 
    route.push(target); 
    return route; 
} 

現在你可以pop_back從開始用自己的方式到目標或從目標到pop自己的方式開始。如果路由是空的，則對應於從原始函數返回false。

Reference on unordered_set和stack，都在STL中。它使用一個桶來實現，因此它比set或map更快，通常使用紅黑樹來實現。

備註：std::unordered_set是一個C++ 11擴展，如果你使用C++ 03，隨時可以用較慢的std::set替換它。

Answer 2

幸福感，一個visited設置 - 你可以有一個parent地圖（圖：Vertex->頂點）。

在遍歷圖時修改地圖，以便如果發現節點u的節點v，請添加parent[v] = u。 Init parent[source] = NULL。

現在，所有你需要做的就是迭代（僞代碼）：

current <- dest 
while current != NULL: 
    print current 
    current <- parent[current] 

它會給你以相反的順序路徑。您可以存儲到堆棧中（而不是打印語句），並且如果要實現路徑的原始順序，則迭代堆棧。 How can I find the actual path found by BFS?