graph.cpp

数据结构经典算法的C语言实现 计算机专业数据结构课程实验

#include <iostream.h>
#include <limits.h>

#define MaxValue Int_Max
#define NumVertices 10		  //最大顶点数
#define NumEdges 45			  //最大边数

typedef char VertexData;      //顶点数据类型

//邻接矩阵表示
typedef struct {
	VertexData vexlist[NumVertices];			//顶点表
	int edge[NumVertices][NumVertices];	        //邻接矩阵－边表，可视为边之间的关系
	int n, e;									//图中当前的顶点个数和边数			
} MTGraph;

//邻接表表示
typedef struct node {	  //边表结点
	int adjvex;			  //邻接点域（下标）
	struct node *next;	  //下一边链接指针
} EdgeNode;	
typedef struct {          //顶点表结点
	VertexData vertex;	  //顶点数据域
	EdgeNode*  firstedge; //边链表头指针
} VertexNode;
typedef struct {          //图的邻接表
	VertexNode vexlist[NumVertices];	
	int n, e;             //图中当前的顶点个数和边数
} AdjGraph;

//构造无向图的邻接矩阵
void CreateMTGraph(MTGraph * G) {
	int i, j, k;

	cout<<"请输入图的顶点个数和边的条数，中间用空格隔开，如 6 9：\n";
	cin>>G->n>>G->e;			        //输入顶点数和边数
	
	cout<<"按顶点编号0,1,2,……依次输入顶点信息，如有三个顶点则可输入abc：\n";
	for(i = 0; i < G->n; i++)			//读入顶点信息，建立顶点表
		cin>>G->vexlist[i];	 
	
	for(i = 0; i < G->n; i++)
		for(j = 0;j < G->n; j++)
			G->edge[i][j] = 0;			//邻接矩阵初始化
	cout<<"按顶点的编号输入各边，如有两条边则可输入0 1回车、1 2回车：\n";
	for( k = 0;k < G->e; k++) {		    //读入e条边建立邻接矩阵
		 cin>>i>>j;		
		 G->edge[i][j] = 1;
		 G->edge[j][i] = 1;
	}
}

//构造无向图的邻接表
void CreateGraph(AdjGraph &G) {
	int i, tail, head;
	EdgeNode* p;
	
	cout<<"请输入图的顶点个数和边的条数，中间用空格隔开，如 6 9：\n";
	cin>>G.n>>G.e;						//输入顶点个数和边数
	
	cout<<"按顶点编号0,1,2,……依次输入顶点信息，如有三个顶点则可输入abc：\n";
	for(i = 0; i < G.n; i++) {	            //建立顶点表		
		cin>>G.vexlist[i].vertex;			//输入顶点信息
		G.vexlist[i].firstedge = NULL;	//边表置为空表
	}
	cout<<"依次输入每条边的头、尾结点，如有两条边则可输入0 1回车、1 2回车：\n"; 
	for(i = 0; i < G.e; i++) {				//逐条边输入，建立边表
		cin>>tail>>head;			
		p = new EdgeNode;			        //建立边结点
		p->adjvex = head;					//设置边结点
		p->next = G.vexlist[tail].firstedge;		//链入第tail号链表的前端
		G.vexlist[tail].firstedge = p;
		
		p = new EdgeNode;
		p->adjvex = tail;
		p->next = G.vexlist[head].firstedge;	    //链入第head号链表的前端
		G.vexlist[head].firstedge = p;
	}	
}

//输出无向图的邻接矩阵
void displayMTG(MTGraph MG) {
	int i = 0, j = 0;
	for(i = 0; i < MG.n; i++) {
		for(j = 0; j < MG.n; j++)
			cout<<MG.edge[i][j]<<" ";
		cout<<"\n";
	}
	cout<<"\n";
}

//输出无向图的邻接表
void displayAG(AdjGraph AG) {
	int i = 0;
	EdgeNode* p;
	for(i = 0; i < AG.n; i++) {
		cout<<i<<" "<<AG.vexlist[i].vertex<<":";
		p = AG.vexlist[i].firstedge;
		while (p != NULL) {
			cout<<AG.vexlist[p->adjvex].vertex;
			p = p->next;
		}
		cout<<"\n";
	}
}


//无向图的先深搜索
typedef enum {FLASE, TRUE} Boolean;
Boolean visited[NumVertices];

//以Vi为出发点时对邻接矩阵表示的图G进行先深搜索
void DFS2(MTGraph*G, int i) {
	int j;

	cout<<G->vexlist[i];                //访问结点vi
	visited[i] = TRUE;					//标记vi已访问过 
	for(j = 0; j < G->n; j++)			//依次搜索vi的邻接点
		if((G->edge[i][j] != 0) && (visited[j] == 0))   //若vj尚未访问过
			DFS2(G, j);
}
//无向图的邻接矩阵先深搜索
void MTDFS(MTGraph &G) {
	int i = 1;
	for(i = 0; i < G.n; i++)
		visited[i] = FLASE;      //标志数组初始化
	for(i = 0; i < G.n; i++)
		if(visited[i] == 0)
			DFS2(&G, i);
}

