表示图的一种简单方法是使用二维数组，称为邻接矩阵表示法。对于每条边（u,v），置A[u][v] = true。否则数组的项就是false。如果边有一个权，那么可以置A[u][v]等于该权，而使用一个很大或者很小的权作为标记表示不存在的边。这种表示方法的空间需求是O(|V^2|)(一般来说空间比时间重要)。如果图的边不是很多，那么这种表示方法的代价就太大了。若图是稠密的|E|=O(|V^2|),则邻接矩阵是合适的表示方法。
如果图是稀疏的，邻接表是更好的解决方法。使用邻接表的空间需求是O(|E|+|V|),可以使用list,vector来维护邻接表，使用vector时，需要将每一个vector都初始化为比默认值稍小一点的容量，否则就会浪费大量空间。
如果需要快速获得任何定点的邻接顶点，使用map会好些，键为顶点。
总结一下用不同方法表示图的优点
二维数组：简单
vector/list:节省空间
map:快速查找
原文：http://www.cnblogs.com/biong-blog/p/4164103.html