Boost.Graph 中的算法類似于標準庫中的算法——它們是通用的并且非常靈活。但是，并不總是很清楚應(yīng)該如何使用它們。

示例 31.8。使用breadth_first_search() 從內(nèi)到外訪問點

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iterator>
#include <algorithm>
#include <iostream>
int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };
  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};
  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};
  boost::array<int, 4> distances{{0}};
  boost::breadth_first_search(g, topLeft,
    boost::visitor(
      boost::make_bfs_visitor(
        boost::record_distances(distances.begin(),
          boost::on_tree_edge{}))));
  std::copy(distances.begin(), distances.end(),
    std::ostream_iterator<int>{std::cout, "\n"});
}

Example31.8

示例 31.8 使用算法 boost::breadth_first_search() 從內(nèi)部到外部訪問點。該算法從作為第二個參數(shù)傳遞的點開始。它首先訪問可以從該點直接到達的所有點，像波浪一樣工作。

boost::breadth_first_search() 不返回特定結(jié)果。該算法只是訪問點。是否收集和存儲數(shù)據(jù)取決于傳遞給 boost::breadth_first_search() 的訪問者。

訪問者是在訪問點時調(diào)用其成員函數(shù)的對象。通過將訪問者傳遞給 boost::breadth_first_search() 之類的算法，您可以決定訪問某個點時應(yīng)該發(fā)生什么。訪問者就像函數(shù)對象，可以傳遞給標準庫的算法。

示例 31.8 使用記錄距離的訪問者。距離是從一個點到另一個點必須跨越的線數(shù)，從作為第二個參數(shù)傳遞給 boost::breadth_first_search() 的點開始。 Boost.Graph 提供了幫助函數(shù) boost::record_distances() 來創(chuàng)建訪問者。還必須傳遞屬性圖和標簽。

屬性映射存儲點或線的屬性。 Boost.Graph 描述了屬性映射的概念。由于指針或迭代器被視為屬性映射的開頭，因此詳細了解屬性映射并不重要。在示例 31.8 中，數(shù)組距離的開頭通過 distances.begin() 傳遞到 boost::record_distances()。這足以將數(shù)組距離用作屬性映射。但是，重要的是數(shù)組的大小不小于圖中的點數(shù)。畢竟，需要存儲到圖中每個點的距離。

請注意，距離基于 boost::array 而不是 std::array。使用 std::array 會導致編譯器錯誤。

根據(jù)算法，有不同的事件。傳遞給 boost::record_distances() 的第二個參數(shù)指定應(yīng)通知訪問者哪些事件。 Boost.Graph 定義了空類的標簽來給事件命名。示例 31.8 中的標簽 boost::on_tree_edge 指定在找到新點時應(yīng)記錄距離。

事件取決于算法。您必須查看有關(guān)算法的文檔，以了解支持哪些事件以及可以使用哪些標簽。

由 boost::record_distances() 創(chuàng)建的訪問者與算法無關(guān)，因此您可以將 boost::record_distances() 與其他算法一起使用。適配器用于綁定算法和訪問者。示例 31.8 調(diào)用 boost::make_bfs_visitor() 來創(chuàng)建這個適配器。此幫助函數(shù)返回算法 boost::breadth_first_search() 所期望的訪問者。此訪問者定義適合算法支持的事件的成員函數(shù)。例如，boost::make_bfs_visitor() 返回的訪問者定義了成員函數(shù) tree_edge()。如果使用標簽 boost::on_tree_edge 定義的訪問者被傳遞給 boost::make_bfs_visitor()（如示例 31.8），則在調(diào)用 tree_edge() 時會通知訪問者。這使您可以使用具有不同算法的訪問者，而無需這些訪問者定義所有算法所期望的所有成員函數(shù)。

boost::make_bfs_visitor() 返回的適配器不能直接傳遞給算法 boost::breadth_first_search()。它必須用 boost::visitor() 包裝，然后作為第三個參數(shù)傳遞。

有兩種算法變體，例如 boost::breadth_first_search()。一種變體期望算法支持的每個參數(shù)都將被傳遞。另一個變體支持類似于命名參數(shù)的東西。使用第二個變體通常更容易，因為只需要傳遞您感興趣的參數(shù)。許多參數(shù)不必傳遞，因為算法使用默認值。

