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

这篇具有很好参考价值的文章主要介绍了(深度/广度优先算法)——遍历邻接表(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;
				}
			}
		}
	}
}

二、运行结果

深度优先遍历邻接表,数据结构,算法,宽度优先,图论,链表,深度优先遍历文章来源地址https://www.toymoban.com/news/detail-751639.html

到了这里,关于(深度/广度优先算法)——遍历邻接表(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包