C++理解BFS找到最短路徑的問題

我有一個簡單的圖，我的任務是找到兩個節點之間的最短路徑。我已經盡力通讀BFS僞代碼和示例，但它只是不點擊。C++理解BFS找到最短路徑的問題

我的節點存儲在一個鄰接表中（此刻我不關心邊的權重）這裏是數據的視覺效果：第一列是向量元素，它的左邊的行是另一個向量。向量元素編號表示相應節點的編號。

===================================== 
0 | (1, 100), (3, 50), (7, 100) 
1 | (0, 100), (4, 50), (5, 10) 
2 | (3, 1000), (4, 200), (6, 1000) 
3 | (0, 50), (2, 1000) 
4 | (1, 50), (2, 200), (6, 100) 
5 | (1, 10), (6, 50), (7, 2000) 
6 | (2, 1000), (4, 100), (5, 50) 
7 | (0, 100), (5, 2000)

我想通過我的wikipedia發現的僞代碼來實現BFS，但我沒有得到它。我adjancency列表存儲在一個向量：vector<vector <vertex> > adjList;vertex是一個結構2 int的1）node和2）weight（再次聲明，我不是真正關心的權重，但現在我要離開這個結構設置這樣修改後來）

我的實現是非常基本的：

vector<vector <vertex> > adjList;  // the vector adjacency list 

// the start and end vertices are passed into the function 
int startV;  //num of start node 
int endV;  //num of destination node 

bool visited = false, done = false; //control   

vector<int> marked, path;    // holds visited and final path 

Queue<int> Q;       // Q for BFS 
Q.push(startV);      // enqueue BFS 

while (!Q.empty() && !done) { 

    int t = Q.front(); Q.pop();  // mark and pop(back) 
    marked.push_back(t);    // push back start node onto marked 

    if (t == endV)      // if t is our destination 
     done = true;     // done, get out of here 

    size_t adjE = adjList[t].size(); // degree of this node 

    for (int i = 0; i < adjE; i++) { 

     int u = adjList[t][i].node; // visit each adjacent node 

     for (int j = 0; j < marked.size(); j++) { 

      if (marked[j] == u)   // test if node has been marked 
       visited = true; 
      } 
             // check if this node has 
      if (!visited) {    // already been visited 
       marked.push_back(u);  // if not enqueue 
       Q.push(u); 
      } 
     } 
    } 
}

我知道必須有什麼毛病我的實現。我只是看不到是什麼。

更新： 我通過使用多重映射的方法解決了這個。詳細的解釋在這裏：Traverse MultiMap to Find Path from a Given Value to a Given Key

來源

2013-03-08 frankV

您不要將'visited'返回到'false'。 – didierc 2013-03-08 01:28:28

我認爲你找到visited節點的邏輯是不正確的。嘗試

... 
int u = adjList[t][i].node; 

visited = false; 
for (int j = 0; j < marked.size(); j++) { 
    // std::find() does essentially all this for you. Check it out. 
    if (marked[j] == u) { 
     visited = true; 
    } 
} 

if (!visited) { 
    marked.push_back(u); 
    Q.push(u); 
}

來源

2013-03-08 01:25:26 James

它不是建立最短路徑。它現在幾次重新訪問節點。就這樣我可以肯定。最短的路徑將被標記？或在隊列中？現在我正在打印標記的內容，但我認爲這是不對的。我不知道如何跟蹤路徑，因爲它是由算法 – frankV 2013-03-08 01:41:08

發現的。您也不得不找到一種方法來記住，如果'u'被添加到'標記'，那麼't'就把它放在那裏。你可以使用'std :: map '來做到這一點。 – James 2013-03-08 01:47:46

因此，爲每個相鄰節點的每個路徑保留一個key =>值。那麼只需返回最短的一個？ – frankV 2013-03-08 03:09:24

C++理解BFS找到最短路徑的問題

回答

相關問題