示例 31.8 使用了需要命名參數(shù)的 boost::breadth_first_search() 的變體。前兩個參數(shù)是圖形和起點，它們是必需的。然而，第三個參數(shù)幾乎可以是一切。在示例 31.8 中，需要傳遞一個訪問者。為此，boost::make_bfs_visitor() 返回的適配器使用 boost::visitor() 命名?，F(xiàn)在，很明顯第三個參數(shù)是訪問者。您將在以下示例中看到其他參數(shù)如何按名稱傳遞到 boost::breadth_first_search()。

示例 31.8 顯示數(shù)字 0、1、2 和 1。這些是從左上角到所有點的距離。右上角的字段（索引為 1 的字段）僅一步之遙。右下方的字段（索引為 2 的字段）相距兩步。左下方的字段——索引為 3 的字段——再次只有一步之遙。首先打印的數(shù)字 0 是指左上角的字段。由于它是傳遞給 boost::breadth_first_search() 的起點，因此需要零步才能到達它。

boost::breadth_first_search() 不設(shè)置數(shù)組中的元素，它只是增加存儲的值。因此，您必須在開始之前初始化數(shù)組距離中的所有元素。

示例 31.9 說明了如何找到最短路徑。

示例 31.9。使用 width_first_search() 查找路徑

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <algorithm>
#include <iostream>
int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };
  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};
  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};
  boost::array<int, 4> predecessors;
  predecessors[bottomRight] = bottomRight;
  boost::breadth_first_search(g, bottomRight,
    boost::visitor(
      boost::make_bfs_visitor(
        boost::record_predecessors(predecessors.begin(),
          boost::on_tree_edge{}))));
  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = predecessors[p];
  }
  std::cout << p << '\n';
}

Example31.9

示例 31.9 顯示 0、1 和 2。這是從左上角到右下角的最短路徑。盡管左下場上的路徑同樣短，但它在右上場上方引導。

再次使用 boost::breadth_first_search() - 這次是為了找到最短路徑。如您所知，此算法只是訪問點。要獲得最短路徑的描述，必須使用適當?shù)脑L問者。示例 31.9 調(diào)用 boost::record_predecessors() 來獲取一個。

boost::record_predecessors() 返回一個訪問者來存儲每個點的前任。每當 boost::breadth_first_search() 訪問一個新點時，前一個點就會存儲在傳遞給 boost::record_predecessors() 的屬性映射中。由于 boost::breadth_first_search() 從內(nèi)部到外部訪問點，因此找到了最短路徑——從作為第二個參數(shù)傳遞給 boost::breadth_first_search() 的點開始。示例 31.9 找到從圖中所有點到右下角的最短路徑。

在 boost::breadth_first_search() 返回后，屬性映射前驅(qū)包含每個點的前驅(qū)。為了在從左上角到右下角時找到第一個字段，索引為 0 的元素（左上角字段的索引）在前輩中被訪問。在前輩中找到的值為 1，這意味著下一個字段位于右上角。訪問索引為 1 的前輩會返回下一個字段。在示例 31.9 中，這是右下角的字段 - 索引為 2 的字段。這樣就可以在巨大的圖表中迭代地找到從起點到終點的點。

示例 31.10。使用 width_first_search() 查找距離和路徑

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <algorithm>
#include <iostream>
int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };
  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};
  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};
  boost::array<int, 4> distances{{0}};
  boost::array<int, 4> predecessors;
  predecessors[bottomRight] = bottomRight;
  boost::breadth_first_search(g, bottomRight,
    boost::visitor(
      boost::make_bfs_visitor(
        std::make_pair(
          boost::record_distances(distances.begin(),
            boost::on_tree_edge()),
          boost::record_predecessors(predecessors.begin(),
            boost::on_tree_edge{})))));
  std::for_each(distances.begin(), distances.end(),
    [](int d){ std::cout << d << '\n'; });
  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = predecessors[p];
  }
  std::cout << p << '\n';
}

Example31.10

示例 31.10 顯示了 boost::breadth_first_search() 如何用于兩個訪問者。要使用兩個訪問者，您需要使用 std::make_pair() 將它們配對。如果需要兩個以上的訪問者，則必須嵌套這些對。示例 31.10 與示例 31.8 和示例 31.9 一起執(zhí)行相同的操作。

boost::breadth_first_search() 只能在每行具有相同權(quán)重的情況下使用。這意味著跨越點之間的任何線所花費的時間總是相同的。如果線是加權(quán)的，這意味著每條線可能需要不同的時間來遍歷，那么您需要使用不同的算法來找到最短路徑。

