C++模板化设计图的邻接矩阵表示法

听完James老师的课，就想着把图的邻接矩阵表示法写成一个模板。
邻接矩阵适合表示稠密图，对于稀疏图，应该用链表实现才合算。
同时邻接矩阵的遍历的时间复杂度是O(n^2)，而邻接表则是O(n + e)。
n表示顶点数量，e表示边数量。

对James老师的实现方式我做了一些修改。

1. 由于要设置成模板，所以将表示顶点的类内置（in-class）。
2. 对部分虽然通俗易懂但是略显冗余的代码做了精简。
3. 广度优先我认为用队列实现更佳，重写了实现代码。
   要注意的是：
4. 由于许多编译器不支持类模板的头文件与实现文件分离编译，所以把它们都放在头文件中。
5. 在大数据遍历的过程中，局部变量造成的额外内存开销还是很客观的，因此，应当将参数列表都改成 const 的引用。为了便于阅读，这边我没有这样处理。
   下面是MyMap.h的实现代码：

#ifndef MYMAP_H
#define MYMAP_H

#include 
#include 
#include 
using namespace std;

template 
class MyMap {
    public:
 MyMap(int capacity);
 ~MyMap();
 //添加的顶点对应的索引依次为0 ... capacity-1. 
 bool addVertex(T data);
 void resetVertex();
 //分别给有向图和无向图添加边。 
 bool setValue2Matrix4DirectedGraph(int row, int col, int val = 1);
 bool setValue2Matrix4UndirectedGraph(int row, int col, int val = 1);
 void DFS(int vertexIndex) const;    //depth first search. 
 void BFS(int vertexIndex) const;    //breadth first search.
    private:
 bool isAvailable(int row, int col) const;   //row, col合法性判断
 int getValueFromMatrix(int row, int col) const;

    private:
 struct Vertex { //默认访问权限 -> public 
     T data;
     bool isVisited;
 };
 int capacity;   //最多可容纳顶点数
 int cntV;//已添加顶点数
 Vertex *arrV;   //顶点数组
 int *pMatrix;   //邻接矩阵 
};

template 
MyMap::MyMap(int capacity) {
    this->capacity = capacity;
    cntV = 0;
    arrV = new Vertex[capacity];
    pMatrix = new int[capacity * capacity];
    memset(pMatrix, 0, capacity * capacity * sizeof(int));
}

template 
MyMap::~MyMap() {
    delete[] arrV;
    delete[] pMatrix;
}

template 
bool MyMap::addVertex(T data) {
    if(cntV == capacity) return false;
    arrV[cntV].data = data;
    arrV[cntV++].isVisited = false;
    return true;
}

template 
void MyMap::resetVertex() {
    for(int i = 0; i < cntV; ++i) 
 arrV[i].isVisited = false;
}

template  
bool MyMap::setValue2Matrix4DirectedGraph(int row, int col, int val) {
    if(!isAvailable(row, col)) return false;
    pMatrix[row * capacity + col] = val;
    return true;
}

template 
bool MyMap::setValue2Matrix4UndirectedGraph(int row, int col, int val) {
    if(!isAvailable(row, col)) return false;
    pMatrix[row * capacity + col] = pMatrix[col * capacity + row] = val;
    return true;
}

template 
void MyMap::DFS(int vertexIndex) const {
    cout << arrV[vertexIndex].data << " ";
    arrV[vertexIndex].isVisited = true;
    for(int i = 0; i < cntV; ++i) {
 if(getValueFromMatrix(vertexIndex, i) > 0 && !arrV[i].isVisited)
     DFS(i);
    }
}

template 
void MyMap::BFS(int vertexIndex) const {
    queue que;
    que.push(vertexIndex);
    while(!que.empty()) {
 int index = que.front();
 que.pop();
 if(!arrV[index].isVisited) {
     cout << arrV[index].data << " ";
     arrV[index].isVisited = true;
 }

 for(int i = 0; i < cntV; ++i) {
     if(getValueFromMatrix(index, i) > 0 && !arrV[i].isVisited)
  que.push(i);
 } 
    }
}

template 
bool MyMap::isAvailable(int row, int col) const {
    return 0 <= row && row < capacity && 0 <= col && col < capacity;
}

template 
int MyMap::getValueFromMatrix(int row, int col) const {
    if(!isAvailable(row, col)) return -1;
    return pMatrix[row * capacity + col];
}

#endif

这是测试文件代码：

int main(void) {
    MyMap myMap(8);
    for(char ch = 'a'; ch <= 'h'; ++ch)
 myMap.addVertex(ch);

    myMap.setValue2Matrix4UndirectedGraph(0, 1);
    myMap.setValue2Matrix4UndirectedGraph(0, 3);
    myMap.setValue2Matrix4UndirectedGraph(1, 2);
    myMap.setValue2Matrix4UndirectedGraph(1, 5);
    myMap.setValue2Matrix4UndirectedGraph(3, 6);
    myMap.setValue2Matrix4UndirectedGraph(3, 7);
    myMap.setValue2Matrix4UndirectedGraph(6, 7);
    myMap.setValue2Matrix4UndirectedGraph(2, 4);
    myMap.setValue2Matrix4UndirectedGraph(4, 5);

    myMap.resetVertex();
    cout << endl << "深度优先：";
    myMap.DFS(0);   //A B C E F D G H
    myMap.resetVertex();
    cout << endl << "广度优先：";
    myMap.BFS(0);   //A B D C F G H E
    cout << endl;

    return 0;
}