关于计算的公理表达通常颇具争论。然而，现代计算最重要的理论支柱之一的图论并不是这些公理表达之一。无数工程领域（从设计路由器和网络到设计构成移动设备核心的芯片）都是图论的应用。
作为 C++++ 应用程序软件">开发人员，我们通常需要直接将实际工程问题转化成一个等价的图论问题。如果有一个可靠的基于 C++ 的通用图库，就可以帮助我们实现这个转换，这样的图库显然非常受欢迎：Boost Graph Library (BGL) 将填补这项空白。
在本文中，您首先将创建一个无向图，然后按照常规的遍历例程创建一个有向图。随后，您可以应用一些经典算法，所有算法都不需要添加大量代码。这就是 BGL 的神奇之处。
下载和安装
BGL 可从 Boost 网站免费下载。BGL 是一个仅有头文件的库，因此，以后在应用程序代码中使用该库时，需要在源代码中包含相关的头文件。但是 BGL 需要这个序列化库来进行链接。以下是一个典型的命令行格式：
root# g++ test_bgl.cpp I/usr/boost/boost_1_44/ -L/usr/boost/boost_1_44/lib
如果要试验本文中的代码，您需要安装 Boost 1.44 版本。
邻接表（Adjacency lists）
任何图实现的头文件中都有一个邻接表 (adjacency list) 或邻接矩阵。清单 1 显示了在 Boost 头文件 adjacency_list.hpp 中如何声明邻接表。
清单 1. 在 Boost 中声明一个邻接表
template <class OutEdgeListS = vecS, // a Sequence or an AssociativeContainer class VertexListS = vecS, // a Sequence or a RandomAccessContainer class DirectedS = directedS, class VertexProperty = no_property, class EdgeProperty = no_property, class GraphProperty = no_property, class EdgeListS = listS> class adjacency_list { };
为了简便起见，我们将重点放在前三个模板参数。
OutEdgeList 模板参数决定了将用于存储边列表（ edge-list）信息的容器类型。回顾一下图论基础知识就可以知道，对于有向图，只具有入边的那些顶点都有一个对应的空邻接表。默认值被设置为 vecS，该值对应于 std::vector。VertexList 模板参数决定了用于表示该图顶点列表的容器类型，默认值同样被设置为 std::vector。DirectedS 模板参数根据提供的值是 directedS 还是 undirectedS 来确定该图是有向图还是无向图。
在 BGL 中创建一个图
在声明邻接表的同时，清单 2 中的代码在 BGL 中创建了一个简单的无向图，边信息将存储在 std::list 中，顶点信息存储在 std::vector 中。
清单 2. 创建一个无向图
#include <boost/graph/adjacency_list.hpp> using namespace boost; typedef boost::adjacency_list<listS, vecS, undirectedS> mygraph; int main() { mygraph g; add_edge (0, 1, g); add_edge (0, 3, g); add_edge (1, 2, g); add_edge (2, 3, g); }
在清单 2 中，在没有在构造函数中提供任何顶点或边信息的情况下创建了图 g。在运行的时候，会使用诸如 add_edge 和 add_vertex 之类的帮助函数创建边和顶点。add_edge 函数，顾名思义：在一个图的两个顶点之间添加一条边。清单 2 中的代码执行结束后，图 g 应该有 4 个顶点，分别标记为 0、1、2 和 3，顶点 1 与顶点 0 和顶点 2 连接，等等。