图遍历的演示.cpp

编制一个演示在连通无向图上访问全部结点操作的程序

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

#define MAX_VERTEX_NUM 30					//无向图最大顶点数
#define MAX_LEN    20						//数据最大长度

int  visited[MAX_VERTEX_NUM];					//全局变量，访问标志数组
typedef struct EBox{							//边结点类型
	int mark;									//访问标记
	int ivex,jvex;								//该边依附的两个顶点位置
	struct EBox *ilink,*jlink;						//分别指向依附这两个顶点的下一条边
}EBox;
typedef struct VexBox{							//顶点结点类型
	char data[MAX_LEN];
	EBox *fistedge;							//指向第一条依附该顶点的边
}VexBox;
typedef struct{
	VexBox  list[MAX_VERTEX_NUM];
	int vexnum,edgenum;						//无向图当前顶点数和边数
}AMLGraph;
void CreateGraph(AMLGraph *p)
{											//创建无向图
	int i,j,k;
	EBox *q;
	 printf("请输入图的结点个数和边的个数:\n");	//输入图的结点数和边数
	 scanf("%d,%d",&p->vexnum,&p->edgenum);
	 for(i=1;i<=p->vexnum;i++)
	 {    printf("请输入结点%d的名称:\n",i);		//输入顶点数据信息
		 scanf("%s",p->list[i].data);
	     p->list[i].fistedge=NULL;				//初始化指针
	 }
	 printf("请输入互相有关联的两个结点:\n");
	 for(k=0;k<p->edgenum;k++)					//输入各边并构造多重链表
	 {
	 scanf("%d,%d",&i,&j);
	 q=(EBox *)malloc(sizeof(EBox));
	 q->mark=0;								//对边结点赋值
	 q->ivex=i;
	 q->ilink=p->list[i].fistedge;
	 q->jvex=j;
	 q->jlink=p->list[j].fistedge;    
	 p->list[i].fistedge=p->list[j].fistedge=q;   		//完成边在链头的插入
	 }
}
void DFS(AMLGraph *p, int v)
{											//对第v个顶点的深度优先遍历
	int w;
	EBox *q;
	visited[v]=1;
    printf("%s ",p->list[v].data);
	for(q=p->list[v].fistedge;q!=NULL;)
	{if(q->ivex==v) {w=q->jvex; q=q->jlink;}
	 else  {w=q->ivex; q=q->ilink;}
	 if(!visited[w]) DFS(p,w);
	}
}
void DFSTraverse(AMLGraph *p,int n)

{											//深度优先遍历
	int v;
	for(v=1;v<=p->vexnum;v++)
		visited[v]=0;							//访问标志数组初始化
	DFS(p,n);									//对起始顶点调用DFS
	for(v=1;v<=p->vexnum;v++)
		if(!visited[v]) DFS(p,v);			 		//对尚未访问的顶点调用DFS
}
void BFS(AMLGraph *p,int v)
{											//对第v个顶点进行广度优先遍历
	    int u,w;
        EBox *x;
        typedef	struct queue{
		int m;
		struct queue *next;
		}Q;									//辅助队列Q
        Q  *head,*tail,*q;
	    head=tail=(Q *)malloc(sizeof(Q));
	    tail->next=NULL;
	    visited[v]=1;
		printf("%s ",p->list[v].data);
		tail->m=v;							 //v入队列
		tail->next=(Q *)malloc(sizeof(Q));
		tail=tail->next;
		tail->next=NULL;
		while(head!=tail){
			q=head;
			head=head->next;
			u=q->m;							//对头元素出队并置为u
			free(q);
			for(x=p->list[u].fistedge;x!=NULL;)
			{if(x->ivex==u) {w=x->jvex;x=x->ilink;}
			    else {w=x->ivex;x=x->jlink;}   
			if(!visited[w]){
				visited[w]=1;
				printf("%s ",p->list[w].data);
				tail->m=w;     
		        tail=tail->next=(Q *)malloc(sizeof(Q));
		        tail->next=NULL;
			}  //if
			}   //for
		}   //while
}  //BFS
void BFSTraverse(AMLGraph *p,int n)
{											//广度优先遍历
   int v;
	for(v=1;v<=p->vexnum;v++)
		visited[v]=0;							//访问标志数组初始化
	BFS(p,n);									//对起始顶点调用BFS
    for(v=1;v<=p->vexnum;v++)
	if(!visited[v])  BFS(p,v);						//对未访问顶点调用BFS
}		
void main()									//主函数
{  
	int x;
	AMLGraph graph,*p;
	p=&graph;
	CreateGraph(p);							//创建图
	printf("请输入起始遍历结点:\n");
	scanf("%d",&x);
    printf("深度优先遍历结果为:\n");
    DFSTraverse(p,x);							//深度优先遍历
	printf("\n");
	printf("广度优先遍历结果为:\n");
	BFSTraverse(p,x);							//广度优先遍历
	printf("\n");
}