用于 BFS 遍历的 C++ Lambda 函数

Question

使用下面的两个函数，我如何使用 lambda 函数来 BFS 遍历名为 x 的事物图

i.e. Graph<Thing> x

其中涉及将显示函数发送给bfsTraverse函数，以便显示每个Thing中的信息。

void display(const Thing& c)
{
    cout<<left<<setw(3)<<c.getKey()<<" "<<left<<setw(2)<<c.getLabel()<<endl;
}

template <typename E> 
void Graph<E>::bfsTraverse(FuncType func)
{
    /* some code not necessary to describe */
}

所以基本上，我只需要了解如何使用 lambda 函数将它们联系在一起。

Answer 1

非常简单。例如，让我们使用 lambda 打印向量的值：

#include <algorithm>
#include <vector>
#include <iostream>

int main (int argc, char* argv[]) {
  std::vector <int> data{1,2,3,4};

  std::for_each (data.begin (), data.end (), [] (const int val) { std::cout << val << std::endl;});

  return 0;
}

最后一个参数 [] (...) 是 lambda。接受 lambda 的函数可能如下所示：

template <typename E, typename FuncType> 
void Graph<E>::bfsTraverse (FuncType func)
{
    /* some code not necessary to describe */
}

更新

如果是图表，您应该执行以下操作。您的图的实现应该有一个访问顶点的方法：它可能是 'getRoot'、'getSource'、'getAllNodes'，它是实现定义的。我会坚持 'getRoot'。每个 vertex/node 都应该有一个像 'getAdjacentVertices'、'getChildren' 这样的方法。将所有组合在一起：

template <typename E, typename FuncType> 
void Graph<E>::bfsTraverse (FuncType func)
{
    std::queue<Node> q;

    auto&& root = getRoot ();

    q.push (root);

    while (not q.empty ()) { 
      auto&& current = q.front ();
      q.pop ();

      func (current);

      auto&& adjacent = current.getAdjacent ();

      for (auto&& a: adjacent) {
        q.push (a);
      }
}

请注意，我故意省略了保留访问节点列表和其他内容。但想法本身保持不变。现在您可以按如下方式调用此函数：

Graph<E> g;
g.bfsTraverse ( [] (const Node& n) {
                  std::cout << n.to_str () << std::endl;
                } 
);

用于 BFS 遍历的 C++ Lambda 函数

C++ Lambda Function for BFS Traversal

c++

algorithm

lambda

graph-theory

breadth-first-search