图论学习（一）使用Boost Graph Library表示图

本文通过使用Boost Graph Library来实现图的新建和遍历。

1.Boost Graph Library库的安装

Boost Graph Library库属于boost库，因此安装boost库就行了。linux系统使用以下命令安装

apt-get install libboost-dev

2.新建图（增加点和边）

新建邻接图使用adjacency_list

#include <boost/graph/adjacency_list.hpp>
using namespace boost;
int main()
{
//1.新建无向图，使用邻接矩阵数据结构
boost::adjacency_list<listS, vecS, undirectedS> g;
//2.增加节点和边方法
add_edge(0, 1, g);
add_edge(1, 4, g);
add_edge(4, 0, g);
add_edge(2, 5, g);
}

3.遍历顶点

遍历点的思路如下
（1）定义顶点迭代器类型（typedef graph_traits::vertex_iterator vertex_iter;）
（2）创建一个pair容器，容器的数据成员类型为顶点迭代器
（3）调用 vertices(g)函数将指针指向pair。
（4）新建顶点迭代器vi遍历图中的顶点。

#include <iostream> // for std::cout
#include <utility> // for std::pair
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
using namespace boost;
using namespace std;
int main()
{
    //1.新建无向图，使用邻接矩阵数据结构
  typedef adjacency_list<listS, vecS, undirectedS > Graph;
    Graph g;
    //2.增加节点和边方法
    add_edge(0, 1, g);
    add_edge(1, 4, g);
    add_edge(4, 0, g);
    add_edge(2, 5, g);

    //3.遍历点
    typedef graph_traits<Graph>::vertex_iterator vertex_iter;
    pair<vertex_iter, vertex_iter> vip;
    cout << "Vertices in g  = [ ";
    vip = vertices(g);
    for(vertex_iter vi = vip.first; vi != vip.second; ++vi) {
        cout << *vi << " ";
    }
    cout<<"]"<<endl;
    return 0;
}

4.遍历边

遍历边的思路如下
（1）定义边迭代器类型（typedef graph_traits::vertex_iterator vertex_iter;）
（2）创建一个pair容器，容器的数据成员类型为边迭代器
（3）调用 edges(g)函数将指针指向pair。
（4）新建边迭代器ei遍历图中的顶点。

#include <iostream> // for std::cout
#include <utility> // for std::pair
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;
using namespace std;
int main()
{
    //1.新建无向图，使用邻接矩阵数据结构
  typedef adjacency_list<listS, vecS, undirectedS > Graph;
    Graph g;
    //2.增加节点和边方法
    add_edge(0, 1, g);
    add_edge(1, 4, g);
    add_edge(4, 0, g);
    add_edge(2, 5, g);
    //3.遍历点
    typedef graph_traits<Graph>::vertex_iterator vertex_iter;
    pair<vertex_iter, vertex_iter> vip;
    cout << "Vertices in g  = [ ";
    vip = vertices(g);
    for(vertex_iter vi = vip.first; vi != vip.second; ++vi) {
        cout << *vi << " ";
    }
    cout<<"]"<<endl;
    //4.遍历边方法1
    typedef graph_traits<Graph>::edge_iterator  edge_iter ;
    pair<edge_iter, edge_iter> eip;
    eip=edges(g);
    cout << "Edge in g  = [ ";
    for(edge_iter ei = eip.first; ei != eip.second; ++ei) {
        //cout << *ei << " ";
        cout<<"( source edge="<< source(*ei, g) ;
        cout<< " taget edge="<<target(*ei, g) <<")"<<endl;
    }
    cout<<"]"<<endl;
    return 0;
}

5.常用操作

（1）定义边迭代器
typedef graph_traits::edge_iterator edge_iter ;
（2）获得边的map
property_map