如何實現廣度優先搜索？

Question

我試圖在C++中實現BFS，函數應該像這樣工作：以一個頂點爲參數的圖形&，然後創建兩個向量，其中一個用於存儲與參數頂點相鄰的頂點，然後檢查那些頂點，如果其中一個未被訪問，則獲取它的鄰接點並將它們添加到向量中，然後頂點應被標記爲VISITED並打印;我寫了這段代碼，但它輸出了任何內容。注：我確保其他功能&像圖這樣的數據結構正在工作，問題在於BFS功能，我希望你們中的一些人能幫我解決它。

#include <iostream> 
#include <vector> 
#include <queue> 

using namespace std; 

enum Mark {VISITED, UNVISITED}; 

struct Vertex { 

    char name; 
    Mark mark; 
}; 

struct Edge{ 

    Vertex v1; 
    Vertex v2; 
    Edge(Vertex vertex1, Vertex vertex2): v1(vertex1), v2(vertex2){}; 
}; 

struct Graph{ 

vector<Vertex>vertices; 
vector<Edge>edges; 

vector<pair<Vertex, Edge>> adjacent(char u){ 

    vector<pair<Vertex, Edge>>res; 

    for(Edge e : edges){ 
     if(e.v1.name == u){ 
      res.push_back(make_pair(e.v2, e)); 
     }else if(e.v2.name == u){ 
      res.push_back(make_pair(e.v1, e)); 
     } 
    } 
    return res; 
} 

vector<Vertex> getAdj(char u){ 

    vector<Vertex>result; 

    for(Edge e: edges){ 
     if(e.v1.name == u){ 
      result.push_back(e.v2); 
     }else if(e.v2.name == u){ 
      result.push_back(e.v1); 
    } 
} 
    return result; 
} 
}; 

void BFS(Graph g, Vertex u){ 

    vector<Vertex>vec = g.getAdj(u.name); 

    for(Vertex v : vec){ 
     if(v.mark == UNVISITED){ 
      vector<Vertex>q = g.getAdj(v.name); 
      for(int i=0; i<q.size(); i++){ 
       vec.push_back(q[i]); 
      } 
      v.mark = VISITED; 
      vec.pop_back(); 
      cout << v.name << " "; 
    } 
    } 
} 





int main(int argc, const char * argv[]) { 

    Graph g; 

    Vertex v1, v2, v3, v4, v5, v6; 

    v1.name = 'A'; 
    v2.name = 'B'; 
    v3.name = 'C'; 
    v4.name = 'D'; 
    v5.name = 'E'; 
    v6.name = 'Z'; 

    g.edges.push_back(Edge(v1, v2)); 
    g.edges.push_back(Edge(v1, v3)); 
    g.edges.push_back(Edge(v2, v3)); 
    g.edges.push_back(Edge(v2, v4)); 
    g.edges.push_back(Edge(v3, v4)); 
    g.edges.push_back(Edge(v3, v5)); 
    g.edges.push_back(Edge(v4, v5)); 
    g.edges.push_back(Edge(v4, v6)); 
    g.edges.push_back(Edge(v5, v6)); 

    BFS(g, v1); 

    cout << endl; 

    } 

Answer 1

您尚未完全初始化您的Vertex s。你給他們的名字，但不是最初的mark標籤。

你可以在你的主要補充一點：

v1.mark = UNVISITED; 
    v2.mark = UNVISITED; 
    v3.mark = UNVISITED; 
    v4.mark = UNVISITED; 
    v5.mark = UNVISITED; 
    v6.mark = UNVISITED; 

你也可以做這樣的事情（也許是更好地與enum class更換）：

enum Mark {VISITED, UNVISITED}; 

struct Vertex { 

    char name; 
    Mark mark = UNVISITED; 
}; 

（我也想創建一個構造初始化名稱以確保你不會忘記這麼做）。

UPDATE：

有幾個問題與您的BFS： - 既然你將元素添加到您的vec內環內，外循環無法正常工作（我認爲它有與迭代器有關，因爲你總是改變向量的大小）。我設法使用常規for循環來解決它。

• 即使您設法使用了一個範圍for循環，您將從向量中的「從左到右」。並且您使用的是從矢量的末尾移除的pop_back()（所以在矢量的最右邊）。我不認爲這是你想要的。

• 您有正確的想法，將eacher Vertex標記爲已訪問且未訪問。但是您只更新BFS函數中的vec中的Vertex。但它們只是getADj方法的副本，這意味着每次將新鄰居添加到vec時，只要有已經訪問過的頂點，該值就不知道。實際上，你正在添加一個從未訪問過的新的Vertex。

可能還有其他的問題，但已經有了這些，你應該有很多的東西！

我建議你使用調試器和/或像'valgrind'這樣的工具來幫助在你的代碼中找到問題。