graphfunction.cpp

这是关于数据结构习题书,清华大学出版社出版,上实验五的一个实验,自己写的,多多指教

#include"GraphFile.h"
void CreatGraph(ALGraph &G)
//自行输入图时创建图
{
	ArcNode *p,*q;
	int ivex,jvex;
	printf("请输入边集(请用边号输入):以 0,0 结束边的输入\n");
	scanf("%d,%d",&ivex,&jvex);
	//输入第一条边，用边号输入
	while(ivex!=0 && jvex!=0){
		p=(struct ArcNode *)malloc(sizeof(struct ArcNode));
		p->adjvex=jvex;
		p->nextarc=NULL;
		if(G.AdjList[ivex].firstarc==NULL) G.AdjList[ivex].firstarc=p; 
		else{
			q=G.AdjList[ivex].firstarc;
			while(q->nextarc!=NULL)
				q=q->nextarc;
			q->nextarc=p;
		}
		scanf("%d,%d",&ivex,&jvex);
	}
}

void CreatFGraph(ALGraph &G)
//用文件创建图
{
	FILE *fp;
	ArcNode *p,*q;
	int ivex,jvex;
	if((fp=fopen("Graph.txt","r"))==NULL){
		printf("cannot open the file!\n");
		exit(0);
	}
	//打开文件，该文件包含每个顶点所关联的边集
	fscanf(fp,"%d,%d",&ivex,&jvex);
	//从文件读出一条边
	while(ivex!=0 && jvex!=0){
		p=(struct ArcNode *)malloc(sizeof(struct ArcNode));
		p->adjvex=jvex;
		p->nextarc=NULL;
		if(G.AdjList[ivex].firstarc==NULL) G.AdjList[ivex].firstarc=p; 
		else{
			q=G.AdjList[ivex].firstarc;
			while(q->nextarc!=NULL)
				q=q->nextarc;
			q->nextarc=p;
		}
		fscanf(fp,"%d,%d",&ivex,&jvex);
	}
}


int FirstAdjVex(ALGraph &G,int v)
{
	//V在G中所关联的第一条边的顶点
	ArcNode *p;
	p=G.AdjList[v].firstarc;
	if(p!=NULL) return(p->adjvex);
	else return(-1);
}

int NextAdjVex(ALGraph &G,int v,int w)
{
	//G中相对于V所关联的下一条边的顶点
	ArcNode *p;
	p=G.AdjList[v].firstarc;
	while(p!=NULL){
		if(p->adjvex==w){
			if(p->nextarc!=NULL)  return(p->nextarc->adjvex);
		}
		p=p->nextarc;
	}
	return(-1);
}

/*void visitFunc(int ivex)
{
	printf("%d ",ivex);
}
*/
int DeQueue(queue &Q)
{
	//删除队列中的第一个成员
	QNode *q;
	int u;
	if(Q.front==Q.rear){
		printf("error!\n");
		exit(0);
	}
	if(Q.front->next==Q.rear){
		q=Q.front->next;
		Q.rear=Q.front;
	}
	q=Q.front->next;
	u=q->date;
	Q.front->next=q->next;
	free(q);
	return(u);
}

int QueueEmpty(queue &Q)
{
	//判断是否为空队列
	if(Q.front==Q.rear) return(1);
	return(0);
}

void InitQueue(queue &Q)
{
	//初始化队列
	if((Q.front=(struct QNode *)malloc(sizeof(struct QNode)))==NULL){
		printf("error!\n");
		exit(0);
	}
	Q.rear=Q.front;
	Q.front->next=NULL;
}

void EnQueue(queue &Q,int ivex)
{
	//元素插入队列
	QNode * q;
	q=(struct QNode *)malloc(sizeof(struct QNode));
	q->date=ivex;
	q->next=NULL;
	Q.rear->next=q;
	if(Q.front->next==NULL) Q.front->next=q;
	Q.rear=q;
}

void PutBound(ALGraph &G,queue &Q1)
{
	//输出边集
	char ch1[20],ch2[20];
	int ivex,jvex;
	ivex=DeQueue(Q1);
	strcpy(ch1,G.AdjList[ivex].data.VexMessage);
	while(!QueueEmpty(Q1)){
		jvex=DeQueue(Q1);
		strcpy(ch2,G.AdjList[jvex].data.VexMessage);
		printf("%s,%s  ",ch1,ch2);
		strcpy(ch1,ch2);
	}
}

void DVisitGraph(ALGraph &G,int * Dvisit,int ivex,queue &Q1)
{
	//深度优先遍历
	int w;
	Dvisit[ivex]=1;
	EnQueue(Q1,ivex);
	//visitFunc(ivex);
	for(w=FirstAdjVex(G,ivex);w>0;w=NextAdjVex(G,ivex,w)){
		if(w==-1) printf("error!\n");
		if(!Dvisit[w]) DVisitGraph(G,Dvisit,w,Q1);
	}
}

void GVisitGraph(ALGraph &G,int * Gvisit,int ivex)
{
	//广度优先遍历
	queue Q,Q2;
	int w,u;
	InitQueue(Q);
	for(ivex=1;ivex<=G.vexnum;ivex++){
		InitQueue(Q2);
		if(!Gvisit[ivex]){
			Gvisit[ivex]=1;
		//	visitFunc(ivex);
			EnQueue(Q,ivex);
			EnQueue(Q2,ivex);
			while(!QueueEmpty(Q)) {
				u=DeQueue(Q);
				for(w=FirstAdjVex(G,u);w>0;w=NextAdjVex(G,u,w))
					if(!Gvisit[w]){
						Gvisit[w]=1;
					//	visitFunc(w);
						EnQueue(Q,w);
						EnQueue(Q2,w);
					}

			}
			PutBound(G,Q2);
		}
	}
}