圖的應用恐怕是C++所有數據結構中最寬泛的了,但這也注定了在講“數據結構的圖”的時候沒什麼好講的——關於圖的最重要的是算法,而且相當的一部分都是很專業的,一般的人幾乎不會接觸到;相對而言,結構就顯得分量很輕。你可以看到關於圖中元素的操作很少,遠沒有單鏈表那裡列出的一大堆“接口”。——一個結構如果復雜,那麼能確切定義的操作就很有限。
筆者從基本儲存方法、DFS和BFS、無向圖、最小生成樹、最短路徑以及活動網絡(AOV、AOE)六個方面詳細介紹圖的應用。本文是這次系列文章的第一篇,主要介紹圖的基本存儲方法。
基本儲存方法
不管怎麼說,還是先得把圖存起來。不要看書上列出了好多方法,根本只有一個——鄰接矩陣。如果矩陣是稀疏的,那就可以用十字鏈表來儲存矩陣(見C++數據結構學習之稀疏矩陣)。如果我們只關系行的關系,那麼就是鄰接表(出邊表);反之,只關心列的關系,就是逆鄰接表(入邊表)。
下面給出兩種儲存方法的實現。
- #ifndef Graphmem_H
- #define Graphmem_H
- #include
- #include
- 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
>; - 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
>; - 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
這個實現是很簡陋的,但應該能滿足後面的講解了。現在這個還什麼都不能做,不要急,在下篇將講述圖的DFS和BFS。