graphmtx.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

//邻接矩阵存储的图的类定义
#ifndef Graphmtx_H
#define Graphmtx_H

//#include<iostream>
//using namespace std;
const int maxWeight = 32767;
template <class T, class E>
class Graphmtx {				//图的邻接矩阵类定义
public:
	Graphmtx(int sz);			//构造函数
	~Graphmtx()									//析构函数
	{delete []VertexList;  delete []Edge;}
	void build();                       //建立图
	T getValue(int i)								//取顶点i的值, i不合理返回0
	{return i >= 0 && i < numVertex ? VertexList[i] : NULL;}
	E getWeight(int v1, int v2) 					//取边(v1,v2)上的权值
	{return v1 != -1 && v2 != -1 ? Edge[v1][v2] : 0;}
	int getFirstNeighbor(int v);					//取顶点v的第一个邻接顶点
	int getNextNeighbor(int v, int w);				//取v的邻接顶点w的下一邻接顶点
	bool insertVertex(const T vertex);				//插入顶点vertex
	bool insertEdge(int v1, int v2, E cost);		//插入边(v1, v2),权值为cost
	bool removeVertex(int v);						//删去顶点v和所有与它相关联的边
	bool removeEdge(int v1, int v2);				//在图中删去边(v1,v2)
	int getVertexPos(T vertex) {					//给出顶点vertex在图中的位置
		for (int i = 0; i < numVertex; i++)
			if (VertexList[i] == vertex) return i;
		return -1;
	}
	int NumberOfVertex() { return numVertex; }
	void DFS(const T& v);   //深度优先遍历图
	void DFS(int v, bool visited[]);//深度优先遍历图，子过程
private:
	T *VertexList; 								//顶点表
	E **Edge;										//邻接矩阵
	int numVertex,numEdges,maxVertexNum;
};

template <class T, class E>
Graphmtx<T,E>::Graphmtx(int sz) {
	//构造函数
	maxVertexNum = sz;  numVertex = 0;  numEdges = 0;
	int i, j;
	VertexList = new T[maxVertexNum];			//创建顶点表数组
	Edge = (int **) new int *[maxVertexNum];	//创建邻接矩阵数组
	for (i = 0; i < maxVertexNum; i++)
		Edge[i] = new int[maxVertexNum];
	for (i = 0; i < maxVertexNum; i++)			//邻接矩阵初始化
		for (j = 0; j < maxVertexNum; j++)
			Edge[i][j] = maxWeight; 
	cout<<"初始化成功"<<endl;
};
template <class T, class E>
int Graphmtx<T,E>::getFirstNeighbor(int v) {
	//给出顶点位置为v的第一个邻接顶点的位置, 如果找不到, 则函数返回-1。
	if (v != -1) {
		for (int col = 0; col < numVertex; col++)
			if (Edge[v][col] > 0 && Edge[v][col] < maxWeight) return col;
	}
	return -1;
};

template <class T, class E>
int Graphmtx<T,E>::getNextNeighbor(int v, int w) {
	//给出顶点v的某邻接顶点w的下一个邻接顶点 
	if (v != -1 && w != -1) {
		for (int col = w+1; col < numVertex; col++) 
			if (Edge[v][col] > 0 && Edge[v][col] < maxWeight) return col; 
	}
	return -1;
};