示例 31.11。使用 dijkstra_shortest_paths() 查找路徑

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iostream>
int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };
  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};
  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS, boost::no_property,
    boost::property<boost::edge_weight_t, int>> graph;
  std::array<int, 4> weights{{2, 1, 1, 1}};
  graph g{edges.begin(), edges.end(), weights.begin(), 4};
  boost::array<int, 4> directions;
  boost::dijkstra_shortest_paths(g, bottomRight,
    boost::predecessor_map(directions.begin()));
  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = directions[p];
  }
  std::cout << p << '\n';
}

Example31.11

示例 31.11 使用 boost::dijkstra_shortest_paths() 來查找到右下角的最短路徑。如果線被加權(quán)，則使用此算法。示例 31.11 假設(shè)從左上角到右上角越過線所需的時間是越過任何其他線所需的時間的兩倍。

在使用 boost::dijkstra_shortest_paths() 之前，必須將權(quán)重分配給行。這是通過數(shù)組權(quán)重完成的。數(shù)組中的元素對應(yīng)于圖中的線條。因為從左上角到右上角的線是第一個，所以 weights 中的第一個元素被設(shè)置為所有其他元素的兩倍大。

為了給線條分配權(quán)重，數(shù)組權(quán)重開頭的迭代器作為第三個參數(shù)傳遞給圖形的構(gòu)造函數(shù)。這第三個參數(shù)可用于初始化線條的屬性。這僅適用于已為線條定義屬性的情況。

示例 31.11 將其他模板參數(shù)傳遞給 boost::adjacency_list。第四個和第五個模板參數(shù)指定點和線是否具有屬性以及這些屬性是什么。您可以為線和點指定屬性。

默認情況下，boost::adjacency_list 使用 boost::no_property，這意味著點和線都沒有屬性。在示例 31.11 中，boost::no_property 作為第四個參數(shù)傳遞，用于指定點的無屬性。第五個參數(shù)使用 boost::property 定義捆綁屬性。

捆綁屬性是內(nèi)部存儲在圖表中的屬性。因為可以定義多個捆綁屬性，所以 boost::property 需要一個標簽來定義每個屬性。 Boost.Graph 提供了一些標簽，例如 boost::edge_weight_t，來定義算法自動識別和使用的常用屬性。傳遞給 boost::property 的第二個模板參數(shù)是屬性的類型。在示例 31.11 中，權(quán)重是 int 值。

示例 31.11 有效，因為 boost::dijkstra_shortest_paths() 自動使用類型為 boost::edge_weight_t 的捆綁屬性。

請注意，沒有訪問者被傳遞到 boost::dijkstra_shortest_paths()。該算法不只是訪問點。它尋找最短路徑——這就是為什么它被稱為 boost::dijkstra_shortest_paths()。您無需考慮事件或訪客。你只需要傳遞一個容器來存儲每個點的前身。如果您使用需要命名參數(shù)的 boost::dijkstra_shortest_paths() 變體，如示例 31.11 中所示，則使用 boost::predecessor_map() 傳遞容器。這是一個輔助函數(shù)，它需要一個指向數(shù)組開頭的指針或迭代器。

示例 31.11 顯示 0、3 和 2：從左上角到右下角的最短路徑通向左下角字段。右上角的路徑比其他可能性具有更大的權(quán)重。

示例 31.12。使用 dijkstra_shortest_paths() 的用戶定義屬性

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iostream>
int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };
  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};
  struct edge_properties
  {
    int weight;
  };
  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS, boost::no_property,
    edge_properties> graph;
  graph g{edges.begin(), edges.end(), 4};
  graph::edge_iterator it, end;
  boost::tie(it, end) = boost::edges(g);
  g[*it].weight = 2;
  g[*++it].weight = 1;
  g[*++it].weight = 1;
  g[*++it].weight = 1;
  boost::array<int, 4> directions;
  boost::dijkstra_shortest_paths(g, bottomRight,
    boost::predecessor_map(directions.begin()).
    weight_map(boost::get(&edge_properties::weight, g)));
  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = directions[p];
  }
  std::cout << p << '\n';
}

Example31.12

示例 31.12 的工作方式與上一個類似，并顯示相同的數(shù)字，但它使用用戶定義的類 edge_properties，而不是預(yù)定義的屬性。

edge_properties 定義成員變量 weight 來存儲線條的重量。如果需要其他屬性，可以添加更多成員變量。

