グラフのアルゴリズム

ウィキペディア小見出し辞書

グラフのアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/15 16:52 UTC 版)

「Boost C++ライブラリ」の記事における「グラフのアルゴリズム」の解説

Boost.Graph - グラフ理論の複数の視点および多数のアルゴリズムの形で、グラフ概念の柔軟かつ効果的な実装を提供する。 アルゴリズムの例：トポロジカルソート #include #include #include #include #include #include #include int main(){ using namespace boost; // Type of graph typedef adjacency_list > Graph; // Handle vertices typedef boost::graph_traits::vertex_descriptor Vertex; // Container for the chain of vertices typedef std::vector container; // Type of representation of arcs typedef std::pair Pair; // Edges of the graph Pair edges[6] = { Pair(0,1), Pair(2,4), Pair(2,5), Pair(0,3), Pair(1,4), Pair(4,3) }; // Count Graph G(edges, edges + 6, 6); // Dictionary to get a handle on the numbers of vertices vertices boost::property_map::type id = get(vertex_index, G); // Container for storing the sorted vertices container c; // Execute algorithm topological_sort(G, std::back_inserter(c)); // Output results: sorting descriptors of the graph in the container, // Get the serial number of vertices std::cout << "Topological check:"; for (container::reverse_iterator ii = c.rbegin(); ii != c.rend(); ++ii) std::cout << id[*ii] << " "; std::cout << std::endl; return 0;} 詳細は The Boost Graph Library を参照。