如何实现广度优先搜索？

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'这样的工具来帮助在你的代码中找到问题。