介紹：細處著手，巧處用功。高手和菜鳥之間的差別就是：高手什麼都知道，菜鳥知道一些。電腦小技巧收集最新奇招高招，讓你輕松踏上高手之路。(首月免費) 圖的應用恐怕是所有數據結構中最寬泛的了，但這也注定了在講“數據結構的圖”的時候沒什麼好講的——關於圖的最重要的是算法，而且相當的一部分都是很專業的，一般的人幾乎不會接觸到；相對而言，結構就顯得分量很輕。你可以看到關於圖中元素的操作很少，遠沒有單鏈表那裡列出的一大堆“接口”。——一個結構假如復雜，那麼能確切定義的操作就很有限。
基本儲存方法
不管怎麼說，還是先得把圖存起來。不要看書上列出了好多方法，根本只有一個——鄰接矩陣。假如矩陣是稀疏的，那就可以用十字鏈表來儲存矩陣（見前面的《稀疏矩陣（十字鏈表）》）。假如我們只關系行的關系，那麼就是鄰接表（出邊表）；反之，只關心列的關系，就是逆鄰接表（入邊表）。
下面給出兩種儲存方法的實現。
#ifndef Graphmem_H
#define Graphmem_H
#include <vector>
#include <list>
using namespace std;
template <class name, class dist, class mem> class Network;
const int maxV = 20;//最大節點數
template <class name, class dist>
class AdjMatrix
{
friend class Network<name, dist, AdjMatrix<name, dist> >;
public:
AdjMatrix() : vNum(0), eNum(0)
{
vertex = new name[maxV]; edge = new dist*[maxV];
for (int i = 0; i < maxV; i++) edge[i] = new dist[maxV];
}
~AdjMatrix()
{
for (int i = 0; i < maxV; i++) delete []edge[i];
delete []edge; delete []vertex;
}
bool insertV(name v)
{
if (find(v)) return false;
vertex[vNum] = v;
for (int i = 0; i < maxV; i++) edge[vNum][i] = NoEdge;
vNum++; return true;
}
bool insertE(name v1, name v2, dist cost)
{
int i, j;
if (v1 == v2 !find(v1, i) !find(v2, j)) return false;
if (edge[i][j] != NoEdge) return false;
edge[i][j] = cost; eNum++; return true;
}
name& getV(int n) { return vertex[n]; } //沒有越界檢查
int nextV(int m, int n)//返回m號頂點的第n號頂點後第一個鄰接頂點號，無返回-1
{
for (int i = n + 1; i < vNum; i++) if (edge[m][i] != NoEdge) return i;
return -1;
}
private:
int vNum, eNum;
dist NoEdge, **edge; name *vertex;
bool find(const name& v)
{
for (int i = 0; i < vNum; i++) if (v == vertex[i]) return true;
return false;
}
bool find(const name& v, int& i)
{
for (i = 0; i < vNum; i++) if (v == vertex[i]) return true;
return false;
}
};
template <class name, class dist>
class LinkedList
{
friend class Network<name, dist, LinkedList<name, dist> >;
public:
LinkedList() : vNum(0), eNum(0) {}
~LinkedList()
{
for (int i = 0; i < vNum; i++) delete vertices[i].e;
}
bool insertV(name v)
{
if (find(v)) return false;
vertices.push_back(vertex(v, new list<edge>));
vNum++; return true;
}
bool insertE(const name& v1, const name& v2, const dist& cost)
{
int i, j;
if (v1 == v2 !find(v1, i) !find(v2, j)) return false;
for (list<edge>::iterator iter = vertices[i].e->begin();
iter != vertices[i].e->end() && iter->vID < j; iter++);
if (iter == vertices[i].e->end())
{
vertices[i].e->push_back(edge(j, cost)); eNum++; return true;
}
if (iter->vID == j) return false;
vertices[i].e->insert(iter, edge(j, cost)); eNum++; return true;
}
name& getV(int n) { return vertices[n].v; } //沒有越界檢查
int nextV(int m, int n)//返回m號頂點的第n號頂點後第一個鄰接頂點號，無返回-1
{
for (list<edge>::iterator iter = vertices[m].e->begin();
iter != vertices[m].e->end(); iter++) if (iter->vID > n) return iter->vID;
return -1;
}
private:
bool find(const name& v)
{
for (int i = 0; i < vNum; i++) if (v == vertices[i].v) return true;
return false;
}
bool find(const name& v, int& i)
{
for (i = 0; i < vNum; i++) if (v == vertices[i].v) return true;
return false;
}
strUCt edge
{
edge() {}
edge(int vID, dist cost) : vID(vID), cost(cost) {}
int vID;
dist cost;
};
struct vertex
{
vertex() {}
vertex(name v, list<edge>* e) : v(v), e(e) {}
name v;
list<edge>* e;
};
int vNum, eNum;
vector<vertex> vertices;
};
#endif
這個實現是很簡陋的，但應該能滿足後面的講解了。現在這個還什麼都不能做，不要急，在下篇將講述圖的DFS和BFS。 更多內容請看C/C++技術專題 數據結構 數據結構教程專題，或 DFS和BFS
對於非線性的結構，遍歷都會首先成為一個問題。和二叉樹的遍歷一樣，圖也有深度優先搜索（DFS）和廣度優先搜索（BFS）兩種。不同的是，圖中每個頂點沒有了祖先和子孫的關系，因此，前序、中序、後序不再有意義了。
仿照二叉樹的遍歷，很輕易就能完成DFS和BFS，只是要注重圖中可能有回路，因此，必須對訪問過的頂點做標記。
最基本的有向帶權網
#ifndef Graph_H
#define Graph_H
#include <iostream>
#include <queue>
using namespace std;
#include "Graphmem.h"
template <class name, class dist, class mem>
class Network
{
public:
Network() {}
Network(dist maxdist) { data.NoEdge = maxdist; }
~Network() {}
bool insertV(name v) { return data.insertV(v); }
bool insertE(name v1, name v2, dist cost) { return data.insertE(v1, v2, cost); }
name& getV(int n) { return data.getV(n); }
int nextV(int m, int n = -1) { return data.nextV(m, n); }
int vNum() { return data.vNum; }
int eNum() { return data.eNum; }
protected:
bool* visited;
static void print(name v) { cout << v; }
private:
mem data;
};
#endif
你可以看到，這是在以mem方式儲存的data上面加了一層外殼。在圖這裡，邏輯上分有向、無向，帶權、不帶權；儲存結構上有鄰接矩陣和鄰接表。也就是說分開來有8個類。為了最大限度的復用代碼，繼續關系就非常復雜了。但是，多重繼續是件很討厭的事，什麼覆蓋啊，還有什麼虛擬繼續，我可不想花大量篇幅講語言特性。於是，我將儲存方式作為第三個模板參數，這樣一來就省得涉及虛擬繼續了，只是這樣一來這個Network的實例化就很麻煩了，不過這可以通過typedef或者外殼類來解決，我就不寫了。反正只是為了讓大家明白，真正要用的時候，最好是寫專門的類，比如無向無權鄰接矩陣圖，不要搞的繼續關系亂七八糟。
DFS和BFS的實現
public:
void DFS(void(*visit)(name v) = print)
{
visited = new bool[vNum()];
for (int i = 0; i < vNum(); i++) visited[i] = false;
DFS(0, visit);
delete []visited;
}
protected:
void DFS(int i, void(*visit)(name v) = print)
{
visit(getV(i)); visited[i] = true;
for (int n = nextV(i); n != -1; n = nextV(i, n))
if (!visited[n]) DFS(n, visit);
}
public:
void BFS(int i = 0, void(*visit)(name v) = print)//n沒有越界檢查
{
visited = new bool[vNum()]; queue<int> a; int n;
for (n = 0; n < vNum(); n++) visited[n] = false;
visited[i] = true;
while (i != -1)//這個判定可能是無用的
{
visit(getV(i));
for (n = nextV(i); n != -1; n = nextV(i, n))
if (!visited[n]) { a.push(n); visited[n] = true; }
if (a.empty()) break;
i = a.front(); a.pop();
}
delete []visited;
}
DFS和BFS函數很難寫得像樹的遍歷方法那麼通用，這在後面就會看到，雖然我們使用了DFS和BFS的思想，但是上面的函數卻不能直接使用。因為樹的信息主要在節點上，而圖的邊上還有信息。
測試程序
#include <iostream>
using namespace std;
#include "Graph.h"
int main()
{
Network<char, int, LinkedList<char, int> > a;
a.insertV('A'); a.insertV('B');
a.insertV('C'); a.insertV('D');
a.insertE('A', 'B', 1); a.insertE('A', 'C', 2);
a.insertE('B', 'D', 3);
cout << "DFS: "; a.DFS(); cout << endl;
cout << "BFS: "; a.BFS(); cout << endl;
return 0;
}
老實說，這個類用起來真的不是很方便。不過能說明問題就好。 更多內容請看C/C++技術專題 數據結構 數據結構教程專題，或 無向圖
要是在紙上隨便畫畫，或者只是對圖做點示范性的說明，大多數人都會選擇無向圖。然而在計算機中，無向圖卻是按照有向圖的方法來儲存的——存兩條有向邊。
實際上，當我們說到無向的時候，只是忽略方向——在紙上畫一條線，難不成那線“嗖”的就出現了，不是從一頭到另一頭畫出來的？ 無向圖有幾個特有的概念，連通分量、關節點、最小生成樹。下面將分別介紹，在此之前，先完成無向圖類的基本操作。
無向圖類
template <class name, class dist, class mem>
class Graph : public Network<name, dist, mem>
{
public:
Graph() {}
Graph(dist maxdist) : Network<name, dist, mem> (maxdist) {}
bool insertE(name v1, name v2, dist cost)
{
if (Network<name, dist, mem>::insertE(v1, v2, cost))
return Network<name, dist, mem>::insertE(v2, v1, cost);
return false;
}
};
僅僅是添加邊的時候，再添加一條反向邊，很簡單。
連通分量
這是無向圖特有的，有向圖可要復雜多了（強、單、弱連通），原因就是無向圖的邊怎麼走都行，有向圖的邊似乎掉下無底深淵就再也爬不上來了。有了DFS，求連通分量的算法就變得非常簡單了——對每個沒有訪問的頂點調用DFS就可以了。
void components()
{
visited = new bool[vNum()]; int i, j = 0;
for (i = 0; i < vNum(); i++) visited[i] = false;
cout << "Components:" << endl;
for (i = 0; i < vNum(); i++)
{
if (!visited[i]) { cout << '(' << ++j << ')'; DFS(i); cout << endl; }
}
delete []visited;
}
關節點
下定義是人們熟悉事物的一個方法，因為概念使得人們能夠區分事物——關於這個還有個絕對的運動和相對的靜止的哲學觀點（河水總在流，但是長江還叫長江，記得那個聞名的“不可能踏進同一條河裡”嗎？）因此，能否有個准確的概念往往是一門學科發展程度的標志，而能否下一個准確的定義反映了一個人的思維能力。說這麼多廢話，原因只有一個，我沒搞清楚什麼叫“關節點”——參考書有限，不能仔細的考究了，如有誤解，還望指正。
嚴版是這麼說的：假如刪除某個頂點，將圖的一個連通分量分割成兩個或兩個以上的連通分量，稱該頂點為關節點。——雖然沒有提到圖必須是無向的，但是提到了連通分量已經默認是無向圖了。
殷版是這麼說的：在一個無向連通圖中，……（余下同嚴版）。
問題出來了，非連通圖是否可以討論含有關節點？我們是否可以說某個連通分量中含有關節點？遺憾的是，嚴版留下這個問題之後，在後面給出的算法是按照連通圖給的，這樣當圖非連通時結果就是錯的。殷版更是滑頭，只輸出重連通分量，不輸出關節點，自己雖然假定圖是連通的，同樣沒有連通判定。
翻翻離散數學吧，結果沒找到什麼“關節點”，只有“割點”，是這樣的：一個無向連通圖，假如刪除某個頂點後，變為非連通圖，該頂點稱為割點。權當“割點”就是“關節點”，那麼算法至少也要先判定是否連通吧？可是書上都直接當連通的了……
關於算法不再細說，書上都有。下面的示例，能輸出每個連通分量的“關節點”（是不是可以這樣叫，我也不清楚）。dfn儲存的是每個頂點的訪問序號，low是深度優先生成樹上每個非葉子頂點的子女通過回邊所能到達的頂點最小的訪問序號。把指向雙親的邊也當成回邊並不影響判定，因此不必特意區分，殷版顯式區分了，屬於畫蛇添足。這樣一來，if (low[n] >= dfn[i]) cout << getV(i);這個輸出關節點的判定中的>=就顯得很尴尬了，因為只能等於不可能大於。還要注重的是，生成樹的根（DFS的起始點）是單獨判定的。
void articul()
{
dfn = new int[vNum()]; low = new int[vNum()]; int i, j = 0, n;
for(i = 0; i < vNum(); i++) dfn[i] = low[i] = 0;//初始化
for (i = 0; i < vNum(); i++)
{
if (!dfn[i])
{
cout << '(' << ++j << ')'; dfn[i] = low[i] = count = 1;
if ((n = nextV(i)) != -1) articul(n); bool out = false;//訪問樹根
while ((n = nextV(i, n)) != -1)
{
if (dfn[n]) continue;
if (!out) { cout << getV(i); out = true; }//樹根有不只一個子女
articul(n);//訪問其他子女
}
cout << endl;
}
}
delete []dfn; delete []low;
}
private:
void articul(int i)
{
dfn[i] = low[i] = ++count;
for (int n = nextV(i); n != -1; n = nextV(i, n))
{
if (!dfn[n])
{
articul(n);
if (low[n] < low[i]) low[i] = low[n];
if (low[n] >= dfn[i]) cout << getV(i);//這裡只可能＝
}
else if (dfn[n] < low[i]) low[i] = dfn[n];//回邊判定
}
}
int *dfn, *low, count;
說人是最難伺候的，真是一點不假。上面剛剛為了“提高可靠性”添加了幾條多余的邊，這會兒又來想辦法怎麼能以最小的代價把所有的頂點都連起來。 可能正是人的這種精神才使得人類能夠進步吧——看著現在3GHz的CPU真是眼紅啊，我還在受500MHz的煎熬，然後再想想8086……
正如圖的基本元素是頂點和邊，從這兩個方向出發，就能得到兩個算法——Kruskal算法（從邊出發）、Prim算法（從頂點出發）。據說還有別的方法，恕我參考資料有限，不能詳查。
最小生成樹的儲存
顯然用常用的樹的儲存方法來儲存沒有必要，雖然名曰“樹”，實際上，這裡誰是誰的“祖先”、“子孫”並不重要。因此，用如下的MSTedge結構數組來儲存就可以了。
template <class dist>
class MSTedge
{
public:
MSTedge() {}
MSTedge(int v1, int v2, dist cost) : v1(v1), v2(v2), cost(cost) {}
int v1, v2;
dist cost;
bool operator > (const MSTedge& v2) { return (cost > v2.cost); }
bool operator < (const MSTedge& v2) { return (cost < v2.cost); }
bool operator == (const MSTedge& v2) { return (cost == v2.cost); }
};
Kruskal算法
最小生成樹直白的講就是，挑選N－1條不產生回路最短的邊。Kruskal算法算是最直接的表達了這個思想——在剩余邊中挑選一條最短的邊，看是否產生回路，是放棄，不是選定然後重復這個步驟。說起來倒是很簡單，做起來就不那麼輕易了——判定是否產生回路需要並查集，在剩余邊中找一條最短的邊需要最小堆（並不需要對所有邊排序，所以堆是最佳選擇）。
Kruskal算法的復雜度是O(eloge)，當e接近N^2時，可以看到這個算法不如O(N^2)的Prim算法，因此，他適合於稀疏圖。而作為稀疏圖，通常用鄰接表來儲存比較好。另外，對於鄰接矩陣儲存的圖，Kruskal算法比Prim算法占不到什麼便宜（初始還要掃描N^2條“邊”）。因此，最好把Kruskal算法放在Link類裡面。
template <class name, class dist> int Link<name, dist>::MinSpanTree(MSTedge<dist>* a)
{
MinHeap<MSTedge<dist> > E; int i, j, k, l = 0;
MFSets V(vNum); list<edge>::iterator iter;
for (i = 0; i < vNum; i++)
for (iter = vertices[i].e->begin(); iter != vertices[i].e->end(); iter++)
E.insert(MSTedge<dist>(i, iter->vID, iter->cost));//建立邊的堆
for (i = 0; i < eNum && l < vNum; i++)//Kruskal Start
{
j = V.find(E.top().v1); k = V.find(E.top().v2);
if (j != k) { V.merge(j, k); a[l] = E.top(); l++; }
E.pop();
}
return l;
}
下面是堆和並查集的實現
#ifndef Heap_H
#define Heap_H
#include <vector>
using namespace std;
#define minchild(i) (heap[i*2+1]<heap[i*2+2]？i*2+1:i*2+2)
template <class T>
class MinHeap
{
public:
void insert(const T& x) { heap.push_back(x); FilterUp(heap.size()-1); }
const T& top() { return heap[0]; }
void pop() { heap[0] = heap.back(); heap.pop_back(); FilterDown(0); }
private:
void FilterUp(int i)
{
for (int j = (i - 1) / 2; j >= 0 && heap[j] > heap[i]; i = j, j = (i - 1) / 2)
swap(heap[i], heap[j]);
}
void FilterDown(int i)
{
for (int j = minchild(i); j < heap.size() && heap[j] < heap[i]; i = j, j = minchild(i))
swap(heap[i], heap[j]);
}
vector<T> heap;
};
#endif
#ifndef MFSets_H
#define MFSets_H
class MFSets
{
public:
MFSets(int maxsize) : size(maxsize)
{
parent = new int[size + 1];
for (int i = 0; i <= size; i++) parent[i] = -1;
}
~MFSets() { delete []parent; }
void merge(int root1, int root2)//root1!=root2
{
parent[root2] = root1;
}
int find(int n)
{
if (parent[n] < 0) return n;
return find(parent[n]);
}
private:
int size;
int* parent;
};
#endif
Prim算法
假如從頂點入手，就能得到另一種方法。從只含有一個頂點的集合開始，尋找集合外面的頂點到這個集合裡的頂點最近的一條邊，然後將這個頂點加入集合，修改因為這個頂點的加入而使得集合外面的頂點到集合裡的頂點的最短距離產生變化的分量。因為需要對每個頂點掃描，鄰接矩陣儲存的圖是最合適Prim算法的。
template <class name, class dist> int AdjMatrix<name, dist>::MinSpanTree(MSTedge<dist>* a)
{
dist* lowC = new dist[vNum]; int* nearV = new int[vNum];
int i, j, k;
for (i = 0; i < vNum; i++) { lowC[i] = edge[0][i]; nearV[i] = 0; } nearV[0] = -1;
for (k = 0; k < vNum-1; k++)//Prim Start
{
for (i = 1, j = 0; i < vNum; i++)
if (nearV[i] != -1 && lowC[i] < lowC[j]) j = i;//find low cost
a[k] = MSTedge<dist>(nearV[j], j, lowC[j]); nearV[j] = -1; //insert MST
if (a[k].cost == NoEdge) return k - 1;//no edge then return
for (i = 1; i < vNum; i++)//modify low cost
if (nearV[i] != -1 && edge[i][j] < lowC[i]) { lowC[i] = edge[i][j]; nearV[i] = j; }
}
return k;
}
【附注】這裡需要說明一下，對於edge[I][I]這樣的是應該是0呢還是NoEdge呢？顯然0合理，但是不好用。並且，從有權圖無權圖統一的角度來說，是NoEdge更好。因此，在我的有權圖的鄰接矩陣中，主對角線上的元素是NoEdge，而不是書上的0。
測試程序
儲存和操作分離，沒想到得到了一個有趣的結果——對於最後的無向圖而言，最小生成樹的算法對外表現不知道是采用了那個算法。
template <class name, class dist, class mem>
bool Graph<name, dist, mem>::MinSpanTree()
{
MSTedge<dist>* a = new MSTedge<dist>[vNum() - 1];
int n = data.MinSpanTree(a); dist sum = dist();
if (n < vNum() - 1) return false;//不夠N－1條邊，不是生成樹
for (int i = 0; i < n; i++)
{
cout << '(' << getV(a[i].v1) << ',' << getV(a[i].v2) << ')' << a[i].cost << ' ';
sum += a[i].cost;
}
cout << endl << "MinCost: " << sum << endl;
delete []a;
return true;
}
最後的測試圖的數據取自殷版（C++）——不知是這組數據好是怎麼的，殷版居然原封不動的照抄了《數據結構算法與應用-C++語言描述》（中文譯名）
#include <iostream>
using namespace std;
#include "Graph.h"
int main()
{
Graph<char, int, AdjMatrix<char, int> > a(100);//改為Link儲存為Kruskal算法
a.insertV('A'); a.insertV('B');
a.insertV('C'); a.insertV('D');
a.insertV('E'); a.insertV('F');
a.insertV('G');
a.insertE('A', 'B', 28); a.insertE('A', 'F', 10);
a.insertE('B', 'C', 16); a.insertE('C', 'D', 12);
a.insertE('D', 'E', 22); a.insertE('B', 'G', 14);
a.insertE('E', 'F', 25); a.insertE('D', 'G', 18);
a.insertE('E', 'G', 24);
a.MinSpanTree();
return 0;
}
最短路徑恐怕是圖的各種算法中最能吸引初學者眼球的了——在地圖上找一條最短的路或許每個人都曾經嘗試過。下面我們用計算機來完成我們曾經的“願望”。
在圖的算法中有個有趣的現象，就是問題的規模越大，算法就越簡單。圖是個復雜的結構，對於一個特定問題，求解特定頂點的結果都會受到其他頂點的影響——就好比一堆互相碰撞的球體，要求解特定球體的狀態，就必須考慮其他球體的狀態。既然每個頂點都要掃描，假如對所有的頂點都求解，那麼算法就非常的簡單——無非是遍歷嗎。然而，當我們降低問題規模，那很自然的，我們希望算法的規模也降低——假如不降低，不是殺雞用牛刀？但是，正是由於圖的復雜性，使得這種降低不輕易達到，因此，為了降低算法的規模，使得算法就復雜了。
在下面的介紹中，清楚了印證了上面的結論。人的認知過程是從簡單到復雜，雖然表面看上去，求每對頂點之間的最短路徑要比特定頂點到其他頂點之間的最短路徑復雜，但是，就像上面說的，本質上，前者更為簡單。下面的介紹沒有考慮歷史因素（就是指哪個算法先提出來），也沒有考慮算法提出者的真實想法（究竟是誰參考了或是沒參考誰），只是從算法本身之間的聯系來做一個闡述，如有疏漏，敬請原諒。
預備工作
一路走下來，圖類已經很“臃腫”了，為了更清楚的說明問題，需要“重起爐灶另開張”，同時也是為了使算法和儲存方法分開，以便於復用。
首先要為基本圖類添加幾個接口。
template <class name, class dist, class mem>
class Network
{
public:
int find(const name& v) { int n; if (!data.find(v, n)) return -1; return n; }
dist& getE(int m, int n) { return data.getE(m, n); }
const dist& NoEdge() { return data.NoEdge; }
};
template <class name, class dist>
class AdjMatrix
{
public:
dist& getE(int m, int n) { return edge[m][n]; }
};
template <class name, class dist>
class Link
{
public:
dist& getE(int m, int n)
{
for (list<edge>::iterator iter = vertices[m].e->begin();
iter != vertices[m].e->end() && iter->vID < n; iter++);
if (iter == vertices[m].e->end()) return NoEdge;
if (iter->vID == n) return iter->cost;
return NoEdge;
}
};
然後就是為了最短路徑算法“量身定做”的“算法類”。求某個圖的最短路徑時，將圖綁定到算法上，例如這樣：
Network<char, int, Link<char, int> > a(100);
//插入點、邊……
Weight<char, int, Link<char, int> > b(&a);
#include "Network.h"
template <class name, class dist, class mem>
class Weight
{
public:
Weight(Network<name, dist, mem>* G) : G(G), all(false), N(G->vNum())
{
length = new dist*[N]; path = new int*[N];
shortest = new bool[N]; int i, j;
for (i = 0; i < N; i++)
{
length[i] = new dist[N]; path[i] = new int[N];
}
for (i = 0; i < N; i++)
{
shortest[i] = false;
for (j = 0; j < N; j++)
{
length[i][j] = G->getE(i, j);
if (length[i][j] != G->NoEdge()) path[i][j] = i;
else path[i][j] = -1;
}
}
}
~Weight()
{
for (int i = 0; i < N; i++) { delete []length[i]; delete []path[i]; }
delete []length; delete []path; delete []shortest;
}
private:
void print(int i, int j)
{
if (path[i][j] == -1) cout << "No Path" << endl; return;
cout << "Shortest Path: "; out(i, j); cout << G->getV(j) << endl;
cout << "Path Length: " << length[i][j] << endl;
}
void out(int i, int j)
{
if (path[i][j] != i) out(i, path[i][j]);
cout << G->getV(path[i][j]) << "->";
}
dist** length; int** path; bool* shortest; bool all; int N;
Network<name, dist, mem>* G;
};
發現有了構造函數真好，算法的結果數組的初始化和算法本身分開了，這樣一來，算法的基本步驟就很輕易看清楚了。
所有頂點之間的最短路徑（Floyed算法）
從v1到v2的路徑要麼是v1->v2，要麼中間經過了若干頂點。顯然我們要求的是這些路徑中最短的一條。這樣一來，問題就很好解決了——最初都是源點到目的點，然後依次添加頂點，使得路徑逐漸縮短，頂點都添加完了，算法就結束了。
void AllShortestPath()//Folyed
{
if (all) return;
for (int k = 0; k < N; k++)
{
shortest[k] = true;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (length[i][k] + length[k][j] < length[i][j])
{
length[i][j] = length[i][k] + length[k][j];
path[i][j] = path[k][j];
}
}
all = true;
}
單源最短路徑（Dijkstra算法）
仿照上面的Floyed算法，很輕易的，我們能得出下面的算法：
void ShortestPath(int v1)
{
//Bellman-Ford
for (int k = 2; k < N; k++)
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (length[v1][j] + length[j][i] < length[v1][i])
{
length[v1][i] = length[v1][j] + length[j][i];
path[v1][i] = j;
}
}
這就是Bellman-Ford算法，可以看到，采用Floyed算法的思想，不能使算法的時間復雜度從O(n3)降到預期的O(n2)，只是空間復雜度從O(n2)降到了O(n)，但這也是應該的，因為只需要原來結果數組中的一行。因此，我並不覺得這個算法是解決“邊上權值為任意值的單源最短路徑問題”而專門提出來的，是Dijkstra算法的“推廣”版本，他只是Floyed算法的退化版本。
顯然，Floyed算法是經過N次N2條邊迭代而產生最短路徑的；假如我們想把時間復雜度從O(n3) 降到預期的O(n2)，就必須把N次迭代的N2條邊變為N條邊，也就是說每次參與迭代的只有一條邊——問題是如何找到這條邊。
先看看邊的權值非負的情況。假設從頂點0出發，到各個頂點的距離是a1,a2……，那麼，這其中的最短距離an必定是從0到n號頂點的最短距離。這是因為，假如an不是從0到n號頂點的最短距離，那麼必然是中間經過了某個頂點；但現在邊的權值非負，一個比現在這條邊還長的邊再加上另一條非負的邊，是不可能比這條邊短的。從這個原理出發，就能得出Dijkstra算法，注重，這個和Prim算法極其相似，不知道誰參考了誰；但這也是難免的事情，因為他們的原理是一樣的。
void ShortestPath(const name& vex1, const name& vex2)//Dijkstra
{
int v1 = G->find(vex1); int v2 = G->find(vex2);
if (shortest[v1]) { print(v1, v2); return; }
bool* S = new bool[N]; int i, j, k;
for (i = 0; i < N; i++) S[i] = false; S[v1] = true;
for (i = 0; i < N - 1; i++)//Dijkstra Start, like Prim？
{
for (j = 0, k = v1; j < N; j++)
if (!S[j] && length[v1][j] < length[v1][k]) k = j;
S[k] = true;
for (j = 0; j < N; j++)
if (!S[j] && length[v1][k] + length[k][j] < length[v1][j])
{
length[v1][j] = length[v1][k] + length[k][j];
path[v1][j] = k;
}
}
shortest[v1] = true; print(v1, v2);
}
假如邊的權值有負值，那麼上面的原則不再適用，連帶的，Dijkstra算法也就不再適用了。這時候，沒辦法，只有接受O(n3) Bellman-Ford算法了，雖然他可以降低為O(n*e)。不過，何必讓邊的權值為負值呢？還是那句話，合理的並不好用。
特定兩個頂點之間的最短路徑（A*算法）
其實這才是我們最關心的問題，我們只是想知道從甲地到乙地怎麼走最近，並不想知道別的——甲地到丙地怎麼走關我什麼事？自然的，我們希望這個算法的時間復雜度為O(n)，但是，正像從Floyed算法到Dijkstra算法的變化一樣，並不是很輕易達到這個目標的。
讓我們先來看看Dijkstra算法求特定兩個頂點之間的最短路徑的時間復雜度究竟是多少。顯然，在上面的void ShortestPath(const name& vex1, const name& vex2)中，當S[v2]==true時，算法就可以中止了。假設兩個頂點之間直接的路徑是他們之間的路徑最短的（不需要經過其他中間頂點），並且這個路徑長度是源點到所有目的點的最短路徑中最短的，那麼第一次迭代的時候，就可以得到結果了。也就是說是O(n)。然而當兩個頂點的最短路徑需要經過其他頂點，或者路徑長度不是源點到未求出最短路徑的目的點的最短路徑中最短的，那就要再進行若干次迭代，對應的，時間復雜度就變為O(2n)、O(3n)……到了最後才求出來（迭代了N－1次）的就是O(n2)。
很明顯的，迭代次數是有下限的，最短路徑上要經過多少個頂點，至少就要迭代多少次，我們只能使得最終的迭代次數接近最少需要的次數。假如再要減低算法的時間復雜度，我們只能想辦法把搜索范圍的O(n)變為O(1)，這樣，即使迭代了N－1次才得到結果，那時間復雜度仍為O(n)。但這個想法實現起來卻是困難重重。
仍然看Dijkstra算法，第一步要尋找S中的頂點到S外面頂點中最短的一條路徑，這個min運算使用基於比較的方法的時間復雜度下限是O(longN)（使用敗者樹），然後需要掃描結果數組的每個分量進行修改，這裡的時間復雜度就只能是O(n)了。原始的Dijkstra算法達不到預期的目的。
現在讓我們給圖添加一個附加條件——兩點之間直線最短，就是說假如v1和v2之間有直通的路徑（不經過其他頂點），那麼這條路徑就是他們之間的最短路徑。這樣一來，假如求的是v1能夠直接到達的頂點的最短路徑，時間復雜度就是O(1)了，顯然比原來最好的O(n)（這裡實際上是O(logN)）提高了效率。
這個變化的產生，是因為我們添加了“兩點之間直線最短”這樣的附加條件，實際上就是引入一個判定准則，把原來盲目的O(n)搜索降到了O(1)。這個思想就是A*算法的思想。關於A*算法更深入的介紹，恕本人資料有限，不能滿足大家了。有愛好的可以到網上查查，這方面的中文資料實在太少了，大家做好看E文的預備吧。
不同於現有的教科書，我把求最短路徑的算法的介紹順序改成了上面的樣子。我認為這個順序才真正反映了問題的本質——當減低問題規模時，為了降低算法的時間復雜度，應該想辦法縮小搜索范圍。而縮小搜索范圍，都用到了一個思想——盡可能的向接近最後結果的方向搜索，這就是貪婪算法的應用。
假如反向看一遍算法的演化，我們還能得出新的結論。Dijkstra算法實際上不用做n2次搜索、比較和修改，當求出最短路徑的頂點後，搜索范圍已經被縮小了，只是限於儲存結構，這種范圍的縮小並沒有體現出來。假如我們使得這種范圍縮小直接體現出來，那麼，用n次Dijkstra算法代替Floyed算法就能帶來效率上的提升。A*算法也是如此，假如用求n點的A*算法來代替Dijkstra算法，也能帶來效率的提升。
但是，每一步的進化實際上都伴隨著附加條件的引入。從Floyed到Dijkstra是邊上的權值非負，假如這個條件不成立，那麼就只能退化成Bellman-Ford算法。從Dijkstra到A*是另外的判定准則的引入（本文中是兩點之間直線最短），假如這個條件不成立，同樣的，只能采用不完整的Dijkstra（求到目的頂點結束算法）。
這部分是和工程相關的，也就是說，當AOV、AOE很復雜的時候，才能顯示出這部分的價值——簡單的話，手工都要比程序快，輸入數據那段時間手工結果就出來了。我也沒什麼例子好舉，總給我一種沒底氣的感覺，勉為其難的把程序寫完就算完事吧。和前邊的相比，這部分專業了一點，換而言之，不是每個人都感愛好，不想看就跳過去吧。
預備工作
活動網絡主要有兩個算法，拓撲排序和求要害路徑，後者以前者為基礎。仿照上篇，另外構造一個“算法類”，需要算法時，將圖綁定到算法上。
#include "Network.h"
#define iterator list<Link<name, dist>::edge>::iterator
#define begin(i) G->data.vertices[i].e->begin()
#define end(i) G->data.vertices[i].e->end()
struct CriAct
{
CriAct() {}
CriAct(int source, int dest) : s(source), d(dest) {}
int s, d;
};
template <class name, class dist>
class ActivityNetwork
{
public:
ActivityNetwork(Network<name, dist, Link<name, dist> >* G) : G(G), N(G->vNum()), outCriAct(CA)
{
count = new int[N]; result = new int[N];
}
~ActivityNetwork()
{
delete []count; delete []result;
}
const vector<CriAct>& outCriAct;
const int* out;
private:
void initialize()
{
for (int j = 0; j < N; j++) count[j] = 0;
for (int i = 0; i < N; i++)
{
for (iterator iter = begin(i); iter != end(i); iter++) count[iter->vID]++;
}
out = result;
}
Network<name, dist, Link<name, dist> >* G;
vector<CriAct> CA;
int N, *count, *result;
};
因為AOV和AOE的邊都不會太多（想象一下邊多的情況，那事件就都是雞毛蒜皮了），所以儲存結構直接選擇了鄰接表。並且為了體現鄰接表的優勢，需要直接操作私有數據，因此要把這個類聲明為Link類和Network類的友元，另外由於這個類在後面，所以需要前視聲明。具體如下：
template <class name, class dist> class ActivityNetwork;
template <class name, class dist> class Link
{friend class ActivityNetwork<name, dist>;};
template <class name, class dist, class mem> class Network
{ friend class ActivityNetwork<name, dist>;};
拓撲排序
這個算法很精巧，避免了對已經排好序的頂點的再次掃描，另外，殷版上用計數數組來充當棧的方法也很巧妙。算法的說明參閱相關的教科書，不再贅述。
bool TopoSort()
{
initialize(); int i, top = -1;
for (i = 0; i < N; i++) if (!count[i]) { count[i] = top; top = i; }
for (i = 0; i < N; i++) //TopoSort Start
{
if (top == -1) return false;
result[i] = top; top = count[top];
for (iterator iter = begin(result[i]); iter != end(result[i]); iter++)
if (!--count[iter->vID]) { count[iter->vID] = top; top = iter->vID; }
}
return true;
}
由於public數據成員out和private數據成員result指向同一個數組，在類的外面可以通過out來得到排序結果，只是不能改變（當然，非要改變const數據也不是沒有辦法）。下面是測試程序，數據來自殷版：
#include <iostream>
using namespace std;
#include "ActivityNetwork.h"
int main()
{
Network<int, int, Link<int, int> > a;
a.insertV(0);a.insertV(1);a.insertV(2);a.insertV(3);a.insertV(4);a.insertV(5);
a.insertE(0,3,1);a.insertE(0,1,1);a.insertE(1,5,1);a.insertE(2,1,1);
a.insertE(2,5,1);a.insertE(4,0,1);a.insertE(4,1,1);a.insertE(4,5,1);
ActivityNetwork<int, int> b(&a);
if (b.TopoSort()) for (int i = 0; i < a.vNum(); i++) cout << b.out[i] << ' ';
return 0;
}
要害路徑
有了拓撲排序的結果，這個程序就比較好寫了，那些所謂的“技巧”就不用了，如下的程序，很直白，算法說明請參考教科書。
bool CriPath()
{
if (!TopoSort()) return false; int i; iterator iter; CA.clear();
dist* Ve = new dist[N]; dist* Vl = new dist[N];//Ve最早開始時間，Vl最遲開始時間
for (i = 0; i < N; i++) Ve[i] = 0;//Ve初始化
for (i = 0; i < N; i++)//按拓撲順序計算Ve
for (iter = begin(result[i]); iter != end(result[i]); iter++)
if (Ve[result[i]]+iter->cost>Ve[iter->vID]) Ve[iter->vID]= Ve[result[i]] + iter->cost;
for (i = 0; i < N; i++) Vl[i] = Ve[N - 1];//Vl初始化
for (i = N - 2; i >= 0; i--)//按逆拓撲順序計算Vl
for (iter = begin(result[i]); iter != end(result[i]); iter++)
if (Vl[iter->vID]-iter->cost < Vl[result[i]]) Vl[result[i]] = Vl[iter->vID] - iter->cost;
for (i = 0; i < N; i++)//計算各個活動的最早開始時間和最遲開始時間
for (iter = begin(i); iter != end(i); iter++)
if (Ve[i] == Vl[iter->vID] - iter->cost) CA.push_back(CriAct(i, iter->vID));
return true;
}
同樣的在類的外面可以通過outCriAct得到結果，是一個const引用。如下的測試程序，數據來自殷版：
#include <iostream>
using namespace std;
#include "ActivityNetwork.h"
int main()
{
Network<int, int, Link<int, int> > a;
a.insertV(0);a.insertV(1);a.insertV(2);a.insertV(3);a.insertV(4);
a.insertV(5); a.insertV(6);a.insertV(7);a.insertV(8);
a.insertE(0,1,6);a.insertE(0,2,4);a.insertE(0,3,5);
a.insertE(1,4,1);a.insertE(2,4,1);a.insertE(3,5,2);
a.insertE(4,6,9);a.insertE(4,7,7);a.insertE(5,7,4);
a.insertE(6,8,2);a.insertE(7,8,4);
ActivityNetwork<int, int> b(&a);
if (b.CriPath())
for (int j = 0; j < b.outCriAct.size(); j++)
cout <<'<'<<a.getV(b.outCriAct[j].s) << ',' << a.getV(b.outCriAct[j].d) << '>' << ' ';
return 0;
}
總結
不同於前面的鏈表和樹，在圖這裡，儲存方法不是重點，我們更多的注重力放在了算法上。我在寫程序的時候，也盡量做到了算法和儲存方法無關。然而算法實際上就是現實問題的抽象，假如我們的常識所不及，我們也就沒有辦法來介紹算法，反過來說，幾乎遇不到的問題，我們也不會對它的算法感愛好。
因此，在圖的算法裡面，由鋪設管道引出了最小生成樹，由提高通信、交通網絡可靠性引出了關節點和重連通分量，由地圖尋徑引出了最短路徑，由工程預算引出了要害路徑。這些恐怕是我們能夠理解的全部了，假如再來一個電氣網絡計算，沒點物理知識恐怕是要完。
但即使這樣，上面的各個算法仍然離我們很遠，我們大多數人恐怕永遠都不會知道管道是怎麼鋪的。我想，這裡面除了最短路徑能引起大多數人的愛好之外，其他的就只能走馬觀花的看看罷了。這也使得圖的學習很像“聾子的耳朵”，真正接觸到圖的用途的人不多，並且即使用到圖，也僅僅是個別的算法。
正像數據結構教學的通病一樣，學無所用經常導致學無所成，前面的鏈表、樹好歹還能做點什麼東西出來，到了圖這裡，除了做個導游系統，我們也做不出別的什麼了。寫到這裡很無奈，但我也只能是無奈……
那麼，學完了圖，我們應該把握什麼呢，是上面零散的算法嗎？我的看法是，不是。我覺得我們更應該知道那些算法是怎麼“創造”出來的，假如碰到了類似的問題，能不能“派生”出新的算法。因此，我覺得《數據結構算法與應用-C++語言描述》這本書，將圖的最小生成樹、最短路徑、拓撲排序算法放到了貪婪算法裡講解，是一種更為合理的安排。
最後對在學習圖時像我一樣茫然的人深表同情。
