这里多分析了三个点： 1. 两种表示方式在另一个维度的比较； 2. 一种复杂应用场景下的取舍办法； 3. 经典表示方法之外的黑科技。
众所周知，在经典的图论里，图的两种表示方式为： 1. 邻接矩阵； 2. 邻接表。
先回顾一下，图是由结点，以及结点之间的边构成的。结点一般编号为0，1，2，……，然后一条边由<u, v[，w]>来定义，其中的u和v都是某个结点的编号（如果有w的话，表示这条边的权重）。
图还分为有向图和无向图，其实本质上并没区别，可以说一切图都是有向图，而无向图只不过是每条有向边都存在一条反方向的边而已（两个结点可以直接互通，谓之无向，在这里，“方向”表示通行的限制）。
先po一张统一的图以便后续分析：
结点为：0, 1, 2边为：<0, 1, 10>, <1, 2, 66>, <2, 0, 55>这张图很明显是一个三角形。
顾名思义，这种方式是用一个N*N的矩阵来表示图，如果存在边
0 10 00 0 6655 0 0优点：可以在常数时间内得到一条边的权重；缺点：占用内存多，特别是对于稀疏图来说；缺点：没法保证在O(e)时间内遍历某个结点的所有边。稍微解释一下，对于1，因为矩阵可以随机存取元素，所以可以在常数时间内知道两个结点之间是否存在一条边。 对于2，很明显矩阵占用的内存是顶点的数量的平方，对于稀疏图来说，很浪费内存。 对于3，比如想遍历结点1的所有边（在这里只有1条），但没法只访问1次，而是必须得访问V（=3）次，才能得出所有与1相邻的边。
用矩阵对于稀疏图来说，太过浪费内存，所以不妨只记录每个结点相邻的结点，比如vector<vector<pair<int, int> > > >就是一个链表的数组。
用链表来表示上面的图便是：
0 -> [<1, 10>]1 -> [<2, 66>]2 -> [<0, 55>]优点：相对省内存，如果E < N*N的话；优点：可以在O(e)时间内遍历某个结点的所有边；缺点：没法在常数时间内获取一条边的权重。对于1，邻接链表存储的元素数量等于边的数量，对于稀疏图来说，很明显是节省内存的。 对于2，由于某个结点对应的链表就是与它相邻的所有边，自然可以在O(e)时间内遍历完。 对于3，由于是用链表存储的，没法随机访问，所以必须遍历链表来得到具体的某条边的权重。
普通情况下，只需要按照上面提到的优缺点便可以轻松取舍，比如稠密图就用邻接矩阵啦，稀疏图并且不需要在常数时间内获取一条边的权重的就用邻接表啦……
但是，在这样一种较复杂的情况下，该用什么——
既需要在常数时间内获取一条边的权重，又需要在O(E)时间内遍历某个结点的所有边。
注意，这里不需要省内存了。
回答这个问题之前，可能一个正常人会先问：真的有这样的场景吗？
有的，这种需求在图论算法的实现中比比皆是，比如最近重新写Dijkstra算法，首先需要在常数时间内获取某条边的权重（因为需要用来计算最短路径）；其次，每次一个结点出队时，我需要遍历它的所有相邻的边，来“疏松”路径。
那该怎么办呢？看上去水火不相容啊？
其实我的解决办法很简单，两种表示法都用，然后各取其长处即可！这样自然没法省内存了，不过时空博弈从来如此。
最后面有具体的实例。
其实很容易想到其它的数据结构来表示图，比如用map<pair<int, int>, int>，map的键是结点对<u, v>，map的值是该边的权重。
这样的数据结构可以在log(E)（注意是大写的E）的时间内获取某条边的权重，但是……没法获取某个顶点相邻的边，只能用其它的数据结构来保存，比如vector<vector<int> >保存的是所有边的信息，这里和邻接表唯一不同的地方就是，没有保存权重，因为权重是用上述的map来保存。
把这两者结合起来的好处是，当log(E)普遍远远小于e时，这样做的总体效率会比邻接表好一些～
有没有必要搞这样一个“四不像”出来呢？应该是有的，就是，图比较稠密，且顶点的数量太大以至于没法开一个矩阵来存放时！
或许会有更好的solution也说不定。
举个例子，我为了调用简单，把这两种表示方法都写成了类，先看看是如何调用的：
int main() { int n, e, u, v, w; cin >> n >> e; AdjacencyMatrix am(n); AdjacencyList al(n); while (e--) { cin >> u >> v >> w; am.insertEdge(u, v, w); al.insertEdge(u, v, w); } int s, t; while (cin >> s >> t) { dijkstra(am, al, s, t); } return 0;}完整的代码请移步：http://paste.Ubuntu.com/23929990/。
然后AdjacencyMatrix和AdjacencyList具体是这样的：
// DirectedGraph.h#ifndef __Directed_Graph_H__#define __Directed_Graph_H__#include <vector>#include <iostream>using namespace std;typedef int weight_t;const weight_t INFINITE = 1e9;class AdjacencyMatrix{public: AdjacencyMatrix(size_t n); int getWeight(size_t u, size_t v) const; void insertEdge(size_t u, size_t v, weight_t w); size_t getNumberOfNode() const;PRivate: vector<vector<weight_t> > data; size_t numberOfNode;};class AdjacencyList{public: AdjacencyList(size_t n); int getWeight(size_t u, size_t v) const; void insertEdge(size_t u, size_t v, weight_t w); const vector<vector<size_t> >& getEdges() const; size_t getNumberOfNode() const;private: size_t numberOfNode; vector<vector<size_t> > edges; vector<vector<weight_t> > weights;};#endif//DirectedGraph.cpp#include "DirectedGraph.h"AdjacencyMatrix::AdjacencyMatrix(size_t n): data(n, vector<weight_t>(n, INFINITE)), numberOfNode(n) {}int AdjacencyMatrix::getWeight(size_t u, size_t v) const { return data[u][v];}void AdjacencyMatrix::insertEdge(size_t u, size_t v, weight_t w) { data[u][v] = w;}size_t AdjacencyMatrix::getNumberOfNode() const { return numberOfNode;}// =====华丽丽的～分隔线======AdjacencyList::AdjacencyList(size_t n): edges(n), weights(n), numberOfNode(n) {}int AdjacencyList::getWeight(size_t u, size_t v) const { for (int i = 0; i < edges[u].size(); ++i) { if (edges[u][i] == v) return weights[u][i]; } return INFINITE;}void AdjacencyList::insertEdge(size_t u, size_t v, weight_t w) { edges[u].push_back(v); weights[u].push_back(w);}const vector<vector<size_t> >& AdjacencyList::getEdges() const { return edges;}size_t AdjacencyList::getNumberOfNode() const { return numberOfNode;}新闻热点
疑难解答
