无向图的深度优先遍历

无向图的深度优先遍历

输入：图的顶点及边的数目、每条边依附的顶点

输出：以任意一点为起点，进行广度优先遍历的结果。

#include"stdio.h"#include"stdlib.h"#include"conio.h"#define MAXADJSIZE 20int visited[MAXADJSIZE];//图的  邻接表  储存方式typedefstruct ArcNode{struct ArcNode*nextarc;//下一个弧int adjvex;//所在定点}ArcNode;typedefstruct VNode{struct ArcNode*firstarc;//指向第一个弧int data;//顶点信息}VNode,AdjList[MAXADJSIZE];typedefstruct{
	AdjList vex;int vexnum,arcnum;}Graph;//队列的链式储存   用于广度优先的遍历typedefstruct QNode{int v;struct QNode*next;}QNode,*Qptr;typedefstruct{
  	Qptr front;
  	Qptr rear;}LinkQ;voidInitQueue(LinkQ&Q){if(!(Q.front=Q.rear=(Qptr)malloc(sizeof(QNode)*MAXADJSIZE)))printf("储存分配失败！！！\n");else{
		Q.front->next=NULL;}}voidEnQueue(LinkQ&Q,int e){
	Qptr p;if(!(p=(Qptr)malloc(sizeof(QNode))))printf("储存分配失败！！！\n");else{
	p->v=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;}}voidDeQueue(LinkQ&Q,int&e){if(Q.rear==Q.front)printf("此队列为空！！！\n");else{
	Qptr p;if(!(p=(Qptr)malloc(sizeof(QNode))))printf("储存分配失败！！！\n");else{
    p=Q.front->next;
	e=p->v;
	Q.front->next=p->next;if(Q.rear==p) Q.rear=Q.front;//当队列中的最后一个元素被删除的时候，rear会丢失，应该对其重新赋值free(p);}}}intEmptyQueue(LinkQ Q){if(Q.front==Q.rear)return1;elsereturn0;}voidVISIT(int v){printf("v%d  ",v+1);}//与节点v相接的第一个边intFirstAdjVex(Graph G,int v){return G.vex[v].firstarc->adjvex;}// 与节点v相接的下一个边intNextAdjVex(Graph G,int v,int w){   ArcNode*p;if(!(p=(ArcNode*)malloc(sizeof(ArcNode))))printf("储存分配失败！！！\n");
	p=G.vex[v].firstarc;while(p->adjvex!=w&&p->nextarc!=NULL)	
	  p=p->nextarc;if(p->nextarc==NULL)return-5;else{	
	  p=p->nextarc;	
	  w=p->adjvex;return w;}}voidBFSTraverse(Graph G){//图的广度优先遍历int v,u; 	
	LinkQ Q;for(v=0;v<G.vexnum;++v) 
	  visited[v]=0;InitQueue(Q);for(v=0;v<G.vexnum;++v){printf("以点v%d为起点的结果：",v+1);if(!visited[v]){VISIT(v);visited[v]=1;EnQueue(Q,v);while(!EmptyQueue(Q)){DeQueue(Q,u);for(int w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))if(!visited[w]){VISIT(w);
		    visited[w]=1;EnQueue(Q,w);}}}for(int i=0;i<G.vexnum;++i) 
	  visited[i]=0;InitQueue(Q);printf("\n");}}voidcreat(Graph&G)//创建存储图的邻接表{int j,i;	
	ArcNode*s,*t,*p;int v1,v2;printf("输入无向图顶点数目和无向图边数：\n");scanf("%d%d",&G.vexnum,&G.arcnum);for(i=0;i<G.vexnum;i++){	
	  G.vex[i].data=i;
  	  G.vex[i].firstarc=NULL;}for(int k=0;k<G.arcnum;k++){printf("请输入第%d条边依附的两个顶点：\n",k+1);scanf("%d %d",&v1,&v2);	
		v1--;
		v2--;
		s=(ArcNode*)malloc(sizeof(ArcNode));
		t=(ArcNode*)malloc(sizeof(ArcNode));
		s->adjvex=v1;	
		s->nextarc=G.vex[v2].firstarc;
		G.vex[v2].firstarc=s;	
		t->adjvex=v2;
		t->nextarc=G.vex[v1].firstarc;	
		G.vex[v1].firstarc=t;}}voidPrint(Graph&G){
	ArcNode*p;printf("%4s %6s %12s\n","编号","顶点","相邻边编号");for(int i=0;i<G.vexnum;i++){printf("%4d     v%d",i,G.vex[i].data+1);for(p=G.vex[i].firstarc;p;p=p->nextarc)printf("%4d",p->adjvex);printf("\n");}}intmain(){
	Graph G;creat(G);//	Print(G);BFSTraverse(G);return0;}