六讲贯通C++图的应用之一 基本储存方法

　　图的应用恐怕是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。

【编辑推荐】

1. 经典四讲贯通C++排序之一 插入排序
2. c++编程常用工具
3. 给C++初学者的50个忠告
4. c++最基础的20条规则
5. 程序员必看 c++笔试题汇总