时间戳

首页 > 解决方案 > 如何使用 stl 迭代器和队列来实现图的广度优先遍历？

c++ - 如何使用 stl 迭代器和队列来实现图的广度优先遍历？

问题描述

虽然我从概念上理解了 BFS，但我还没有掌握如何使用迭代器和队列来实现 BFS。如果有人能给我一些关于如何在我的代码中正确使用迭代器的见解，我将不胜感激。谢谢你。

我什至不确定迭代器在这里是否是个好主意，我也尝试学习自动类型，但我不确定如何使用它。

#ifndef GRAPH_H
#define GRAPH_H
#include<vector>
#include<iostream>
using namespace std;

struct vertex;

struct adjVertex{
    vertex *v;
};

struct vertex{

    string name;
    bool visited = false;
    int distance = 0;
    vector<adjVertex> adj;
};

class Graph
{
    public:
        void addEdge(string v1, string v2);
        void addVertex(string name);
        void displayEdges();
        void breadthFirstTraverse(string sourceVertex);
        int getConnectedBuildings();


    private:
        vector<vertex*> vertices;
};

#endif // GRAPH_H

void Graph::breadthFirstTraverse(string sourceVertex){
    
    //first initialize everything as not found
    for(int i = 0; i < vertices.size(); i++)
    {
        vertices[i]->visited = false;
    }

    //pointer to sourceVertex
    vertex *vStart;

    for(int i=0; i < vertices.size(); i++)
    {
        if(vertices[i]->name == sourceVertex){
            vStart = vertices[i];
            cout << "Starting vertex (root): " << vStart->name << " -> " << endl;
        }
    }
    queue<vertex*> q;
    vStart->visited = true;
    q.push(vStart);
    vertex *n;
    vector<int>:: iterator i;
    
    while(!q.empty()){
        n = q.front();

        q.pop();

        for(i = n->adj.begin(); i != n->adj.end(); ++i){ // error: no viable overloaded '='

            cout << n->adj[*i].v->name <<"(" << n->adj[*i].v->distance << ")" << " ";

            if(!n->adj[*i].v->visited){
                n->adj[*i].v->visited = true;
                q.push(*i); //no matching member function for call to 'push'
            }
        }
    }
}

注意：我在评论中解决了我自己的问题。

标签： c++data-structuresgraphstlbreadth-first-search

解决方案

您的第一条错误消息：

错误：没有可行的重载'='

这与以下内容有关：

vector<int>:: iterator i;
for(i = n->adj.begin(); i != n->adj.end(); ++i) {

请注意，类型n->adj.begin()是vector<adjVertex>::iterator。但是，变量i的类型是vector<int>::iterator。编译器错误的内容比您显示的要多得多。这将完美地解释这个问题。

这应该可以修复错误：

for(vector<adjVertex>::iterator i = n->adj.begin(); i != n->adj.end(); ++i) {

既然你问了auto，那也是可以接受的：

for(auto i = n->adj.begin(); i != n->adj.end(); ++i) {

在这种情况下，类型i将为vector<adjVertex>::iterator。

第二个错误是相关的：

没有匹配的成员函数调用“push”

就是为了这个：

q.push(*i);

在这里，is的类型和qisqueue<vertex*>的类型。如果您应用我的上述修复，那么将产生相同问题的类型。所以，你需要：*iint*iadjVertex

q.push(i->v);

回到第一个错误，有一种更现代的迭代方式（从 C++11 开始），使用基于范围的循环：

for (auto& elem : n->adj) {

上面，这将遍历你的向量，让你通过typeadj的值访问它的元素。因此，您将能够使用.elemadjVertex&vertex*elem.v

推荐阅读