使用 C++ 实现 BFS

Question

我正在尝试用 C++ 实现 BFS，这是代码。

#include <iostream>
#include <list>
#include <string>
#include <limits>
#include <map>

int infinity=std::numeric_limits<int>::max();


struct Node{
        int value;
        int distance;
        std::string color;

        Node(int val):
        value(val),
        distance(infinity),
        color("white")
        {}
};

//using AdjList = std::map<Node*,std::list<Node*>>;
typedef std::map<Node*,std::list<Node*>> AdjList;
AdjList create_graph()
{
    Node* n1 = new Node(1);
    Node* n2 = new Node(2);
    Node* n3 = new Node(3);
    Node* n4 = new Node(4);
    Node* n5 = new Node(5);
    Node* n6 = new Node(6);
    Node* n7 = new Node(7);
    Node* n8 = new Node(8);

    AdjList m;
    m[n1] = {n2, n5};
    m[n2] = {n1, n6};
    m[n3] = {n4, n6, n7};
    m[n4] = {n3, n7, n8};
    m[n5] = {n1};
    m[n6] = {n2, n3, n7};
    m[n7] = {n3, n4, n6, n8};
    m[n8] = {n4, n7};
    return m;
}


void bfs(const AdjList& m, Node* n1)
{
    std::list<Node*> queue;
    queue.push_back(n1);
    unsigned count = 0;

    while (!queue.empty())
    {
        auto n = queue.front();
        std::cout << n->value << std::endl;
        queue.pop_front();
        std::cout << *(m[n].begin()) << std::endl;
        for(auto it = m[n].begin(); it != m[n].end(); ++it)
        {
            if ((*it)->color != "black")
                queue.push_back(*it);
        }

        n->color = "black";
        n->distance = count;
        ++count;
    }
}

在尝试使用 gcc 进行编译时，我收到以下错误消息。

bfs.cpp: In function ‘void bfs(const AdjList&, Node*)’:
bfs.cpp:59:27: error: passing ‘const AdjList {aka const std::map<Node*, std::list<Node*> >}’ as ‘this’ argument of ‘std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = Node*; _Tp = std::list<Node*>; _Compare = std::less<Node*>; _Alloc = std::allocator<std::pair<Node* const, std::list<Node*> > >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = std::list<Node*>; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = Node*]’ discards qualifiers [-fpermissive]
         std::cout << *(m[n].begin()) << std::endl;
                           ^
bfs.cpp:60:20: error: passing ‘const AdjList {aka const std::map<Node*, std::list<Node*> >}’ as ‘this’ argument of ‘std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = Node*; _Tp = std::list<Node*>; _Compare = std::less<Node*>; _Alloc = std::allocator<std::pair<Node* const, std::list<Node*> > >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = std::list<Node*>; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = Node*]’ discards qualifiers [-fpermissive]
   for(auto it = m[n].begin(); it != m[n].end(); ++it)
                    ^
bfs.cpp:60:40: error: passing ‘const AdjList {aka const std::map<Node*, std::list<Node*> >}’ as ‘this’ argument of ‘std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = Node*; _Tp = std::list<Node*>; _Compare = std::less<Node*>; _Alloc = std::allocator<std::pair<Node* const, std::list<Node*> > >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = std::list<Node*>; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = Node*]’ discards qualifiers [-fpermissive]
   for(auto it = m[n].begin(); it != m[n].end(); ++it)

我不确定哪里出了问题。错误请指出

Answer 1

std::map::operator[] 是非常量，因为它会在需要时插入元素：

int main()
{
    std::map<std::string, std::string> m;
    m["new element"] = "1";
}

问题是 m 是一个 const AdjList&，您不能在其上调用非常量成员函数。您可以使用 std::map::find() 代替：

auto itor = m.find(n);
if (itor != m.end())
    std::cout << *(m->second.begin()) << std::endl;

Answer 2

两个 C++11 特性将使您的生活更轻松

映射的 at() const 函数，类似于 [] 但如果键不存在则抛出 out of range 异常，而不是添加新的项目到地图。
容器上的 for 循环

所以 :

for (auto it : m.at(n))  {
  if (it->color != "black")
  queue.push_back(it);
}

使用 C++ 实现 BFS

Implementing BFS using C++

c++

breadth-first-search

c++11