本文实例讲述了C++实现图的邻接表存储和广度优先遍历方法。分享给大家供大家参考。具体如下：

示例：建立如图所示的无向图

由上图知，该图有5个顶点，分别为a,b,c,d,e,有6条边.

示例输入（按照这个格式输入）：

5
6
abcde
0 1
0 2
0 3
2 3
2 4
1 4

输入结束（此行不必输入）

注：0 1表示该图的第0个顶点和第1个定点有边相连，如上图中的a->b所示
0 2表示该图的第0个顶点和第2个定点有边相连，如上图中的a->c所示
2 3表示该图的第2个顶点和第3个定点有边相连，如上图中的c->d所示

实现代码如下：

#include <stdio.h>#include <malloc.h>#define MAX_VEX 50typedef struct NODE{ int ix; struct NODE *next; }EdgeNode; typedef struct{ char vex; EdgeNode *first; }Vertex; typedef struct{ Vertex vex[MAX_VEX]; int n,e;}GRAPH;void Create(GRAPH *G);void BFS(GRAPH *G,int k); int main(int argc, char *argv[]){ GRAPH G; Create(&G); BFS(&G,0); return 0;}void BFS(GRAPH *G,int k){ EdgeNode *p; int queue[MAX_VEX]; int front = -1,rear = -1,amount = 0; int visited[MAX_VEX]; int i,j; for(i = 0 ; i < MAX_VEX ; ++i) visited[i] = 0; printf("访问顶点:%c\n",G->vex[k].vex); visited[k] = 1; rear = (rear + 1) % MAX_VEX; front = 0; queue[rear] = k; ++amount; while(amount > 0) { i = queue[front]; front = (front + 1) % MAX_VEX; --amount; p = G->vex[i].first; while(p) { if(visited[p->ix] == 0) { printf("访问顶点:%c\n",G->vex[p->ix].vex); visited[p->ix] = 1; rear = (rear + 1) % MAX_VEX; queue[rear] = p->ix; ++amount; } p = p->next; } }}void Create(GRAPH *G){ printf("输入顶点数：\n"); scanf("%d",&G->n); printf("输入边数：\n"); scanf("%d",&G->e); getchar(); EdgeNode *p; int i,j,k; for(i = 0 ; i < G->n ; ++i) { scanf("%c",&G->vex[i].vex); G->vex[i].first = NULL; } for(k = 0 ; k < G->e ; ++k) { scanf("%d%d",&i,&j); p = (EdgeNode*)malloc(sizeof(EdgeNode)); p->next = G->vex[i].first; p->ix = j; G->vex[i].first = p; p = (EdgeNode*)malloc(sizeof(EdgeNode)); p->next = G->vex[j].first; p->ix = i; G->vex[j].first = p; }}

希望本文所述对大家的C++程序设计有所帮助。