template <class T, class E>
bool Graphmtx<T,E>::insertVertex(const T vertex) {		//插入顶点vertex
	if (numVertex == maxVertexNum) return false;		//顶点表满, 不插入
	VertexList[numVertex++] = vertex;
	return true;
};
template <class T, class E>
bool Graphmtx<T,E>::insertEdge(int v1, int v2, E cost) {
	//插入边(v1, v2), 权值为cost
	if (v1 > -1 && v1 < numVertex && v2 > -1 && v2 < numVertex &&
		Edge[v1][v2] == maxWeight) {				//插入条件
			Edge[v1][v2] = Edge[v2][v1] = cost;
			numEdges++;
			return true;
	}
	else return false;
};
template <class T, class E>
void Graphmtx<T,E>::build(){
	//通过从输入流对象cin输入n个顶点信息和e条无向边的信息建立用邻接矩阵表示的
	//图grph. 邻接矩阵初始化的工作已经在构造函数中完成。
	int i, j, k, n, m;  T e1, e2; E weight;
	cout<<"请输入顶点数：";
	cin >> n;
	cout<<"请输入边数：";
	cin >> m; 											//输入顶点数n和边数m
	for (i = 0; i < n; i++)	{	                    //建立顶点表数据
		cout<<"输入顶点"<<i<<": ";	
		cin >> e1;  insertVertex(e1);
	} 
	i = 0;
	while (i < m) {
		cout<<"输入各边的两顶点及权值：";
		cin >> e1 >> e2 >>weight;  							//输入端点信息
		j = getVertexPos(e1);  k = getVertexPos(e2);	//查顶点号
		if (j == -1 || k == -1)
			cout << "边两端点信息有误,重新输入！" << endl;
		else {
			insertEdge(j, k, weight);  i++;
		}
	}
};

template <class T, class E>
bool Graphmtx<T,E>::removeVertex(int v) {
	//删去顶点v和所有与它相关联的边
	if (v < 0 && v >= numVertex) return false;		//v不在图中,不删除
	if (numVertex == 1) return false;				//只剩一个顶点,不删除
	int i, j;
	VertexList[v] = VertexList[numVertex-1];		//顶点表中删除该结点
	for (i = 0; i < numVertex; i++)					//减去与v相关联边数
		if (Edge[i][v] > 0 && Edge[i][v] < maxWeight) numEdges--;
	for (i = 0; i < numVertex; i++)					//用最后一列填补第v列
		Edge[i][v] = Edge[i][numVertex-1];
	numVertex--;										//顶点数减一
	for (j = 0; j < numVertex; j++)					//用最后一行填补第v行
		Edge[v][j] = Edge[numVertex][j];
	return true;
};

template <class T, class E>
bool Graphmtx<T,E>::removeEdge(int v1, int v2) {
	//在图中删去边(v1,v2)
	if (v1 > -1 && v1 < numVertex && v2 > -1 && v2 < numVertex &&
		Edge[v1][v2] > 0 && Edge[v1][v2] < maxWeight) {
			Edge[v1][v2] = Edge[v2][v1] = maxWeight;
			numEdges--;
			return true;
	}
	else return false;
};

template<class T, class E> 
void Graphmtx<T,E>::DFS(const T& v) {
	//从顶点v出发，对图G进行深度优先遍历的主过程	
	int i, loc, n = NumberOfVertex(); 			//取图中顶点个数
	bool *visited = new bool[n]; 					//创建辅助数组
	for (i = 0; i < n; i++) visited [i] = false;	//辅助数组visited初始化
	loc = getVertexPos(v);
	DFS(loc, visited); 							//从顶点0开始深度优先搜索
	delete [] visited;								//释放visited
};

template<class T, class E>
void Graphmtx<T,E>::DFS(int v, bool visited[]) {	//子过程
	//从顶点位置v出发, 以深度优先的次序访问所有可读入的尚未访问过的顶点。算法中用到一个
	//辅助数组visited, 对已访问过的顶点作访问标记。
	cout << getValue(v) << ' ';					//访问顶点v
	visited[v] = true;	 							//顶点v作访问标记
	int w = getFirstNeighbor(v); 					//找顶点v的第一个邻接顶点w
	while (w != -1) {								//若邻接顶点w存在
		if (visited[w] == false) DFS(w, visited);
		//若w未访问过, 递归访问顶点w
		w = getNextNeighbor(v, w);				//取v排在w后的下一个邻接顶点
	}
};

#endif;