c++ - 在 Boost 中执行深度优先搜索和广度优先搜索

Question

我对 Boost 库和 C++ 语言都很陌生。

我使用 Boost 创建了一个图并添加了顶点和边，并在 graphviz 中输出了图。

现在我想执行从一个顶点到图中所有其他顶点的广度优先和深度优先搜索。

结果应该是图中从起始顶点到其他顶点的最短路径。

如何在 Boost 中完成此操作？任何帮助将不胜感激。

提前致谢。

我也添加了我的源代码供您引用。

#include "stdafx.h"
#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/range/irange.hpp>
#include <boost/graph/graphviz.hpp>

int main()
{
            using namespace std;
            using namespace boost;


        // Property types
            typedef property<vertex_name_t, std::string,
            property<vertex_index2_t, int> > VertexProperties;

        // Graph type
            typedef adjacency_list<vecS, vecS, undirectedS,
            VertexProperties> Graph;

        // Graph instance
            Graph g;

        // Property accessors
            property_map<Graph, vertex_name_t>::type
            profinet_name = get(vertex_name, g);
            property_map<Graph, vertex_index2_t>::type
            profinet_index2 = get(vertex_index2, g);

        // Create the vertices
            typedef graph_traits<Graph>::vertex_descriptor Vertex;
            Vertex u1;
            u1 = add_vertex(g);
            profinet_name[u1] = "Profinet 1";
            profinet_index2[u1] = 1;

            Vertex u2;
            u2 = add_vertex(g);
            profinet_name[u2] = "Profinet 2";
            profinet_index2[u2] = 2;

            Vertex u3;
            u3 = add_vertex(g);
            profinet_name[u3] = "Profinet 3";
            profinet_index2[u3] = 3;

            Vertex u4;
            u4 = add_vertex(g);
            profinet_name[u4] = "Profinet 4";
            profinet_index2[u4] = 4;

            Vertex u5;
            u5 = add_vertex(g);
            profinet_name[u5] = "Profinet 5";
            profinet_index2[u5] = 5;

            Vertex u6;
            u6 = add_vertex(g);
            profinet_name[u6] = "Profinet 6";
            profinet_index2[u6] = 6;


        // Create the edges
            typedef graph_traits<Graph>::edge_descriptor Edge;
            Edge e1;
            e1 = (add_edge(u1, u2, g)).first;

            Edge e2;
            e2 = add_edge(u1, u4, g).first;

            Edge e3;
            e3 = (add_edge(u1, u6, g)).first;

            Edge e4;
            e4 = (add_edge(u2, u3, g)).first;

            Edge e5;
            e5 = (add_edge(u2, u4, g)).first;

            Edge e6;
            e6 = (add_edge(u2, u5, g)).first;

            Edge e7;
            e7 = (add_edge(u3, u6, g)).first;

            Edge e8;
            e8 = (add_edge(u6, u5, g)).first;

            Edge e9;
            e9 = (add_edge(u5, u4, g)).first;


            write_graphviz(cout, g);

            return 0;


}

Answer 1

如果要执行从 a 到 b 的最短路径，则应该使用 Dijkstra 算法。

如果所有边的成本都为 1，BFS 理论上会更好，但在 boost::graph 中它需要一些努力(它只是一个空壳，你需要实现自己的访问者以存储与起源)。

但是，为了使用 dijkstra，您需要在边上添加带有权重的边属性，并在算法中使用它。

在下面的例子中http://www.boost.org/doc/libs/1_51_0/libs/graph/example/dijkstra-example.cpp您可以通过查看前导图来展开从 s 到 t 的最短路径:p[t] 是最短路径中 t 之前的节点。

我希望这就够了:)