graph1.h

1

#include<iomanip.h>
#include<iostream.h>
class Matrix{
public:
	int MaxValue;
	int VertexNum;//--------图的顶点数
	int EdgeNum;//----------图的边数
	bool visited[50];
	char vexlist[50];//--------存储顶点信息的数组
	int  adjmatrix[50][50];//----存储邻接矩阵的数组
	bool C1;//----------判断是否带权
	bool C2;//----------判断是否无向

	void Initvisited();
	void InitMatrix();
	void CreateMatrix();//------创建邻接矩阵
	void PrintMatrix();//---------输出邻接矩阵
	void dfsMatrix(int i);//-------深度优先搜索邻接矩阵表示的图
	void bfsMatrix(int i);//-------广度优先搜索邻接矩阵表示的图
};
void Matrix::Initvisited(){
	for(int i=0;i<=50;i++)visited[i]=false;
}

void Matrix::InitMatrix(){
	char input;
	cout<<"请输入顶点个数：";
	int i;
	cin>>i;
	VertexNum=i;
	cout<<endl<<"请输入边数：";
	cin>>i;
	EdgeNum=i;
	cout<<endl;
	cout<<"是带权图吗(Y/N)?";
	cin>>input;
	if(input=='Y'||input=='y')C1=true;
	else C1=false;
	cout<<endl;
	cout<<"是无向图吗(Y/N)?";
	cin>>input;
	if(input=='Y'||input=='y')C2=true;
	else C2=false;
	cout<<endl;
	MaxValue=10000;
	for(int j=0;j<100;j++)visited[j]=false;
}

void Matrix::CreateMatrix(){
	int i,j,k,w;
	cout<<"请连续输入"<<VertexNum<<"个顶点,以空格间隔："<<endl;
	for(i=0;i<VertexNum;i++)cin>>vexlist[i];
	for(i=0;i<VertexNum;i++){
			for(j=0;j<VertexNum;j++){
				if(i==j)adjmatrix[i][j]=0;
				else adjmatrix[i][j]=MaxValue;
			}
	}
	if(C1==true&&C2==true){
		cout<<"请输入"<<EdgeNum<<"条边(请输入两端点序号和权,以空格间隔)："<<endl;
		for(k=1;k<=EdgeNum;k++){
			cin>>i>>j>>w;
			adjmatrix[i][j]=adjmatrix[j][i]=w;
		}
	}
	if(C1==false&&C2==true){
		cout<<"请输入"<<EdgeNum<<"条边(两端点序号以空格间隔)："<<endl;
		for(k=1;k<=EdgeNum;k++){
			cin>>i>>j;
			adjmatrix[i][j]=adjmatrix[j][i]=1;
		}
	}
 if(C1==false&&C2==false){
		cout<<"请输入"<<EdgeNum<<"条边(两端点序号以空格间隔)："<<endl;
		for(k=1;k<=EdgeNum;k++){
			cin>>i>>j;
			adjmatrix[i][j]=1;
		}
	}           
if(C1==true&&C2==false){

		cout<<"请输入"<<EdgeNum<<"条边(请输入两端点序号和权,以空格间隔)："<<endl;
		for(k=1;k<=EdgeNum;k++){
			cin>>i>>j>>w;
			adjmatrix[i][j]=w;
		}
	}
}

void Matrix::PrintMatrix(){
	int i,j;
	cout<<endl;
    cout<<"顶点:"<<endl;
	cout<<setw(10);
	for(i=0;i<VertexNum;i++)cout<<vexlist[i]<<setw(4);
	cout<<endl<<endl;
	cout<<"邻接矩阵:"<<endl;
	cout<<setw(3);
	for(i=0;i<VertexNum;i++){
		for(j=0;j<VertexNum;j++){
			if(adjmatrix[i][j]==MaxValue&&C1==true)cout<<"∞"<<setw(5);
			else if(adjmatrix[i][j]==MaxValue&&C1==false)cout<<0<<setw(5);
			else cout<<adjmatrix[i][j]<<setw(5);
		}
		cout<<endl<<setw(3);
	}

}

void Matrix::dfsMatrix(int i){
	cout<<i<<' ';
	visited[i]=true;
	for (int j=0;j<VertexNum;j++){
		if(adjmatrix[i][j]!=0&&adjmatrix[i][j]!=MaxValue&&!visited[j])
			dfsMatrix(j);
	}
}

void Matrix::bfsMatrix(int i){
	for(int w=0;w<=VertexNum;w++)visited[w]=false;
	int queue[50];
	int front,rear;
	front=rear=0;
	cout<<i<<' ';
	visited[i]=true;
	queue[++front]=i;
	while(front!=rear){
		int k=queue[++rear];
		for(int j=0;j<VertexNum;j++){
			if(adjmatrix[k][j]!=0&&adjmatrix[k][j]!=MaxValue&&!visited[j]){
				cout<<j<<' ';
				visited[j]=true;
				queue[++front]=j;
			}
		}
	}
}