深度優先搜索和圖中兩個節點之間的廣度優先搜索

我有一個無向連接圖。我用一個二維數組的鄰接矩陣來實現它。深度優先搜索和圖中兩個節點之間的廣度優先搜索

據我所知，DFS在兄弟姐妹之前訪問子節點。 BFS在孩子面前拜訪兄弟姐妹。

我實現了這兩個這樣的：

public void DFT(int firstVertex) { 
    connectedVertices = 0; 
    int v; 
    Stack<Integer> stack = new Stack<Integer>(); 
    for (int i = 0; i < numVertices; i++) { 
     if(vertex[i] != null){ 
      vertex[i].setPushed(false); 
     } 
    } 
    stack.push(firstVertex); 
    connectedVertices++; 
    vertex[firstVertex].setPushed(true); 

    while(!stack.isEmpty()){ 
     v = stack.pop(); 
     vertex[v].visit(); 
     for (int i = 0; i < numVertices; i++) { 
      if(adj[v][i] != 0 && !vertex[i].getPushed()){ 
       stack.push(i); 
       connectedVertices++; 
       vertex[i].setPushed(true); 
      } 
     } 
    } 

} 

public void BFT(int firstVertex) { 
    connectedVertices = 0; 
    int v; 
    Queue<Integer> queue = new LinkedList<Integer>(); 
    for (int i = 0; i < numVertices; i++) { 
     if(vertex[i] != null){ 
      vertex[i].setPushed(false); 
     } 
    } 
    queue.add(firstVertex); 
    connectedVertices++; 
    vertex[firstVertex].setPushed(true); 

    while(!queue.isEmpty()){ 
     v = queue.remove(); 
     vertex[v].visit(); 
     for (int i = 0; i < numVertices; i++) { 
      if(adj[v][i] != 0 && !vertex[i].getPushed()){ 
       queue.add(i); 
       connectedVertices++; 
       vertex[i].setPushed(true); 
      } 
     } 
    } 

}

因爲它是這些方法只需要一個參數，起始頂點。如果我被要求將DFS和BFS從一個節點提供給另一個節點，該怎麼辦？這是一個連通無向圖的簡單例子。 enter image description here

如果我被要求執行從D到E的DFS，它會是D，C，A，E還是D，E。我認爲DFS和BFS必須訪問每個節點，在這種情況下B不能被訪問。我不知道如何改變我目前的方法來滿足這些要求。

來源

2013-11-25 Infodayne

如果您先訪問C或E，我不確定它真的很重要。他們都是D的孩子，對吧？它是特定於實現的行爲，DFS沒有定義你首先訪問哪個孩子。

在DFS，如果你選擇Child C級第一，那麼你應該訪問您訪問E.

前

在BFS，你應該已經訪問了E和C您訪問A或B

來源

2013-11-25 02:17:21 Justin

前行啊，但是如果我被要求從一個頂點執行一個dfs或bfs到另一個頂點，那麼當我碰到第二個頂點後，我會完成嗎？或者我必須繼續並訪問其餘的頂點？在上面的示例中，無論我是先訪問C還是E，如果末端點是E，我都無法到達B. DFS/BFS是否要求您訪問連接組件中的每個頂點？ – Infodayne

@Infodayne如果您被要求搜索（DFS或BFS）從D到E，那麼您應該在到達E時立即停止;你不需要繼續。理論上講，如果BFS接近起點，它將首先找到頂點;如果DFS距離起點較遠，它將首先找到該頂點。 – Justin

深度優先搜索和圖中兩個節點之間的廣度優先搜索

回答

相關問題