如果您使用線的描述符作為圖形的索引，則可以訪問用戶定義的屬性。因此，該圖的行為類似于一個數(shù)組。您從 boost::edges() 返回的行迭代器中獲取描述符。這樣就可以為每一行分配一個權(quán)重。

為了讓 boost::dijkstra_shortest_paths() 理解權(quán)重存儲在 edge_properties 中的權(quán)重中，必須傳遞另一個命名參數(shù)。這是通過 weight_map() 完成的。請注意，weight_map() 是從 boost::predecessor_map() 返回的對象的成員函數(shù)。還有一個名為 boost::weight_map() 的獨立函數(shù)。如果需要傳遞多個命名參數(shù)，則必須在第一個命名參數(shù)（獨立函數(shù)返回的參數(shù)）上調(diào)用成員函數(shù)。這樣，所有參數(shù)都被打包到一個對象中，然后傳遞給算法。

為了告訴 boost::dijkstra_shortest_paths() edge_properties 中的權(quán)重包含權(quán)重，傳遞了一個指向該屬性的指針。它不會直接傳遞給 weight_map()。相反，它通過 boost::get() 創(chuàng)建的對象傳遞?，F(xiàn)在調(diào)用已完成，并且 boost::dijkstra_shortest_paths() 知道要訪問哪個屬性來獲取權(quán)重。

示例 31.13。在圖形定義處初始化用戶定義的屬性

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iostream>
int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };
  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};
  struct edge_properties
  {
    int weight;
  };
  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS, boost::no_property,
    edge_properties> graph;
  boost::array<edge_properties, 4> props{{2, 1, 1, 1}};
  graph g{edges.begin(), edges.end(), props.begin(), 4};
  boost::array<int, 4> directions;
  boost::dijkstra_shortest_paths(g, bottomRight,
    boost::predecessor_map(directions.begin()).
    weight_map(boost::get(&edge_properties::weight, g)));
  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = directions[p];
  }
  std::cout << p << '\n';
}

定義圖形時可以初始化用戶定義的屬性。您只需將迭代器作為第三個參數(shù)傳遞給 boost::adjacency_list 的構(gòu)造函數(shù)，它引用用戶定義屬性類型的對象。因此，您不需要通過描述符訪問行的屬性。示例 31.13 的工作原理與前一個類似，并顯示相同的結(jié)果。

示例 31.14。帶有 random_spanning_tree() 的隨機路徑

示例 31.14 中介紹的算法會找到隨機路徑。 boost::random_spanning_tree() 類似于 boost::dijkstra_shortest_paths()。它返回通過 boost::predecessor_map 傳遞的容器中的點的前驅(qū)。與 boost::dijkstra_shortest_paths() 相比，起點不直接作為參數(shù)傳遞給 boost::random_spanning_tree()。它必須作為命名參數(shù)傳遞。這就是為什么在 boost::predecessor_map 類型的對象上調(diào)用 root_vertex()。示例 31.14 查找到左下角字段的隨機路徑。

因為 boost::random_spanning_tree() 正在尋找隨機路徑，所以必須將隨機數(shù)生成器作為第二個參數(shù)傳遞。示例 31.14 使用 std::mt19937，它自 C++11 以來一直是標準庫的一部分。您還可以使用 Boost.Random 中的隨機數(shù)生成器。

示例 31.14 顯示 1、0 和 3 或 1、2 和 3。1 是右上角的字段，3 是左下角的字段。從右上場到左下場只有兩種可能的路徑：通過左上場或通過右下場。 boost::random_spanning_tree() 必須返回這兩個路徑之一。

練習

為以下國家/地區(qū)創(chuàng)建具有頂點的圖形：荷蘭、比利時、法國、德國、瑞士、奧地利和意大利。用共同邊界連接這些國家的頂點。找到從意大利到荷蘭的最短路徑——過境次數(shù)最少的路徑。將所有國家/地區(qū)的名稱寫入您從意大利到荷蘭的途中經(jīng)過的標準輸出。

擴展您的計劃：現(xiàn)在進入法國花費 10 歐元，進入比利時 15 歐元，進入德國 20 歐元?？缭剿衅渌吔缛匀皇敲赓M的。找到最短的路徑——過境點最少的路徑——這也是從意大利到荷蘭的最便宜的路徑。將所有國家/地區(qū)的名稱寫入您從意大利到荷蘭的途中經(jīng)過的標準輸出。

到此這篇關(guān)于C++ Boost Graph算法超詳細精講的文章就介紹到這了,更多相關(guān)C++ Boost Graph 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！