查找是否存在2個節點之間的路由深度優先搜索

我正在使用深度優先搜索和圖形來查找是否存在2個節點之間的路由。但由於某種原因，即使有路徑，我的方法總是會導致錯誤。查找是否存在2個節點之間的路由深度優先搜索

這裏是我的搜索代碼：

static boolean search(Graph g, Node start, Node end) 
{ 

if(start == null || end == null) return false; 

start.state = State.Visited; 

for(Node u: start.getChildNodes()) 
{ 
    if(u.state != State.Visited) 
    { 
     if(u.equals(end)) 
     { 
      return true; 
     } 
     else 
     { 
      u.state = State.Visited; 
      search(g,u,end); 
     } 
    } 
} 

return false;

}

我打電話這樣的方法：）

public static void main(String[] args) { 

     Graph gDfs = createNewGraph(); 

     System.out.println("path between A & B"); 
     System.out.println(search(gDfs,gDfs.getNode()[0],gDfs.getNode()[1])); 
    }

createNewGraph（

public static Graph createNewGraph() 
{ 

Graph g = new Graph();   
Node[] temp = new Node[8]; 

temp[0] = new Node("A", 3); 
temp[1] = new Node("B", 3); 
temp[2] = new Node("C", 1); 
temp[3] = new Node("D", 1); 
temp[4] = new Node("E", 1); 
temp[5] = new Node("F", 1); 

temp[0].addChildNode(temp[1]); 
temp[0].addChildNode(temp[2]); 
temp[0].addChildNode(temp[3]); 

temp[1].addChildNode(temp[0]); 
temp[1].addChildNode(temp[4]); 
temp[1].addChildNode(temp[5]); 

temp[2].addChildNode(temp[0]); 
temp[3].addChildNode(temp[0]); 
temp[4].addChildNode(temp[1]); 
temp[5].addChildNode(temp[1]); 

for (int i = 0; i < 7; i++) 
{ 
    g.addNode(temp[i]); 
} 
return g;

}

@amit =>這是你的建議嗎？

for(Node u: start.getChildNodes()) 
     { 
      if(u.state != State.Visited) 
      { 
       if (search(g,u,end)) return true; 
      } 
     }

來源

2014-05-03 fscore

見Amit的答案。另外，確保Node.equals（）正確實現，否則當路由存在時你也可能會錯誤。 –

只用當前狀態工作總是比較好，而不是下一個或前一個（無論是dfs還是bfs）。

boolean search(Graph g, Node current, Node target) 
{ 

    if (current == null || target == null) return false; 

    current.state = State.Visited; 

    if (current == target) return true; 

    for(Node u: current.getChildNodes()) 
    { 
     if(u.state != State.Visited && search(g,u,target)) 
     {     
      return true; 
     } 
    }  
    return false;  
}

有些頂點的「狀態」可以不被標記爲「State.Visited」即使是從「A」可以實現的。它可能會導致一些錯誤或錯誤的複雜度估計。我建議用

void search(Graph g, Node v) 
{ 
    v.state = State.Visited;  

    for(Node u: v.getChildNodes()) 
    { 
     if(u.state != State.Visited) 
     {     
      search(g,u); 
     } 
    }   
}

檢查最壞的情況，並檢查「B.state」是否是「State.Visited」

來源

2014-05-03 08:33:22 Ralor

我嘗試了第一次執行，它仍然返回false – fscore

@fscore然後嘗試第二次。如果還會返回false - 路徑不存在。這是一個類似於定義的實現。 – Ralor

我想我的例子之間的A和B之間的路徑，因爲A和B是根和兒童..有一個確定的路線.. – fscore

你的遞歸調用應產生真正的，如果它也取得了真正的結束：

if (search(g,u,end)) return true;

否則，你不這樣做與它返回的任何有價值的東西，而只會得到的結束for循環並最終產生false。

作爲一個方面說明，檢查當前節點是否爲目標節點的更好方法是不在for循環中，而是作爲它之前的新停止子句。請注意，儘管每個節點與其自身之間都有一條路徑（長度爲0），但您的方法將失敗search(G,start,start)。

來源

2014-05-03 08:06:42 amit

錯過了「別人什麼也不做」的部分。不好意思:) –

@amit哪一行應該在其他部分進行更改，我用你提到的行替換了搜索 – fscore

我不是這樣的問題，我建議的'if'中不應該有' else'，如果條件不成立，你只需要繼續下一次迭代。 – amit

查找是否存在2個節點之間的路由深度優先搜索

回答

相關問題