graph1.cpp

图的运算

#include<iostream.h>
#include"graph1.h"
void Check(int n,int& i,int& j);
void InitGMatix(adjmatrix& GA,int n)
{
	GA=new int *[n];
	int i,j;
	for(i=0;i<n;i++)
		GA[i]=new int [n];
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(i==j)GA[i][j]=0;
			else GA[i][j]=MaxValue;
}
void CreateMatrix(adjmatrix GA,int n, int k1,int k2)
{
	int i,j,k,e,w;
	cout<<"输入图的总边数：";
	cin>>e;
	if(k1==0 && k2==0){
		cout<<"输入"<<e<<"条无向无权边的起点和终点序号！"<<endl;
		for(k=1;k<=e;k++){
			cin>>i>>j;
			Check(n,i,j);
			GA[i][j]=GA[j][i]=1;
		}
	}
	else if(k1==0 && k2!=0){
		cout<<"输入"<<e<<"条无向带权边的起点和终点序号及权值！"<<endl;
		for(k=1;k<=e;k++){
			cin>>i>>j>>w;
			Check(n,i,j);
			GA[i][j]=GA[j][i]=w;
		}
	}
	else if(k1!=0 && k2==0){
		cout<<"输入"<<e<<"条有向无权边的起点和终点序号！"<<endl;
		for(k=1;k<=e;k++){
			cin>>i>>j;
			Check(n,i,j);
			GA[i][j]=1;
		}
	}
	else if(k1!=0 && k2!=0){
		cout<<"输入"<<e<<"条有向有权边的起点和终点序号及权值！"<<endl;
		for(k=1;k<=e;k++){
			cin>>i>>j>>w;
			Check(n,i,j);
			GA[i][j]=w;
		}
	}
}
void dfsMatrix(adjmatrix GA,bool*& visited,int i,int n)
{
	cout<<i<<' ';
	visited[i]=true;
	for(int j=0;j<n;j++)
		if(i!=j && GA[i][j]!=MaxValue && !visited[j])
			dfsMatrix(GA,visited,j,n);
}
void bfsMatrix(adjmatrix GA,bool *& visiited,int i,int n)
{
	const int MaxLength=30;
	int q[MaxLength]={0};
	int front=0,rear=0;
	cout<<i<<' ';
	visiited[i]=true;
	q[++rear]=i;
	while(front!=rear){
		front=(front+1)%MaxLength;
		int k=q[front];
		for(int j=0;j<n;j++)
		{
			if(k!=j && GA[k][j]!=MaxValue && !visiited[j]){
				cout<<j<<' ';
				visiited[j]=true;
				rear=(rear+1)%MaxLength;
				q[rear]=j;
			}
		}
	}
}
void InitGAdjoin(adjlist& GL,int n)
{
	GL=new edgenode* [n];
	for(int i=0;i<n;i++) GL[i]=NULL;
}
void CreateAdjoin(adjlist GL,int n,int k1,int k2)
{
	int i,j,k,e,w;
	cout<<"输入图的总边数；";
	cin>>e;
	if(k1==0 && k2==0){
		cout<<"输入"<<e<<"条无向无权边的起点和终点序号！"<<endl;
		for(k=1;k<=e;k++){
			cin>>i>>j;
			Check(n,i,j);
			edgenode* p=new edgenode;
			p->adjvex=j;p->weight=1;
			p->next=GL[i];
			GL[i]=p;
			p=new edgenode;
			p->adjvex=i;p->weight=1;
			p->next=GL[j];
			GL[j]=p;
		}
	}
	else if(k1==0 && k2!=0){
		cout<<"输入"<<e<<"条无向带权边的起点和终点序号及权值！"<<endl;
		for(k=1;k<=e;k++){
			cin>>i>>j>>w;
			Check(n,i,j);
			edgenode* p=new edgenode;
			p->adjvex=j;p->weight=w;
			p->next=GL[i];
			GL[i]=p;
			p=new edgenode;
			p->adjvex=i;p->weight=w;
			p->next=GL[j];
			GL[j]=p;
		}
	}
	else if(k1!=0 && k2==0){
		cout<<"输入"<<e<<"条有向无权边的起点和终点序号！"<<endl;
		for(k=1;k<=e;k++){
			cin>>i>>j;
			Check(n,i,j);
			edgenode* p=new edgenode;
			p->adjvex=j;p->weight=1;
			p->next=GL[i];
			GL[i]=p;
		} 
	}  
	else if(k1!=0 && k2!=0){
		cout<<"输入"<<e<<"条有向有权边的起点和终点序号及权值！"<<endl;
		for(k=1;k<=e;k++){
			cin>>i>>j>>w;
			Check(n,i,j);
			edgenode* p=new edgenode;
			p->adjvex=j;p->weight=w;
			p->next=GL[i];
			GL[i]=p;
		}
	}
}
void dfsAdjoin(adjlist GL,bool *& visited, int i,int n)
{
	cout<<i<<' ';
	visited[i]=true;
	edgenode* p=GL[i];
	while(p!=NULL){
		int j=p->adjvex;
		if(!visited[j])
			dfsAdjoin(GL,visited,j,n);
		p=p->next;
	}
}
void bfsAdjoin(adjlist GL,bool*& visited,int i,int n)
{
	const int MaxLength=30;
	int q[MaxLength]={0};
	int front=0,rear=0;
	cout<<i<<' ';
	visited[i]=true;
	q[++rear]=i;
	while(front!=rear){
		front=(front+1)%MaxLength;
		int k=q[front];
		edgenode* p=GL[k];
		while(p!=NULL)
		{
			int j=p->adjvex;
			if(!visited[j]){
				cout<<j<<' ';
				visited[j]=true;
				rear=(rear+1)%MaxLength;
				q[rear]=j;
			}
			p=p->next;
		}
	}
	
}
void Check(int n,int& i,int& j)
{
	while(1){
		if(i<0||i>=n||j<0||j>=n)
			cout<<" 输入有误，请重输！";
		else return;
		cin>>i>>j;
	}
}
void graphChange(adjmatrix GA,adjlist GL,int n)
{
	int i,j;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(GA[i][j]!=0 && GA[i][j]!=MaxValue){
				edgenode* p=new edgenode;
				p->adjvex=j;
				p->weight=GA[i][j];
				p->next=GL[i];
				GL[i]=p;
			}
		}
	}
}