在grah中尋找兩個節點之間的方式（存儲傳遞的節點）

我有一張圖，我想找到兩個節點（編號3和5）之間的路徑。在grah中尋找兩個節點之間的方式（存儲傳遞的節點）

我讀了關於查找圖中的路徑，我試着寫DFS和BFS。兩者都實施並運行良好。但是，我想獲得直接從3到5訪問的每個節點的列表。這兩種算法都按照預期的方式工作，在運行bsf時，我將按以下順序訪問節點：2,6,1,4,5。使用dfs 2,1,4,5。但我想要達到的是6,5（第一種情況）和2,4,5秒。

換句話說，我只想保存從3到5（在dfs/bfs期間並不都被訪問）的節點，作爲節點列表。

我一直在絞盡腦汁，如何改變我的代碼來實現它，或者我應該改變我的方法？我應該將節點存儲在正確的路徑中，還是使用不同的算法？我根本不知道如何去做。

我的BFS

public List<Node> bfs(Node root, Node nodeWeSearchFor) 
{ Queue<Node> queue = new LinkedList<Node>(); 
    List<Node> route = new ArrayList<Node>(); 

    if(root == null || nodeWeSearchFor == null) return route; 
    //State is just an enum Visited or unvisited 
    root.state = State.Visited; 
    //Adds to end of queue 
    queue.add(root); 

    while(!queue.isEmpty()) 
    { 
     //removes from front of queue 
     Node r = queue.remove(); 


     //Visit child first before grandchild 
     for(Node n: r.getConnectedNodes()) 
     { 
      if(n.state == State.Unvisited) 
      { 
       queue.add(n); 
       route.add(n); 
       n.state = State.Visited; 
       //If we found node, return 
       if(n==nodeWeSearchFor){ 
        return route; 
       } 
      } 
     } 
    } 
return route;}

我的DFS：

public List<Node> dfs(Node root, Node nodeWeSearchFor) 
{  
    List<Node> route = new ArrayList<Node>(); 
    //Avoid infinite loops 
    if(root == null) return route; 

    System.out.print(root.toString() + "\t"); 
    root.state = State.Visited; 
    route.add(root); 
    if(root == nodeWeSearchFor) return route; 
    //for every child 
    for(Node n: root.getConnectedNodes()) 
    { 
     //if childs state is not visited then recurse 
     if(n.state == State.Unvisited) 
     { 
      //recursive call for dfs (We are passing route) 
      dfs(n,nodeWeSearchFor,route); 
     } 
    } 
return route; 
} 

public List<Node> dfs(Node root, Node nodeWeSearchFor,List<Node> _route) 
{  
    List<Node> route = _route; 
    //Avoid infinite loops 
    if(root == null) return route; 

    System.out.print(root.toString() + "\t"); 
    root.state = State.Visited; 
    route.add(root); 
    if(root == nodeWeSearchFor) return route; 
    //for every child 
    for(Node n: root.getConnectedNodes()) 
    { 
     //if childs state is not visited then recurse 
     if(n.state == State.Unvisited) 
     { 
      dfs(n,nodeWeSearchFor,route); 
     } 
    } 
return route;

}

來源

2015-11-11 Thamiar

這是很容易的，在DFS，當你到達「結束」（你不能往前走），你必須「回去」。所以當你「回來」時，你只需從被訪問節點的列表中刪除「死衚衕」中的那個節點。

在BFS中，您必須爲訪問的每個節點創建新的列表，複製已「訪問」節點的已訪問節點，然後將其自身添加到該列表中。

來源

2015-11-11 15:22:08 libik

在grah中尋找兩個節點之間的方式（存儲傳遞的節點）

回答

相關問題