graphopr.cpp

创建邻接矩阵 广度优先搜索 深度优先搜索

#include<stdio.h>
#include<stdlib.h>

#define MAX 20
#define MAXQ 100

typedef struct ArcNode
{
	int vex;
	struct ArcNode *next;
}ArcNode,*ptrnode,ArcList[MAX];

typedef struct 
{
	int *base;
	int front,rear;
}SqQueue;

void InitQueue(SqQueue *Q);
void EnQueue(SqQueue *Q,int e);
void DeQueue(SqQueue *Q,int *u);

void createUDN(int verx[ ][MAX],int v,int e);              //创建邻接矩阵
void printUDN(int verx[ ][MAX],int v);                     //输出邻接矩阵
void DFStraverseUDN(int vexnum[MAX],int verx[ ][MAX],int v);   //深度优先搜索邻接矩阵
void DFSUDN(int vexnum[MAX],int verx[ ][MAX],int i,int v);
void BFStraverseUDN(int vexnum[MAX],SqQueue Q,int verx[ ][MAX],int v); //广度优先搜索邻接矩阵


void CreateAdjList(struct ArcNode ArcList[MAX],int v,int e);     //创建邻接表
void DFStraverseL(struct ArcNode ArcList[MAX],int vexnum[MAX],int v);   //深度优先搜索邻接表
void DFSL(struct ArcNode ArcList[MAX],int vexnum[MAX],int i);
void BFStraverseL(struct ArcNode ArcList[MAX],int vexnum[MAX],SqQueue Q,int v); //广度优先搜索邻接表


void main()
{
	int i,v,e;
	int vexnum[MAX];
	int verx[MAX][MAX];
	SqQueue Q;
	struct ArcNode ArcList[MAX];
	

	printf("输入顶点数和边数:");            //输入序列：8 9  1 2  2 4  2 5  5 8  4 8  1 3  3 6  3 7  6 7
	scanf("%d%d",&v,&e);                    

	for(i=1;i<=v;i++)
		vexnum[i]=0;     //设置访问标志



//	createUDN(verx,v,e);      //创建邻接矩阵
//	printUDN(verx,v);         //输出邻接矩阵
//	DFStraverseUDN(vexnum,verx,v);    //深度优先搜索邻接矩阵
//	BFStraverseUDN(vexnum,Q,verx,v);    //广度优先搜索邻接矩阵

	CreateAdjList(ArcList,v,e);   //创建邻接表
	DFStraverseL(ArcList,vexnum,v);    //深度优先搜索邻接表
//	BFStraverseL(ArcList,vexnum,Q,v);  //广度优先搜索邻接表




}


void createUDN(int verx[ ][MAX],int v,int e)         //创建邻接矩阵
{
	int i,j,v1,v2;

	for(i=1;i<=v;i++)
		for(j=1;j<=v;j++)
			verx[i][j]=0;

		printf("输入邻接的两顶点:\n");

		for(i=1;i<=e;i++)
		{
			scanf("%d%d",&v1,&v2);
			verx[v1][v2]=verx[v2][v1]=1;
		}
		
}

void printUDN(int verx[ ][MAX],int v)      //输出邻接矩阵
{ 
	int i,j;
   
    printf("输入的邻接矩阵为:\n");
	for(i=0;i<=v;i++)
		printf("%4d",i);
    printf("\n");

	for(i=1;i<=v;i++)
	{
		printf("%4d",i);
		for(j=1;j<=v;j++)
			printf("%4d",verx[i][j]);	
		
			printf("\n");
	}
}


void DFStraverseUDN(int vexnum[MAX],int verx[ ][MAX],int v)   //深度优先搜索邻接矩阵
{
	int i;

	printf("深度优先搜索邻接矩阵结果如下:\n");
	for(i=1;i<=v;i++)
		if(vexnum[i]==0)
			DFSUDN(vexnum,verx,i,v);

	printf("\n");

}

void DFSUDN(int vexnum[MAX],int verx[ ][MAX],int i,int v)
{
	int j;

	vexnum[i]=1;
	printf("%4d",i);

	for(j=1;j<=v;j++)
		if(verx[i][j]==1)
			if(vexnum[j]==0)
				DFSUDN(vexnum,verx,j,v);
			
}


void BFStraverseUDN(int vexnum[MAX],SqQueue Q,int verx[ ][MAX],int v) //广度优先搜索邻接矩阵
{
	int i,j,u;

	printf("广度优先搜索邻接矩阵结果如下:\n");

	InitQueue(&Q);

	for(i=1;i<=v;i++)
		if(vexnum[i]==0)
		{
			vexnum[i]=1;
			printf("%4d",i);

			EnQueue(&Q,i);

			while(Q.base[Q.front]!=Q.base[Q.rear])
			{
				DeQueue(&Q,&u);

				for(j=1;j<=v;j++)
					if(verx[u][j]==1)
			            if(vexnum[j]==0)
				              EnQueue(&Q,j);
			}                
			
		}

		printf("\n");
}


	
void CreateAdjList(struct ArcNode ArcList[MAX],int v,int e)    //创建邻接表
{
	int i,v1,v2;
	
	ptrnode p;

	for(i=1;i<=v;i++)
	{
		ArcList[i].vex=i;
		ArcList[i].next=NULL;
	}

	for(i=1;i<=e;i++)
	{
		scanf("%d%d",&v1,&v2);
		p=(ptrnode)malloc(sizeof(ArcNode));
		p->vex=v2;
		p->next=ArcList[v1].next;
		ArcList[v1].next=p;
	}



}


void DFStraverseL(struct ArcNode ArcList[MAX],int vexnum[MAX],int v)   //深度优先搜索邻接表
{
	int i;

	printf("深度优先搜索邻接表结果如下:\n");

	for(i=1;i<=v;i++)
		if(vexnum[i]==0)
			DFSL(ArcList,vexnum,i);

	printf("\n");
}

void DFSL(struct ArcNode ArcList[MAX],int vexnum[MAX],int i)
{
	ptrnode p;

	vexnum[i]=1;
	printf("v%d  ",i);

	for(p=ArcList[i].next;p;p=p->next)
	{
		if(vexnum[p->vex]==0)
			DFSL(ArcList,vexnum,p->vex);
	}
}



void BFStraverseL(struct ArcNode ArcList[MAX],int vexnum[MAX],SqQueue Q,int v)    //广度优先搜索邻接表
{
	int i;
	ptrnode p;

	printf("广度优先搜索邻接表结果如下:\n");

	InitQueue(&Q);

	for(i=1;i<=v;i++)
		if(vexnum[i]==0)
		{
			vexnum[i]=1;
			printf("%4d",i);

			EnQueue(&Q,i);

			while(Q.base[Q.front]!=Q.base[Q.rear])
			{
				DeQueue(&Q,&i);

                for(p=ArcList[i].next;p;p=p->next)
					if(vexnum[p->vex]==0)
					{
						vexnum[p->vex]=1;
						printf("%4d",p->vex);

						EnQueue(&Q,p->vex);
					}
			}
		}

		printf("\n");
}



void InitQueue(SqQueue *Q)
{
	(*Q).base=(int *)malloc(MAXQ*sizeof(int));
	(*Q).front=(*Q).rear=0;
}

void EnQueue(SqQueue *Q,int e)
{
	(*Q).base[(*Q).rear]=e;
	(*Q).rear=((*Q).rear+1)%MAXQ;
}

void DeQueue(SqQueue *Q,int *u)
{
	*u=(*Q).base[(*Q).front];
	(*Q).front=((*Q).front+1)%MAXQ;
}