Boost 图类库简介
图（Graph）是一种数学抽象，可用于解决计算机科学领域中的多种问题。因此，这种抽象必须也用计算机程序表示出来。一个用于遍历图的标准化的范型接口，对于促进对图算法和数据结构的重用，具有无可比拟的重要性。Boost 图类库（BGL）的一部分是一个可用于访问图的结构的范型接口，同时隐藏了其实现细节。这是一个“开放”的接口，这意味着任何实现了该接口的图类库，都将可以与 BGL 范型算法（或是其他使用了该接口的算法）相互协作。BGL 提供了一些遵循该接口的通用目的的图类，但它们并不企图成为“唯一”的图类；肯定会有其他图类更适合于特定场合。我们相信，BGL 的主要贡献将是对该接口的指定。
BGL 图接口和图组件是泛型的，如同标准模板库（STL）。在下一节中，我们将回顾泛型编程在 STL 中扮演的角色，并将其与我们在图背景下应用泛型编程相比较。
当然，如果你已经熟悉泛型编程，大可以跳过这一节！这里是目录。对于分布式内存并行性，你还可以查看并行 BGL。
BGL 的源代码作为 Boost 发行版的一部分提供，你可以从这里下载。
如何构建 BGL
根本不用！Boost 图类库是一个仅包含头文件的库，不需要构建即可使用。唯一的例外是 GraphViz 输入解析器 和 GraphML 解析器。
编译使用 BGL 的程序时，请务必进行优化编译。例如，使用 Microsoft Visual C++ 选择“Release”模式或给 GCC 加上 -O2 或 -O3 选项。
STL 中的泛型
STL 以三种方式体现出它是范型的。
算法/数据结构互操作性
首先，每个算法都以数据结构中立的方式编写，允许单个模板函数在许多不同的容器类上操作。迭代器的概念是算法和数据结构解耦的关键因素。这种技术的影响是将 STL 的代码大小从
可扩展性（通过函数对象）
其次，STL 的算法和容器是可扩展的。用户可以通过使用函数对象来调整和定制 STL。正是这种灵活性使 STL 成为解决实际问题的绝佳工具。每个编程问题都会带来它自己的实体集合和需要建模的交互。函数对象提供了这样一种机制来扩展 STL，使其能处理每个问题领域的细节。
元素类型的参数化
第三，STL容器的元素类型是参数化的。虽然这点非常重要，但它可能是最不有趣的一种方式。范性编程常常被简单地总结为参数化的列表，如 std::list<T>。但这只是冰山一角！
Boost 图类库中的范型
与 STL 一样，BGL 也以三种方式体现出它是范型的。
算法/数据结构的互操作性
首先，BGL 的图算法是按照一个抽象掉了特定的图结构的细节的接口写成的。和 STL 一样，BGL 使用迭代器来定义数据结构遍历的接口。有三种不同的图遍历模式：遍历图的所有顶点，经过所有的边，以及沿着图的邻接结构（从一个顶点到它的邻居）。对每一种遍历模式，都有一种专门的迭代器。
该范型接口使得像 breadth_first_search() 这样的模板函数可以工作于多种多样的图结构之上，无论是以指针链接的节点实现的图，还是编码在数组里的图。这种弹性对于图论领域尤其重要。图结构常常是为特定的应用定制的。在以前，如果程序员想要重用一个算法实现他们必须将他们的图数据转换/复制到图类库的规定的图结构。在使用像LEDA, GTL, Stanford GraphBase 这样的库的时候，正是这样；对于用 Fortran 写成的图算法，就更是如此。这严重地限制了它们的图算法的重用。
相反，通过外部适配（external adaptation，参见小节如何将既有图转换为 BGL）定制的（或者甚至是遗留的）图结构可以原封不动地与 BGL 范型图算法共同使用。外部适配将一个新的接口包裹在一个数据结构外面，无需复制，也无需将数据放在适配对象里。BGL 的接口经过仔细的设计，以使这个适配的过程尽可能简单。为了演示这一点，在 BGL 图算法中，我们为多种图结构（LEDA 图、Stanford GraphBase 图，甚至 Fortran 风格的数组）构建了接口连接代码。
可扩展性（通过 Visitor）
其次，BGL 的图算法是可扩展的。BGL 引入了 visitor（访问子）的概念，其实它只是一个有多个方法的函数对象。在图算法中，常常需要在一些关键点（event points）插入用户定义的操作。访问子对象有一个不同的、只在关键点才调用的方法。具体的关键点以及相应的访问子方法依具体的算法而定。它们通常包括 start_vertex()、discover_vertex()、examine_edge()、tree_edge() 和 finish_vertex() 等方法。
顶点和边属性多重参数化
BGL 的第三种范型方式，类似于 STL 容器中的元素类型的参数化，可是情况比 STL 容器要复杂一些。我们既需要将值（称为“属性”）关联于图的顶点，也需要关联于边。另外，常常需要将多重属性关联于每个顶点和每条边；这正是所谓的多重参数化。STL 的 std::list<T> 类有一个参数 `T`` 指定它的元素类型。相似地，BGL 图类有对应于顶点和边的属性的模板参数。一个属性参数指定属性的参数化的类型，同时给该属性分派一个识别标签。这个标签用于区分开一个顶点或边所具有的多个属性。关联于一个特定的顶点或边的属性值，可以经由一个属性映射表（property map）获得。对每一个属性，都有一张单独的属性映射表。
传统的图库和图结构会在遇到图属性参数化时变得无能为力。这是图结构必须为具体应用定制的一个主要原因。BGL 中的图类中属性的参数化使得它们非常适合于重用。
算法
BGL 算法由一组核心算法模式（实现为范型算法）和一组更大的图算法组成。核心算法模式有：
- 广度优先搜索（Breadth First Search）
- 深度优先搜索（Depth First Search）
- 成本一致搜索（Uniform Cost Search）
这些算法模式自身并不对图计算任何有意义的量；他们只是构造图算法的建筑基石。目前 BGL 中的图算法包括：
- Dijkstra 最短路径（Dijkstra’s Shortest Paths）
- Bellman-Ford 最短路径（Bellman-Ford Shortest Paths）
- Johnson 全源最短路径（Johnson’s All-Pairs Shortest Paths）
- Kruskal 最小生成树（Kruskal’s Minimum Spanning Tree）
- Prim 最小生成树（Prim’s Minimum Spanning Tree）
- 连通分量（Connected Components）
- 强连通分量（Strongly Connected Components）
- 动态连通分量（使用不相交集）（Dynamic Connected Components (using Disjoint Sets)）
- 拓扑排序（Topological Sort）
- 转置（Transpose）
- 逆向 Cuthill Mckee 序（Reverse Cuthill Mckee Ordering）
- 最小最后顶点序（Smallest Last Vertex Ordering）
- 顺序顶点染色（Sequential Vertex Coloring）
数据结构
BGL 目前提供了两个图类和一个边链表适配器：
adjacency_list 类是通用目的的，是图类中的瑞士军刀。它是高度参数化的，因此它可以为不同场合进行优化：图是有向的还是无向的，是否允许平行边，只可以高效访问出边还是也可高效访问入边，快速顶点插入与删除的额外空间开销等等。
adjacency_matrix 将边储存在一个
edge_list 类是一个适配器，它接受任何类型的边迭代器实现一个边链表图（Edge List Graph）。