用邻接表形式存储图并且按广度优先搜索打印遍历结果
#include<stdio.h>#define MAX_VERTEX_NUM 20//最多顶点个数 #define ERROR -1typedef char VertexData;//边表节点类型定义 typedef struct ArcNode{int adj;//该弧指向顶点的位置 struct ArcNode *nextarc;//指向下一条弧的指针 }ArcNode;//表头节点类型定义 typedef struct VertexNode{VertexData data;ArcNode *firstarc;//指向该顶点第一条弧的指针； }VertexNode;typedef struct{VertexNode vertex[MAX_VERTEX_NUM];int vexnum,arcnum;}AdjList;void CreateGraph(AdjList *G){printf("请输入图的顶点数和弧数（最多不超过20）：");scanf("%d %d",&G->vexnum,&G->arcnum);printf("请输入顶点:");int i,j,k;for(i=1;i<G->vexnum+1;i++)//表头结点下标从1开始 {fflush(stdin);scanf("%c",&(G->vertex[i].data)); G->vertex[i].firstarc=NULL;}printf("请输入一条弧的两个顶点的序号（例如1 2）:\n");for(k=1;k<G->vexnum+1;k++){fflush(stdin);scanf("%d %d",&i,&j);ArcNode *p,*q;p=(ArcNode*)malloc(sizeof(ArcNode));q=(ArcNode*)malloc(sizeof(ArcNode));//头插法 p->adj=j;p->nextarc=G->vertex[i].firstarc;G->vertex[i].firstarc=p;//头插法 q->adj=i;q->nextarc=G->vertex[j].firstarc;G->vertex[j].firstarc=q;}}void print(AdjList *G)//将建图结果打印在屏幕上{int i,j;for(i=1;i<(G->vexnum+1);i++){printf("%c ",G->vertex[i].data);ArcNode *p;p=G->vertex[i].firstarc;while(p!=NULL){printf("%d ",p->adj);p=p->nextarc;}printf("\n"); }}//队列typedef struct Node{int data;struct Node *next;}LinkQueueNode; typedef struct{LinkQueueNode *front;LinkQueueNode *rear;}LinkQueue;//队列初始化int InitQueue(LinkQueue *Q){Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(Q->front!=NULL){Q->rear=Q->front;Q->front->next=NULL;return(1);}else return(0);} //入队操作int EnterQueue(LinkQueue *Q,int x){LinkQueueNode *NewNode;NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(NewNode!=NULL){NewNode->data=x;NewNode->next=NULL;Q->rear->next=NewNode;Q->rear=NewNode;return(1);}else return(0);}//出队操作DeleteQueue(LinkQueue *Q,int *x){LinkQueueNode *p;if(Q->front==Q->rear)return(0);p=Q->front->next;Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;*x=p->data;free(p);return(1);} void BFS(AdjList G){int i,j;LinkQueue Q;int visited[MAX_VERTEX_NUM];for(i=1;i<G.vexnum+1;i++){visited[i]=0;}InitQueue(&Q);for(i=1;i<G.vexnum+1;i++){if(visited[i]==0)//未访问过该顶点{ArcNode *p;visited[i]=1;printf("%c ",G.vertex[i].data);EnterQueue(&Q,i);//将其入队while(Q.front!=Q.rear)//队列不为空{DeleteQueue(&Q,&i); //将队中元素出队列，赋值给i p=G.vertex[i].firstarc;//p指向出队顶点的第一条边while(p!=NULL){if(visited[p->adj]==0){printf("%c ",G.vertex[p->adj].data);visited[p->adj]=1;EnterQueue(&Q,p->adj);}p=p->nextarc;} } } }} void main(){AdjList G;CreateGraph(&G);print(&G);printf("广度优先遍历的结果为:");BFS(G);}
以这个简单图为例
程序运行结果为
特别注意：
1.为了方便，代码中表头结点数组的下标从1开始，进而以后需要用到vexnum（表头结点个数）的时候需要给其加1
否则会造成最后一个元素无法遍历到的情况
2.广度优先搜索时，借用辅助队列，入队和出队的都是整型数字，也就是该结点的序号（下标），而不是字符
如果觉得《邻接表形式存储图并且按广度优先搜索遍历的C语言实现》对你有帮助，请点赞、收藏，并留下你的观点哦！
