深度優先搜索過早終止

Question

在this question我問了一些關於實現我自己的圖創建數據結構的問題。現在，它終於可以工作了，我正在實施基本的DFS和BFS。我的BFS正在使用我自己創建的隊列類。然而，我的DFS沒有工作，我似乎無法弄清楚爲什麼。它只能從第一個節點開始並找到第一個相鄰節點（「USA」）。任何其他組合都會返回NULL指針（所以沒有「真正的」運行時錯誤）。下面是代碼，我刪除了無關的例程和已經工作的內容。

#include <iostream> 
#include <vector> 
#include <string> 
using namespace std; 

template<class T> 
class Node{ 
    T data; 
    vector<Node<T>*> adjacent; 
    public: 
     bool visited; 
     int n; 
     Node(T initData) : data(initData), visited(false),n(0){} 
     void addAdjacent(Node<T>& other){//call from within GraphCl class. push_back in adjacent} 
     T getData(){return data;} 
     Node<T>* getEdge(int edgeNum){return adjacent[edgeNum];} 
}; 

template<class T> 
class GraphCl{ 
    int n; 
    vector<Node<T>*> nodes; 
    public: 
     GraphCl(int size=0): n(size) {//[...]} 
     ~GraphCl(){//[...]} 
    void addNode(T input){//push_back new node to nodes vector} 
    void addEdge(int baseNode, int edgeNode){//push_back edgeNode adres in adjacent vector} 
    Node<T>* getNodeAddress(int idx){return nodes[idx];} 
}; 

template<class T> 
Node<T>* dfs(Node<T>* rootNode, T key){ 
    if(rootNode->visited == false){ 
     rootNode->visited = true; 
     if (rootNode->getData() == key){ 
      return rootNode; 
     } 
     for(int i=0;i<rootNode->n;i++){ 
      if(dfs(rootNode->getEdge(i),key) != NULL){ 
       return dfs(rootNode->getEdge(i),key); 
      } 
     } 
    } 
    return NULL; 
} 

int main(){ 
    GraphCl<string> *myGraph = new GraphCl<string>(); 
    myGraph->addNode("USA");//0 
    myGraph->addNode("Australia");//1 
    myGraph->addNode("The_Netherlands");//2 
    //more nodes added here ... 
    myGraph->addNode("Indonesia"); 
    myGraph->addNode("Canada"); 
    myGraph->addNode("Czech_Republic"); 
    myGraph->addEdge(0,1); 
    myGraph->addEdge(0,4); 
    myGraph->addEdge(2,10); 
    //more edges added here ... 
    myGraph->addEdge(3,1); 
    myGraph->addEdge(11,12); 
    myGraph->addEdge(6,11); 
    Node<string> *rootNode = myGraph->getNodeAddress(4); 
    cout << dfs<string>(rootNode, "USA")->getData(); 
    return 0; 
} 

DFS功能有什麼嚴重錯誤，可以立即發現嗎？無法弄清楚。

Answer 1

這就是問題所在：

if(dfs(rootNode->getEdge(i),key) != NULL){ 
       return dfs(rootNode->getEdge(i),key); 
      } 

您在這裏同一節點上兩次調用dfs。第二次給你打電話，rootNode->visited將是真實的。在這種情況下，您的代碼返回NULL。要修復它，請將if塊更改爲

Node<T>* val = dfs(rootNode->getEdge(i),key); 
if(val != NULL){ 
        return val; 
       }