图的构造和实现——邻接矩阵[无向图]（c++）

//环境：vs2010

//MGraph.h#ifndef MGraph_H                    //定义头文件
#define MGraph_Hconst int MaxSize = 10;           //图中最多顶点个数template <class DataType>
class MGraph
{
public:MGraph(DataType a[ ], int n, int e);    //构造函数，建立具有n个顶点e条边的图~MGraph( ) { }                     //析构函数为空void DFSTraverse(int v);              //深度优先遍历图void BFSTraverse(int v);               //广度优先遍历图
private:DataType vertex[MaxSize];          //存放图中顶点的数组int arc[MaxSize][MaxSize];          //存放图中边的数组int vertexNum, arcNum;             //图的顶点数和边数
};
#endif

//MGraph.cpp#include <iostream>
using namespace std;
#include "MGraph.h"                                          //引入头文件template <class DataType>
MGraph<DataType>::MGraph(DataType a[ ], int n, int e)
{int i, j;vertexNum=n; arcNum=e;for (i=0; i<vertexNum; i++)vertex[i]=a[i];for (i=0; i<vertexNum; i++)for (j=0; j<vertexNum; j++)arc[i][j]=0;for (int k=0; k<arcNum; k++){cout<<"请输入边的两个顶点的序号：";cin>>i;cin>>j;arc[i][j]=1; arc[j][i]=1;	}
}template <class DataType>
void MGraph<DataType>::DFSTraverse(int v)
{cout << vertex[v]; visited[v] = 1;for (int j = 0; j < vertexNum; j++)if (arc[v][j] == 1 && visited[j]==0) DFSTraverse(j);
}template <class DataType>
void MGraph<DataType>::BFSTraverse(int v)
{int Q[MaxSize];int front = -1, rear = -1;int k;  //初始化队列,假设队列采用顺序存储且不会发生溢出cout << vertex[v]; visited[v] = 1;  Q[++rear] = v;   //被访问顶点入队while (front != rear)                   //当队列非空时{k= Q[++front];                   //将队头元素出队并送到v中for (int j = 0; j < vertexNum; j++)if (arc[k][j] == 1 && visited[j] == 0 ) {cout << vertex[j]; visited[j] = 1; Q[++rear] = j;}}
}

//MGraphmain.cpp#include <iostream>
using namespace std;
#include "MGraph.cpp"                                         //引用graph.cpp文件
int visited[MaxSize]={0};int main( )
{char ch[]={'A','B','C','D','E'};MGraph<char> MG(ch, 5, 6);for (int i=0; i<MaxSize; i++)visited[i]=0;cout<<"深度优先遍历序列是：";MG.DFSTraverse(1);cout<<endl;for (int i=0; i<MaxSize; i++)visited[i]=0;cout<<"广度优先遍历序列是：";MG.BFSTraverse(0);cout<<endl;return 0;
}