图 2003374313 李南宁.c

本程序用邻接矩阵实现图的深度优先遍历 图的广度优先遍历

/*------------------------------------Program Description----------------------------------------*/
/*图的基本操作                                                                                   */
/*李南宁                 03级计算机科学与技术 3班               2003374313                       */
/*-----------------------------------------------------------------------------------------------*/
#include <stdio.h>
#define vertexnum 9                                     /*定义顶点数*/
#define queuemax 10
struct node{                                          /*声明图形顶点结构*/
int vertex;                                            /*邻接顶点数据*/
struct node *next;                                      /*下一个邻接顶点*/
};                                               
typedef struct node *graph;                            /*定义图形结构*/
struct node head[vertexnum];                            /*顶点数组*/
int visited[vertexnum]={0};
int queue[queuemax];
int front=-1;
int rear=-1;


/*-----------------------------------------------------------------------------------------------*/
/*建立邻接顶点至邻接列表内                                                                       */
/*-----------------------------------------------------------------------------------------------*/

void creat_graph(int vertex1,int  vertex2)   
{
graph pointer,new1;                                      /*节点和新顶点声明*/
new1 =(graph)malloc(sizeof(struct node));                   /*配置内存*/
if(new1)                                                 /*配置成功*/
{
new1->vertex=vertex2;                                   /*邻近顶点*/
new1->next=0;                                             /*下一个邻接顶点指针*/
pointer=&(head[vertex1]);                                 /*pointer指针设为顶点数组之首节点*/
while (pointer->next)      
pointer=pointer->next;                                   /*往下一个节点*/
pointer->next=new1;}                                        /*串连在链接尾端*/
}

/*-----------------------------------------------------------------------------------------------*/
/*输出邻接列表内数据                                                                             */
/*-----------------------------------------------------------------------------------------------*/
void print_graph(struct node *head)        
{
	graph pointer;                                       /*节点声明*/
	pointer=head->next;
while(pointer)                                          /*当节点为0结束循环*/
{
	printf("[%d]",pointer->vertex);
	pointer=pointer->next;
}
printf("\n");
}



/*-----------------------------------------------------------------------------------------------*/
/*深度优先搜索法                                                                                 */
/*-----------------------------------------------------------------------------------------------*/
void DFS(int vertex)                           
{
	graph pointer;                                      /*节点声明*/
	visited[vertex]=1;                                  /*已查找 */
	printf("[%d]==>",vertex);
	pointer=head[vertex].next;
	while(pointer)
	{
		if(visited[pointer->vertex]==0)
			DFS(pointer->vertex);                            /*递归调用*/
		pointer=pointer->next ;                               /*下一个邻接点*/
	}
}



/*-----------------------------------------------------------------------------------------------*/
/*广度优先搜索法                                                                                 */
/*-----------------------------------------------------------------------------------------------*/
void BFS(int vertex)
{    
	graph pointer;                                          /*节点声明*/
	queue[++rear]=vertex;                                   /*存入队列*/
	visited[vertex]=1;                                        /*已查找*/
	printf("[%d]==>",vertex);
	while (front!=rear)                                      /*队列为空时，结束循环*/
	{
		vertex=queue[++front];
		pointer=head[vertex].next ;
		while(pointer)                                      /*读入邻接列表所有顶点*/
		{
			if(visited[pointer->vertex]==0)   
			{
				queue[++rear]=pointer->vertex;                   /*存入队列*/
				visited[pointer->vertex]=1;                     /*已查找过的顶点*/
				printf("[%d]==>",pointer->vertex);
			}
			pointer=pointer->next;                          /*下一个邻接点*/
			
		}
	}
}





menu()
{   int i,n;
    
printf("\n\n*******************\n");	
printf("1 图的深度优先遍历\n");
printf("2 图的广度优先遍历\n");
printf("3 exit!\n");
printf("*******************\n");
printf("请输入操作：");
scanf("%d",&n);
return n;
}


void main()
{
	int source,n=10;                                         /*起始顶点*/
	int d,i,j;                                         /*终止顶点*/
	int node[20][2]={{1,2},{2,1},{1,3},{3,1},{2,4},{4,2}
	                ,{2,5},{5,2},{3,6},{6,3},{3,7},{7,3},
					{4,8},{8,4},{5,8},{8,5},{6,8},{8,6},{7,8},{8,7}};
					printf("请输入要输入边的个数：");
					scanf("%d",&d);
					printf("请输入各条边的起始定点和终止顶点:\n");
					for(i=0;i<d;i++)
						scanf("%d%d",&node[i][0],&node[i][1]);
	for(i=0;i<vertexnum;i++)
	{
		head[i].vertex=i;
		head[i].next=0;
	}
	
	for(i=0;i<d;i++)
	creat_graph(node[i][0],node[i][1]);
	printf("-----------------Program Description----------------\n");
    printf("图的基本操作                                        \n");
    printf("李南宁     03级计算机科学与技术 3班   2003374313    \n");
    printf("----------------------------------------------------\n");
	while(n!=3)
	{  for(i=0;i<vertexnum;i++)
	   visited[i]=0;
     n=menu();
	switch(n)
	{  
case 1:
		printf("##graph##\n");

		for(i=0;i<vertexnum;i++)
		{	printf("vertex[%d]:",i);
		 print_graph(&head[i]);                                  /*输出邻接列表数据*/
		}
	printf("Depth-First-Search:\n");
		printf("[BEGIN]==>");
		DFS(1);
		printf("END");	break;
case 2:
		printf("##graph##\n");

		for(i=0;i<vertexnum;i++)
		{	printf("vertex[%d]:",i);
		 print_graph(&head[i]);                                  /*输出邻接列表数据*/
		}
	printf("Bepth-First-Search:\n");
		printf("[BEGIN]==>");
		BFS(4);
		printf("END");break;
}

	}
}