本文实例讲述了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所示
实现代码如下：
?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#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("访问顶点%c\n",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("访问顶点%c\n",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("访问顶点：%c\n",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++程序设计有所帮助。
如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）
发表评论
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。