(深度/广度优先算法)——遍历邻接表(C语言)

一、算法代码

//采用邻接表表示图的遍历
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 100
typedef int VerTexType;
int visited[MAXSIZE];			//访问数组
typedef struct ArcNode{			//边结点
	int adjvex;					//结点位置
	ArcNode *nextarc;			//指向下一结点的指针
}ArcNode;
typedef struct VNode{			//头结点
	VerTexType data;			//顶点信息
	ArcNode *firstarc;			//指向第一条依附该顶点的边的指针
}Vnode;
typedef struct{
	Vnode verxs[MAXSIZE];		//顶点表
	int numNodes,numEdqes;		//顶点数和边数
}AGraph;
AGraph* CreatAGraph();
void DFSTraverse(AGraph G);		//深度优先遍历
void BFSTraverse(AGraph G);		//广度优先遍历
int main(){
	AGraph * G;
	printf("\n---采用邻接表表示图的遍历---\n\n");
	G=CreatAGraph();
	printf("\n-----------邻接表深度优先搜索遍历序列---------------\n\n");
	DFSTraverse(*G);
	printf("\n-----------邻接表广度优先搜索遍历序列---------------\n\n");
	BFSTraverse(*G);
	printf("\n\n");
	system("pause");
	return 0;
}


//--------------------------链队列定义-------------------------------------------------
//链队列的结构
typedef int QElemType;

typedef struct QNode{ //结点结构
	QElemType  data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct{ //队列的链表结构
QueuePtr front,rear;//队头、队尾指针
}LinkQueue;
int initQueue(LinkQueue *q){
	q->front=q->rear=(QueuePtr)malloc(sizeof(QNode));
	if(!q->front)
		return 0;
	q->front->next = NULL;
	return 1;
}
int EnQueue(LinkQueue *q,QElemType e){
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
	if(!s) return 0;
	s->data=e;
	s->next=NULL;
	q->rear->next=s;
	q->rear=s;
	return 1;
}
int DeQueue(LinkQueue *q,QElemType *e){
	QueuePtr p;
	if(q->front==q->rear) return 0;
	p=q->front->next;
	*e=p->data;
	q->front->next=p->next;
	if(q->rear==p) q->rear=q->front;
	free(p);
	return 1;
}
int QueueEmpty(LinkQueue q){
	if(q.front == q.rear) return 1;
	return 0;
}
//--------------------------创建图-------------------------------------------------
int LocateVex(AGraph *G,int v1){
	for(int i=0;i<G->numNodes;i++){
		if(G->verxs[i].data==v1) return i;
	}
	return 0;
}
AGraph* CreatAGraph(){
	AGraph *G=(AGraph*)malloc(sizeof(AGraph));		
	printf("请输入要创建图的顶点数和边数：(空格间隔)\n");
	scanf("%d %d", &G->numNodes, &G->numEdqes);		//输入总顶点数，总边数
	getchar();
	printf("请输入%d个顶点的值：(空格间隔)\n",G->numNodes);
	for(int i=0;i<G->numNodes;i++){					//输入各点，构造表头结点表
		scanf("%d",&G->verxs[i].data);				//输入顶点值
		G->verxs[i].firstarc=NULL;					//初始化表头结点的指针域
	}
	printf("请输入弧尾和弧头：(空格间隔)\n");
	for(int k=0;k<G->numEdqes;++k){					//输入各边，构造邻接表
		int v1,v2,i,j;
		scanf("%d %d",&v1,&v2);						//输入一条边依附的两个顶点
		i=LocateVex(G,v1);							//两个顶点位置
		j=LocateVex(G,v2);
		ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode));			//生成一个新的边结点*p
		p->adjvex=j;								//邻接点序号为j
		p->nextarc=G->verxs[i].firstarc;
		G->verxs[i].firstarc=p;						//将新结点*p插入顶点verxs[i]的边表头部
		p=(ArcNode*)malloc(sizeof(ArcNode));		//生成另一个对称的新的边结点*p
		p->adjvex=i;								//邻接点序号为i
		p->nextarc=G->verxs[j].firstarc;
		G->verxs[j].firstarc=p;					//将新结点*p插入顶点verxs[j]的边表头部
	}
	return G;
}

//-----------------------------深度优先遍历-----------------------------------------
void DFS(AGraph G,int v){
	ArcNode *p;
	visited[v]=1;
	printf("%d ",G.verxs[v].data);
	p=G.verxs[v].firstarc;
	while(p!=NULL){
		if(visited[p->adjvex]==0){
			DFS(G,p->adjvex);
		}
		p=p->nextarc;	
	}
} 
void DFSTraverse(AGraph G){
	for(int i=0;i<G.numNodes;i++)
		visited[i]=0;	//初始化所有结点为未访问
	for(int i=0;i<G.numNodes;i++)
		if(!visited[i]) DFS(G,i);
}
//-----------------------------广度优先遍历----------------------------------------

void BFSTraverse(AGraph G){
	LinkQueue q;							//初始化队列q
	initQueue(&q);							//初始化标志数组
	for (int i=0;i<G.numNodes;i++) visited[i] = 0;
	for (int i=0; i<G.numNodes;i++){
		if (visited[i]==0){
			visited[i]=1;
			printf("%d ",G.verxs[i].data);
			EnQueue(&q,i);					//将下标i入队列
			while(!QueueEmpty(q)){
				int index;
				DeQueue(&q,&index);			//出队列
				//边表结点指针s用来遍历边表
				ArcNode* s=G.verxs[index].firstarc;
				while(s!=NULL){
					if(visited[s->adjvex]==0){
						visited[s->adjvex]=1;
						printf("%d ",G.verxs[s->adjvex].data);
						EnQueue(&q,s->adjvex);
					}
					s=s->nextarc;
				}
			}
		}
	}
}

二、运行结果