图论学习(一)使用Boost Graph Library表示图

时间:2023-02-03 20:48:56

本文通过使用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