利用vector实现邻接表建图

我们为什么要使用邻接表？

众所周知，图的存储方式有很多，比如邻接矩阵、邻接表、十字链表、边集数组等等。对于刚刚进行算法竞赛学习的弱弱来说，最常用的可能就是邻接矩阵了，简单明了，操作方便，运用在各类dfs、bfs题目中可谓是一招鲜吃遍天。

但是，当我们进入到图论算法的学习中，就可能会开始发现邻接矩阵使用起来并不是那么得心应手了。当一张图中顶点很多但是边却不多的时候，如果运用邻接矩阵来存储的话，那么遍历起来就会耗费很多的时间。

举一个比较极端的例子，一张图中有10000个顶点，但是只有100条边，当它用邻接矩阵存储时，遍历的过程要进行10000*10000次操作。这个时候，即使算法正确，样例能过，然而往往在提交之后会因为某个数据量很大的数据而超时。而如果用邻接表来存储，只需要进行100次操作即可，极大程度上缩短了运行时间。

（关于邻接表的相关知识就不再赘述，若暂时不太清楚或已经遗忘，可上网搜索相关资料、博客进行学习，或是参考《大话数据结构》）

vector 简介及基本操作

1. 简介

vector是c++中stl库中封装好的容器，常用定义不定长数组来构建无向图或有向图。

简单来说vector就是一个长度可以变化的数组，c语言中的数组只能存放数字或字符，而vector基本上可以存放任何类型的数据，如struct(也可以直接用结构体数组)、string、pair等。

所以从实际效果上看vector就等同于链表

2. 基本操作：

(1)头文件

#include <vector>

(2)创建vector对象

vector<int>  vec;

(3)尾部插入元素

vec.push_back(a);

(4)使用下标访问元素

cout<<vec[0]<<endl;//记住下标是从0开始的。

(5)使用迭代器访问元素

vector<int>::iterator it;
for(it=vec.begin();it!=vec.end();it++)
	cout<<*it<<endl;

(6)插入元素:

vec.insert(vec.begin()+i,a);//在第i+1个元素前面插入a;

(7)删除元素:

vec.erase(vec.begin()+2);//删除第3个元素
vec.erase(vec.begin()+i,vec.end()+j);//删除区间[i,j-1];区间从0开始

(8)向量大小:

vec.size();

(9)清空:

vec.clear();

vector的元素不仅仅可以使int,double,string,还可以是结构体，但是要注意：结构体要定义为全局的，否则会出错。如下例：

struct node {int s, t, v;};
vector <node>G[ ];

构建图

1.定义不定长数组

vector <int> map(100010) ;

2.建边

for(i=1;i<=n;i++)
{

    scanf("%d %d",&s,&t);
    map[s].push_back(t);
    map[t].push_back(s); //有向图时，此步省略。
}

3.遍历

for(i=0;i<=map[s].size();i++)
{
    printf("%d\n",map[s][i]);
}