這里多分析了三個點： 1. 兩種表示方式在另一個維度的比較； 2. 一種復(fù)雜應(yīng)用場景下的取舍辦法； 3. 經(jīng)典表示方法之外的黑科技。
眾所周知，在經(jīng)典的圖論里，圖的兩種表示方式為： 1. 鄰接矩陣； 2. 鄰接表。
先回顧一下，圖是由結(jié)點，以及結(jié)點之間的邊構(gòu)成的。結(jié)點一般編號為0，1，2，……，然后一條邊由<u, v[，w]>來定義，其中的u和v都是某個結(jié)點的編號（如果有w的話，表示這條邊的權(quán)重）。
圖還分為有向圖和無向圖，其實本質(zhì)上并沒區(qū)別，可以說一切圖都是有向圖，而無向圖只不過是每條有向邊都存在一條反方向的邊而已（兩個結(jié)點可以直接互通，謂之無向，在這里，“方向”表示通行的限制）。
先po一張統(tǒng)一的圖以便后續(xù)分析：
結(jié)點為：0, 1, 2邊為：<0, 1, 10>, <1, 2, 66>, <2, 0, 55>這張圖很明顯是一個三角形。
顧名思義，這種方式是用一個N*N的矩陣來表示圖，如果存在邊
0 10 00 0 6655 0 0優(yōu)點：可以在常數(shù)時間內(nèi)得到一條邊的權(quán)重；缺點：占用內(nèi)存多，特別是對于稀疏圖來說；缺點：沒法保證在O(e)時間內(nèi)遍歷某個結(jié)點的所有邊。稍微解釋一下，對于1，因為矩陣可以隨機(jī)存取元素，所以可以在常數(shù)時間內(nèi)知道兩個結(jié)點之間是否存在一條邊。 對于2，很明顯矩陣占用的內(nèi)存是頂點的數(shù)量的平方，對于稀疏圖來說，很浪費內(nèi)存。 對于3，比如想遍歷結(jié)點1的所有邊（在這里只有1條），但沒法只訪問1次，而是必須得訪問V（=3）次，才能得出所有與1相鄰的邊。
用矩陣對于稀疏圖來說，太過浪費內(nèi)存，所以不妨只記錄每個結(jié)點相鄰的結(jié)點，比如vector<vector<pair<int, int> > > >就是一個鏈表的數(shù)組。
用鏈表來表示上面的圖便是：
0 -> [<1, 10>]1 -> [<2, 66>]2 -> [<0, 55>]優(yōu)點：相對省內(nèi)存，如果E < N*N的話；優(yōu)點：可以在O(e)時間內(nèi)遍歷某個結(jié)點的所有邊；缺點：沒法在常數(shù)時間內(nèi)獲取一條邊的權(quán)重。對于1，鄰接鏈表存儲的元素數(shù)量等于邊的數(shù)量，對于稀疏圖來說，很明顯是節(jié)省內(nèi)存的。 對于2，由于某個結(jié)點對應(yīng)的鏈表就是與它相鄰的所有邊，自然可以在O(e)時間內(nèi)遍歷完。 對于3，由于是用鏈表存儲的，沒法隨機(jī)訪問，所以必須遍歷鏈表來得到具體的某條邊的權(quán)重。
普通情況下，只需要按照上面提到的優(yōu)缺點便可以輕松取舍，比如稠密圖就用鄰接矩陣?yán)玻∈鑸D并且不需要在常數(shù)時間內(nèi)獲取一條邊的權(quán)重的就用鄰接表啦……
但是，在這樣一種較復(fù)雜的情況下，該用什么——
既需要在常數(shù)時間內(nèi)獲取一條邊的權(quán)重，又需要在O(E)時間內(nèi)遍歷某個結(jié)點的所有邊。
注意，這里不需要省內(nèi)存了。
回答這個問題之前，可能一個正常人會先問：真的有這樣的場景嗎？
有的，這種需求在圖論算法的實現(xiàn)中比比皆是，比如最近重新寫Dijkstra算法，首先需要在常數(shù)時間內(nèi)獲取某條邊的權(quán)重（因為需要用來計算最短路徑）；其次，每次一個結(jié)點出隊時，我需要遍歷它的所有相鄰的邊，來“疏松”路徑。
那該怎么辦呢？看上去水火不相容啊？
其實我的解決辦法很簡單，兩種表示法都用，然后各取其長處即可！這樣自然沒法省內(nèi)存了，不過時空博弈從來如此。
最后面有具體的實例。
其實很容易想到其它的數(shù)據(jù)結(jié)構(gòu)來表示圖，比如用map<pair<int, int>, int>，map的鍵是結(jié)點對<u, v>，map的值是該邊的權(quán)重。
這樣的數(shù)據(jù)結(jié)構(gòu)可以在log(E)（注意是大寫的E）的時間內(nèi)獲取某條邊的權(quán)重，但是……沒法獲取某個頂點相鄰的邊，只能用其它的數(shù)據(jù)結(jié)構(gòu)來保存，比如vector<vector<int> >保存的是所有邊的信息，這里和鄰接表唯一不同的地方就是，沒有保存權(quán)重，因為權(quán)重是用上述的map來保存。
把這兩者結(jié)合起來的好處是，當(dāng)log(E)普遍遠(yuǎn)遠(yuǎn)小于e時，這樣做的總體效率會比鄰接表好一些～
有沒有必要搞這樣一個“四不像”出來呢？應(yīng)該是有的，就是，圖比較稠密，且頂點的數(shù)量太大以至于沒法開一個矩陣來存放時！
或許會有更好的solution也說不定。
舉個例子，我為了調(diào)用簡單，把這兩種表示方法都寫成了類，先看看是如何調(diào)用的：
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;}新聞熱點
疑難解答
