1

私は、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;


}
4

1 に答える 1

3

a から b への最短経路を実行する場合は、ダイクストラ アルゴリズムを使用する必要があります。

すべてのエッジのコストが 1 の場合、理論的には BFS の方が優れていますが、boost::graph では多少の労力が必要です (これは単なる空のシェルであり、オリジンからの距離を保存するために独自のビジターを実装する必要があります)。 .

ただし、ダイクストラを使用するには、エッジに重みを付けて Edge プロパティを追加し、それをアルゴリズムで使用する必要があります。

次の例http://www.boost.org/doc/libs/1_51_0/libs/graph/example/dijkstra-example.cppでは、先行マップを見ることで s から t への最短パスを巻き戻すことができます: p[ t] は、最短経路で t の前のノードです。

これで十分だと思います:)

于 2012-09-03T08:59:25.520 に答える