//以Vi为出发点时对邻接表表示的图G进行先深搜索
void DFS1(AdjGraph*G, int i) {
	EdgeNode *p;
	
	cout<<G->vexlist[i].vertex;        //访问顶点
	visited[i] = TRUE;					//标记vi已经访问过
	p = G->vexlist[i].firstedge;		//取vi边表的头指针
	while( p != NULL) {					//依次搜索vi的邻接点vj，这里j = p->adjvex 
		if(visited[p->adjvex] == 0)	    //若vj没被访问过，则以vj为出发点先深搜索	
			DFS1(G, p->adjvex);
		p = p->next;
	}
}
//无向图的邻接表先深搜索
void AGDFS(AdjGraph &G) {
	int i = 1;
	for(i = 0; i < G.n; i++)
		visited[i] = FLASE;      //标志数组初始化
	for(i = 0; i < G.n; i++)
		if(visited[i] == 0)
			DFS1(&G, i);
}


//无向图的先广搜索，其中使用了队列
//队列中每个结点的型 
struct celltype {
	int  element;
	celltype *next;
};
//队列的型 
struct QUEUE {
	celltype *front;
	celltype *rear;
};

//将队列Q置空  
void MAKENULL(QUEUE &Q) {
	Q.front = new celltype;      //建立表头结点 
	Q.front->next = NULL;
	Q.rear = Q.front;        
}
//检查队列Q是否为空，空返回1，不空返回0
int EMPTY(QUEUE Q) {
	if(Q.front == Q.rear)
		return 1;
	else
		return 0;
}
//插入一个元素X到队列Q的后端
void ENQUEUE(int x, QUEUE &Q) {
	Q.rear->next = new celltype;    //在队列的后端加一个新结点 
	Q.rear = Q.rear->next;
	Q.rear->element = x;
	Q.rear->next = NULL;
}
//返回队列Q的第一个元素并在队列中删除此元素
int FRONT(QUEUE &Q) {
	celltype *tmp;
	int i;

	i = Q.front->next->element;
	tmp = Q.front->next;
	Q.front->next = tmp->next;
	delete tmp;
	if(Q.front->next == NULL)
		Q.rear = Q.front;
	
	return i;
}

//以vi为出发点时对邻接矩阵表示的图G进行先广搜索
void BFS1(MTGraph G, int k) {
	QUEUE  Q;
	int i, j;

	MAKENULL(Q);
	cout<<G.vexlist[k];
	visited[k] = TRUE;             //标记vk已访问过 
	ENQUEUE(k, Q);

	while(!EMPTY(Q))               //队列空时搜索结束 
	{
		i = FRONT(Q);
		for(j=0; j < G.n; j++) {
			if(!G.edge[i][j] == 0 && !visited[j]) {    //若vj未被访问过
				cout<<G.vexlist[j];
				visited[j] = TRUE;
				ENQUEUE(j, Q);
			}
		}   //重复循环，检测vk的所有邻接顶点
	}   //外层循环，判断队列是否为空 
}
//无向图的邻接矩阵先广搜索
void MTBFS(MTGraph G) {
	int i;

	for(i=0; i < G.n; i++)
		visited[i] = FLASE;        //标记数组初始化 
	for(i=0;i<G.n;i++) {
		if(!visited[i])
			BFS1(G, i);            //从顶点i出发开始搜索 
	}
}	

//以vi为出发点时对邻接表表示的图G进行先广搜索 
void BFS2(AdjGraph G, int k) {
	EdgeNode *p;
	QUEUE Q;
	int i;

	MAKENULL(Q);
	cout<<G.vexlist[k].vertex;
	visited[k] = TRUE;
	ENQUEUE(k, Q);       

	while(!EMPTY(Q)) {     //队列空则搜索结束 
		i = FRONT(Q);
		p = G.vexlist[i].firstedge;     //取vi的边表头指针 
		while(p) {
			if(!visited[p->adjvex]) {
				cout<<G.vexlist[p->adjvex].vertex;   //访问vj 
				visited[p->adjvex] = TRUE;             //标记vj已访问过 
				ENQUEUE(p->adjvex, Q);                 //访问过的vj入队 
			}
			p = p->next;
		}  //重复检测vi的所有邻接顶点 
	}   //外层循环，判断队列是否为空 
}
//无向图的邻接表先广搜索
void AGBFS(AdjGraph G) {
	int i;

	for(i=0; i < G.n; i++)
		visited[i] = FLASE;          //标记数组初始化 
	for(i=0; i < G.n; i++) {
		if(!visited[i])
			BFS2(G, i);              //从顶点i出发开始搜索 
	}
}

void main() {
	MTGraph MG;
	AdjGraph AG;
	char yn = 'y';
	int i = 0;

	while(yn == 'Y' || yn == 'y') {
		cout<<"请选择建立无向图的方式：\n１：邻接矩阵    ２：邻接表\n";
		cin>>i;
		
		switch(i) {
			case 1:
				CreateMTGraph(&MG);
				cout<<"邻接矩阵为：\n";
				displayMTG(MG);
				cout<<"先深搜索结果为：\n";
				MTDFS(MG);
				cout<<"\n";
				cout<<"先广搜索结果为：\n";
				MTBFS(MG);
				cout<<"\n";
				break;
			case 2:
				CreateGraph(AG);
				cout<<"邻接表为：\n";
				displayAG(AG);
				cout<<"先深搜索结果为：\n";
				AGDFS(AG);
				cout<<"\n";
				cout<<"先广搜索结果为：\n";
				AGBFS(AG);
				cout<<"\n";
				break;
			default:
				cout<<"选择错误！\n";
				break;
		}
		cout<<"是否继续使用本程序？(Y/N)：";
		cin>>yn;
	}		
}