生成圖形的BFS森林

Question

我想生成DAG（直接非循環圖）的BFS森林。這意味着我的Tree類需要是一棵普通的樹，而不是一棵二叉樹（換句話說，當我生成一個森林時，我無法知道一個節點會有多少個子節點）。大部分代碼都寫在下面，但是我缺少一行，在我的生活中，它逃脫了我！

public Tree BFS(V start) 
{ 
    reset(); 
    LinkedList<GraphMatrixVertex<V>> list = new LinkedList<GraphMatrixVertex<V>>(); 
    GraphMatrixVertex<V> vert = dict.get(start); 
    Tree root = new Tree(vert); 
    list.add(vert); 
    do 
    { 
     vert = list.getFirst(); 
     Iterator<V> ni = neighbors(start); 
     while(ni.hasNext()) 
     { 
      V v = ni.next(); 
      GraphMatrixVertex<V> vtx = dict.get(v); 
      if(!vtx.isVisited()) 
      { 
       list.add(vtx); 
          vtx.visit(); 
       root.addChild(new Tree(vtx)); 
      } 
     } 
    //code goes here 
    } 
    while(!list.isEmpty()); 

    return root; 
} 

我的樹類存儲一個值參數，父引用和一系列子項。 我的問題是引用下一個樹節點。一旦我將所有未訪問的鄰居添加爲當前節點的子節點，我如何才能到達下一個節點？

編輯：

所以它看起來像這樣？

public void bfs(Tree parent) 
{ 
    Iterator<V> ni = neighbors((V) parent.value()); 
    if(ni.hasNext()) 
    { 
      while(ni.hasNext()) 
      { 
      V next = ni.next(); 
      GraphMatrixVertex<V> vert = dict.get(next); 
      if(!vert.isVisited()) 
       parent.addChild(new Tree(next)); 
     } 
    } 
} 

遞歸調用去哪裏？

Answer 1

如果我正確理解你的問題，你可以使用遞歸來做到這一點。基本上你有一個函數可以創建一個節點層，然後爲你想要創建/訪問的每個子節點再次調用它自己。

編輯：

好的，我編輯了一下你的代碼。首先，我刪除了if（hasNext）作爲其冗餘的while循環內部。對於鄰居列表中的每個子節點，創建一個新的樹節點，然後運行其bfs（）方法，將當前的Tree對象傳入。該函數返回一個列表，該列表應該是樹中的最佳路徑。我也不確定你的鄰居節點的方式，它看起來有點奇怪。我還沒有測試過代碼，所以可能會有錯別字和內容，但希望它能給你一個關於如何去搜索的想法。哦，當你點擊一個葉節點（你的目標？）時，它只需要設置它的權重並返回一個新列表，只有它自己。

int weight; // this should be you node traversal cost 

public LinkedList<Tree> bfs(Tree parent){ 

    Iterator<V> ni = neighbors((V) parent.value()); 

    LinkedList bestPath = null;  
    int bestScore = 0xFFFFFFFF; 

    while(ni.hasNext()){ 
     V next = ni.next(); 
     GraphMatrixVertex<V> vert = dict.get(next); 
     if(!vert.isVisited()){ 
      Tree newNode = new Tree(next); 
      parent.addChild(newNode); 
      LinkedList path = newNode.bfs(this); 
       if(newNode.weight < bestScore){ 
        bestScore = weight; 
        bestPath = path; 
       } 
     } 
    } 
    weight = bestScore + this.weight; 
    bestPath.addFirst(this); 
    return path; 
} 

編輯2：

public void bfs(Tree parent){ 

    Iterator<V> ni = neighbors((V) parent.value()); 

    while(ni.hasNext()){ 
     V next = ni.next(); 
     GraphMatrixVertex<V> vert = dict.get(next); 
     if(!vert.isVisited()){ 
      Tree newNode = new Tree(next); 
      parent.addChild(newNode); 
      newNode.bfs(this); 
     } 
    } 
}