首先告訴大家一個好消息，數據結構到這里就要結束了！然后再來一個壞消息，這里是數據結構中“沒有意義”的部分和難的部分。圖的應用恐怕是所有結構中寬泛的了，但這也注定了在講“數據結構的圖”的時候沒什么好講的——關于圖的重要的是算法，而且相當的一部分都是很專業的，一般的人幾乎不會接觸到；相對而言，結構就顯得分量很輕。你可以看到關于圖中元素的操作很少，遠沒有單鏈表那里列出的一大堆“接口”。——一個結構如果復雜，那么能確切定義的操作就很有限。

　　不管怎么說，還是先得把圖存起來。不要看書上列出了好多方法，根本只有一個——鄰接矩陣。如果矩陣是稀疏的，那就可以用十字鏈表來儲存矩陣（見前面的《稀疏矩陣（十字鏈表）》）。如果我們只關系行的關系，那么就是鄰接表（出邊表）；反之，只關心列的關系，就是逆鄰接表（入邊表）。

　　下面給出兩種儲存方法的實現。

#ifndef Graphmem_H

#define Graphmem_H

#include

#include

using namespace std;

template class Network;

const int maxV = 20;//節點數

template

class AdjMatrix
{
friend class Network >;
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 LinkedList
{
friend class Network >;

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));
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::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::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* e) : v(v), e(e) {}
name v;
list* e;
};
int vNum, eNum;
vector vertices;
};

#endif

　　這個實現是很簡陋的，但應該能滿足后面的講解了?，F在這個還什么都不能做，不要急，在下篇將講述圖的DFS和BFS。