实验六 邻接矩阵

#include<iostream.h>
const int MaxSize=10;

template<class DataType>
class MGraph
{
public:
	MGraph(DataType a[],int n,int e);
	~MGraph(){}
	void DFSTraverse(int v);
	void BFSTraverse(int v);
	void Next();
private:
	DataType vertex[MaxSize];
	int arc[MaxSize][MaxSize];
	int vertexNum,arcNum;
};
template<class DataType>
MGraph<DataType>::MGraph(DataType a[],int n,int e)
{
	int i,j,k;
	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(k=0;k<arcNum;k++)
	{
		cout<<"请输入边的两个顶点的序号：";
		cin>>i>>j;
		arc[i][j]=1;arc[j][i]=1;
	}
}
template<class DataType>
void MGraph<DataType>::DFSTraverse(int v)
{
	int j;
	cout<<vertex[v];visited[v]=1;
	for(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 j;
	int Q[MaxSize];
	int front=-1,rear=-1;
	cout<<vertex[v];visited[v]=1;Q[++rear]=v;
	while(front!=rear)
	{
		v=Q[++front];
		for(j=0;j<vertexNum;j++)
			if(arc[v][j]==1&&visited[j]==0)
			{
				cout<<vertex[j];visited[j]=1;Q[++rear]=j;
			}
	}
}
template<class DataType>  
void MGraph<DataType>::Next()  
{  
    for(int i=0;i<vertexNum;i++)    
    {  
        cout<<vertex[i]<<"的邻接点为: ";    
        for(int j=0;j<vertexNum;j++)    
            if(arc[i][j]==1&&visited[j]==0)    
                cout<<vertex[j]<<" ";    
    cout<<endl;}    
}
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(0);
	cout<<endl;
	for(i=0;i<MaxSize;i++)
		visited[i]=0;
	cout<<"广度优先遍历序列是：";
	MG.BFSTraverse(0);
	cout<<endl;
	for(i=0;i<MaxSize;i++)
		visited[i]=0;
	MG.Next();
	cout<<endl;
	return 0;
}