工业上有很多非常好的图库的实现,例如C++的boost graph库.如果可以，尽量用这些库，这样可以大大提高你的效率。

注意：

n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。(换句话说，每条边（i,j）在邻接表 中出现两次：一次在关于i的邻接表中，另一次在关于j的邻接表中)

对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。

【例】有向图G6如下图所示，其中顶点v1的邻接表上两个表结点中的顶点序号分别为0和4，它们分别表示从v1射出的两条边(简称为v1的出边)：和。

注意：

n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。（因为有向图是单向的）

在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。

入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。

注意：

n个顶点e条边的有向图，它的逆邻接表表示中有n个顶点表结点和e个边表结点。

邻接表是一个二维容器，第一维描述某个点，第二维描述这个点所对应的边集们。

实现邻接表的方法绝对有100种以上。即使是前向星这种东西也是邻接表，因为它还是描述某个点和这个点所对应的边集们.

我们说说常用的邻接表存图法（静态的array就不说了.）必须有开O1以及以上编译的条件，不然没有测试的效率无任何意义。

第一维是描述点的。可以用vector,list,forward_list,deque,map,multimap,unordered_map,unordered_multimap等（一般不能用set,mutiset,unordered_set,unordered_multiset）.

按照你的要求去选择。一般来讲存完图以后不涉及点的加入与删除优先使用vector.map,multimap,unordered_map,unordered_multimap.

第二维是描述这个点的边集，可以用全部的容器。也是的一般来讲存完图以后,不涉及点的加入与删除优先使用vector,空间充足可以考虑deque.涉及点的删除用forward_list或者是list,map,multimap,unordered_map,unordered_multimap.

对于这个图存储的方法举例(对于上面的图):

第一种:

对第一种方法有种优化就是对每个点所对应的边的向量进行预估。例如有m条有向边，n个点，那么每个向量需要reserve(6*(m/n)/5);一般这样存储效率会有显著提高。

第二种(使用map,set):

方法太多，不再举例了。

然而我们这样存图是不够的，对于无向图而言，可能存在一条边需要知道自己的反向边的位置。例如欧拉回路，例如网络流都是需要的。

第二种方法由于std::map

然而对于第一种方法，我们没有办法解决反向边的互相访问题。

所以我们对于这种图需要存图修正。代码如下:

对于list容器可以直接存迭代器的，但是存图时也得考虑a是否等于b.forward_list存反向边的图就不好，因为用链表存图就是需要存完图后插入删除，假定一个元素前面的元素被删除了，那么根本无法访问反向边!!!!

感觉存图没问题了？NO!!!!还有一种图更奇葩，那就是对于每个点中的边得排序又得知道反向边的那种图。USACO上有个题目叫做骑马修栅栏，那个题要求字典序输出。数据量很小，以至于可以直接矩阵存图，但是我们考虑如何数据量大，这种方法就不行了。如果用第二种方法（std::map）

方法就是先用边集表存图，然后每条边a,b得优先以std::min(a,b)为第一关键字再按std::max(a,b)为第二关键字排序，再按照修正后的存图方法存图即可。具体代码见nocow上骑马修栅栏那题lgeecn发的题解和代码。

如果使用list存图可以先存图再用list.sort( )函数进行排序，不过似乎效率会差一些,毕竟相对于vector,list常数太大了，达到6倍以上。

存图真心不简单，因为真正用的时候你可能会遇到各种问题，但是你可以加以思考，进行容器搭配使用，即可解决。

无向图只要在addd过程中反过来再new一遍就可以了