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