C++实现图的邻接矩阵表示

#ifndef GraphMatrix_h
#define GraphMatrix_h
#include 
using namespace std;
 
const int DefaultVertices = 30; // 默认最大顶点数
 
template 
class GraphMatrix {
public:
 const E maxWeight = 100000; // 代表无穷大的值（=∞）
 GraphMatrix(int sz=DefaultVertices); // 构造函数
 ~GraphMatrix(); // 析构函数
 void inputGraph(); // 创建基于邻接矩阵的图
 void outputGraph(); // 输出图的所有顶点和边信息
 T getValue(int i); // 取顶点i的值，i不合理返回0
 E getWeight(int v1, int v2); // 取边(v1, v2)上的权值
 int getFirstNeighbor(int v); // 取顶点v的第一个邻接顶点
 int getNextNeighbor(int v, int w); // 取v的邻接顶点w的下一个邻接顶点
 bool insertVertex(const T& vertex); // 插入顶点vertice
 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); // 给出顶点vertice在图中的位置
private:
 int maxVertices; // 图中最大的顶点数
 int numEdges; // 当前边数
 int numVertices; // 当前顶点数
 T *VerticesList; // 顶点表
 E **Edge; // 邻接矩阵
};
 
// 构造函数
template 
GraphMatrix::GraphMatrix(int sz) {
 int i, j;
 
 maxVertices = sz;
 numVertices = 0;
 numEdges = 0;
 VerticesList = new T[maxVertices]; // 创建顶点表数组
 Edge = new E*[maxVertices]; // 创建邻接矩阵数组
 for(i = 0; i 
GraphMatrix::~GraphMatrix() {
 delete []VerticesList; // 释放动态分配的空间
 delete []Edge;
}
 
// 创建基于邻接矩阵的图
template 
void GraphMatrix::inputGraph() {
 int i, j, k;
 int n, m; // 要输入的顶点数和边数
 T e1, e2; // 边的两端顶点
 E weight; // 边对应的权值
 
 cout <<"请输入顶点数和边数:" <> n >> m;
 cout <<"请输入顶点：" <> e1;
  insertVertex(e1); // 插入
 }
 cout <<"请输入边的两端顶点和权值:" <> e1 >> e2 >> weight; // 输入端点信息
  j = getVertexPos(e1); // 查顶点号
  k = getVertexPos(e2);
  if(j == -1 || k == -1)
   cout <<"边两端点信息有误，重新输入!" <
void GraphMatrix::outputGraph() {
 int i, j, n, m;
 T e1, e2;
 E w;
 
 n = numVertices;
 m = numEdges;
 cout <<"顶点数为：" < 0 && w 
int GraphMatrix::getVertexPos(T vertex) {
 for(int i = 0; i 
T GraphMatrix::getValue(int i) {
 if(i >= 0 && i 
E GraphMatrix::getWeight(int v1, int v2) {
 if(v1 != -1 && v2 != -1) // 存在这两个顶点
  return Edge[v1][v2];
 return 0;
}
 
// 取顶点v的第一个邻接顶点
template 
int GraphMatrix::getFirstNeighbor(int v) {
 if(v != -1) {
  for(int col = 0; col  0 && Edge[v][col] 
int GraphMatrix::getNextNeighbor(int v, int w) {
 if(v != -1 && w != -1) {
  for(int col = w+1; col  0 && Edge[v][col] 
bool GraphMatrix::insertVertex(const T& vertex) {
 if(numVertices == maxVertices) // 顶点表满
  return false;
 VerticesList[numVertices++] = vertex;
 return true;
}
 
// 插入边(v1, v2)权值为cost
template 
bool GraphMatrix::GraphMatrix::insertEdge(int v1, int v2, E cost) {
 if(v1 > -1 && v1  -1 && v2 
bool GraphMatrix::removeVertex(int v) {
 if(v <0 && v > numVertices) // v不在图中，不删除
  return false;
 if(numVertices == 1) // 只剩一个顶点，不删除
  return false;
 int i, j;
 
 VerticesList[v] = VerticesList[numVertices-1]; // 用最后一个顶点替代当前要删的顶点
 // 删除与v相关联边数
 for(i = 0; i  0 && Edge[i][v] 
bool GraphMatrix::removeEdge(int v1, int v2) {
 if(v1 > -1 && v1  -1 && v2 

// 测试数据：
/*
5 7
A B C D E
A B 24 A C 46 B C 15 B E 67 C B 37 C D 53 E D 31
 */
 
#include "GraphMatrix.h"
 
int main(int argc, const char * argv[]) {
 GraphMatrix st; // 声明对象
 bool finished = false;
 int choice;
 char e1, e2, next;
 int weight;
 
 while(!finished) {
  cout <<"[1]创建基于邻接矩阵的图" <> choice;
  switch(choice) {
   case 1:
    st.inputGraph();
    break;
   case 2:
    st.outputGraph();
    break;
   case 3:
    cout <<"请输入顶点:";
    cin >> e1;
    e2 = st.getValue(st.getFirstNeighbor(st.getVertexPos(e1)));
    if(e2)
     cout <<"顶点" <> e1 >> e2;
    next = st.getValue(st.getNextNeighbor(st.getVertexPos(e1), st.getVertexPos(e2)));
    if(next)
     cout <<"顶点" <> e1;
    if(st.insertVertex(e1))
     cout <<"插入成功！" <> e1 >> e2 >> weight;
    st.insertEdge(st.getVertexPos(e1), st.getVertexPos(e2), weight);
    break;
   case 7:
    cout <<"请输入要删除的顶点：";
    cin >> e1;
    if(st.removeVertex(st.getVertexPos(e1)))
     cout <<"顶点" <> e1 >> e2;
    st.removeEdge(st.getVertexPos(e1), st.getVertexPos(e2));
    break;
   case 9:
    finished = true;
    break;
   default:
    cout <<"选择输入错误，请重新输入!" <