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

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

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

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

5

6

abcde

0 1 1

0 2 1

0 3 1

2 3 1

2 4 1

1 4 1

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

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

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

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

实现代码如下：

#include <stdio.h> #define MAX_GRAPH 100 #define MAX_QUEUE 30 typedef struct { char vex[MAX_GRAPH]; /* 顶点 */ int edge[MAX_GRAPH][MAX_GRAPH]; /* 邻接矩阵 */ int n; /* 当前的顶点数 */ int e; /* 当前的边数 */ }GRAPH; void Create(GRAPH *G); /* 图的邻接矩阵表示法 */ void BFS(GRAPH *G,int k); /* 广度优先遍历 */ void DFS(GRAPH *G,int k); /* 深度优先遍历 */ int visited[MAX_GRAPH]; int main(int argc, char *argv[]) { int i; for(i = 0 ; i < MAX_QUEUE ; ++i) visited[i] = 0; GRAPH G; Create(&G); /* BFS(&G,0);*/ DFS(&G,0); return 0; } void BFS(GRAPH *G,int k) { int queue[MAX_QUEUE]; /* 队列 */ int front = -1,rear = -1,amount = 0; int visited[MAX_GRAPH]; /* 标记已经访问过的元素 */ int i,j; for(i = 0 ; i < MAX_GRAPH ; ++i) visited[i] = 0; printf("访问顶点%cn",G->vex[k]); visited[k] = 1; rear = (rear + 1) % MAX_QUEUE; /* 入队操作 */ queue[rear] = k; front = rear; ++amount; while(amount > 0) { i = queue[front]; /* 出队操作 */ front = (front + 1) % MAX_QUEUE; --amount; for(j = 0 ; j < G->n ; ++j) { if(G->edge[i][j] != 0 && visited[j] == 0) { printf("访问顶点%cn",G->vex[j]); visited[j] = 1; rear = (rear + 1) % MAX_QUEUE; /* 入队 */ queue[rear] = j; ++amount; } } } printf("遍历结束n"); } void DFS(GRAPH *G,int k) { int j; printf("访问顶点：%cn",G->vex[k]); visited[k] = 1; for(j = 0 ; j < G->n ; ++j) { if(G->edge[k][j] != 0 && visited[j] == 0) DFS(G,j); } } void Create(GRAPH *G) { printf("输入顶点数：n"); scanf("%d",&G->n); printf("输入边数：n"); scanf("%d",&G->e); getchar(); int i,j,k,w; printf("请输入端点(char型)：n"); for(i = 0 ; i < G->n ; ++i) /* 建立表头 */ scanf("%c",&G->vex[i]); for(i = 0 ; i < G->n ; ++i) /* 初始化邻接矩阵 */ for(j = 0 ; j < G->n ; ++j) G->edge[i][j] = 0; printf("请输入边：n"); for(k = 0 ; k < G->e ; ++k) { scanf("%d%d%d",&i,&j,&w); /* 输入(vi,vj)上的权w */ G->edge[i][j] = w; G->edge[j][i] = w; } }

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