本文实例讲述了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所示
实现代码如下:
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
|
#include <stdio.h>
#include <malloc.h>
#define MAX_VEX 50
typedef 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++程序设计有所帮助。