首先告訴大家一個(gè)好消息，數(shù)據(jù)結(jié)構(gòu)到這里就要結(jié)束了！然后再來一個(gè)壞消息，這里是數(shù)據(jù)結(jié)構(gòu)中“最沒有意義”的部分和最難的部分。圖的應(yīng)用恐怕是所有結(jié)構(gòu)中最寬泛的了，但這也注定了在講“數(shù)據(jù)結(jié)構(gòu)的圖”的時(shí)候沒什么好講的——關(guān)于圖的最重要的是算法，而且相當(dāng)?shù)囊徊糠侄际呛軐I(yè)的，一般的人幾乎不會(huì)接觸到；相對(duì)而言，結(jié)構(gòu)就顯得分量很輕。你可以看到關(guān)于圖中元素的操作很少，遠(yuǎn)沒有單鏈表那里列出的一大堆“接口”。——一個(gè)結(jié)構(gòu)如果復(fù)雜，那么能確切定義的操作就很有限。
不管怎么說，還是先得把圖存起來。不要看書上列出了好多方法，根本只有一個(gè)——鄰接矩陣。如果矩陣是稀疏的，那就可以用十字鏈表來儲(chǔ)存矩陣（見前面的《稀疏矩陣（十字鏈表）》）。如果我們只關(guān)系行的關(guān)系，那么就是鄰接表（出邊表）；反之，只關(guān)心列的關(guān)系，就是逆鄰接表（入邊表）。
下面給出兩種儲(chǔ)存方法的實(shí)現(xiàn)。
#ifndef Graphmem_H
#define Graphmem_H
<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
#include <vector>
#include <list>
using namespace std;
template <class name, class dist, class mem> class Network;
const int maxV = 20;//最大節(jié)點(diǎn)數(shù)
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號(hào)頂點(diǎn)的第n號(hào)頂點(diǎn)后第一個(gè)鄰接頂點(diǎn)號(hào)，無返回-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 vertex[i].second;
}
bool insertV(name v)
{
if (find(v)) return false;
vertex.push_back(pair<name, list<edge>* >(v, new list<edge>));
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;
for (list<edge>::iterator iter = vertex[i].second->begin();
iter != vertex[i].second->end(); iter++) if (iter->vID == j) return false;
vertex[i].second->push_back(edge(j, cost)); eNum++; return true;
}
name& getV(int n) { return vertex[n].first; } //沒有越界檢查
int nextV(int m, int n)//返回m號(hào)頂點(diǎn)的第n號(hào)頂點(diǎn)后第一個(gè)鄰接頂點(diǎn)號(hào)，無返回-1
{
for (list<edge>::iterator iter = vertex[m].second->begin();
iter != vertex[m].second->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 == vertex[i].first) return true;
return false;
}
bool find(const name& v, int& i)
{
for (i = 0; i < vNum; i++) if (v == vertex[i].first) return true;
return false;
}
struct edge
{
edge() {}
edge(int vID, dist cost) : vID(vID), cost(cost) {}
int vID;
dist cost;
};
int vNum, eNum;
vector<pair<name, list<edge>* > > vertex;
};
#endif
這個(gè)實(shí)現(xiàn)是很簡(jiǎn)陋的，但應(yīng)該能滿足后面的講解了。現(xiàn)在這個(gè)還什么都不能做，不要急，在下篇將講述圖的DFS和BFS。