一、算法代码
//采用邻接表表示图的遍历
#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
文章来源:https://www.toymoban.com/news/detail-751639.html
到了这里,关于(深度/广度优先算法)——遍历邻接表(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!