图 ADT接口遍历运算常规运算邻接矩阵实现

60 阅读 0 评论 40 点赞

我是靠谱客的博主冷静飞机，最近开发中收集的这篇文章主要介绍图 ADT接口遍历运算常规运算邻接矩阵实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Graph.h (图的结构, 遍历, 常规操作接口)

 1 /*定义图的最大定点数, 它要大于等于具体图的顶点树n*/
 2 #define MaxVertexNum 12
 3
 4 /*定义图的最大边数,它要大于等于具体图的边数e*/
 5 #define MaxEdgeNum 20
 6
 7 /* 定义MaxValue 为一个符号常量,其值要大于邻接矩阵中所有有效值之和*/
 8 #define MaxValue 1000
 9
10 /*定义MS为一个符号常量,用于广度优先搜索遍历的算法中,作为自定义顺序队列的数组长度*/
11 #define MS 20
12
13 /*定义图中顶点数据的类型VertexType为整型*/
14 typedef int VertextType;
15
16 /*定义vexlist为存储顶点信息的数组类型*/
17 typedef VertexType vexlist[MaxVertexNum];
18
19 /*定义adjmatrix 为存储邻接矩阵的数组类型*/
20 typedef int adjmatrix[MaxVertexNum][MaxVertexNum];
21
22 /*定义保存图顶点访问标记的数组*/
23 int visited[MaxVertexNum];
24
25
26
27 /*通过从键盘上输入的n个顶点信息和e条无向带权边的信息建立顶点数组GV和邻接矩阵GA*/
28 void Create1(vexlist GV, adjmatrix GA, int n, int e);
29
30 /*从初始点Vi出发深度优先搜索由邻接矩阵GA表示的图*/
31 void dfs1(adjmatrix GA, int i, int n);
32
33 /*从初始点Vi出发广度优先搜索由邻接矩阵GA表示的图*/
34 void bfs1(adjmatrix GA, int i, int n);

Graph.c (图的接口实现)

 1 void Create1(vexlist GV, adjmatrix GA, int n, int e){
 2 /*通过从键盘上输入的n个顶点信息和e条无向带权边的信息建立顶点数组GV和邻接矩阵GA*/
 3
int i,j,k,w;
 4
/*建立顶点数组*/
 5
printf("输入%d个顶点数据n", n);
 6
for(i = 0; i<n; i++) scanf("%d", &GV[i]);
 7
/*初始化邻接矩阵数组*/
 8
for(i = 0; i<n; i++)
 9
for(j = 0; j<n; j++){
10
if(i == j)GA[i][j] = 0;
11
else GA[i][j] = MaxValue;
12 
}
13
/*建立邻接矩阵数组*/
14
printf("输入%d条无向带权边n", e);
15
for(k = 1; k<=e; k++){
16
/*输入一条边的两端点序号i和j及边上的权w*/
17
scanf("%d %d %d", &i, &j, &w);
18
/*置数组中相应对称元素的值为w*/
19
GA[i][j] = GA[j][i] = w;
20 
}
21
22 }
23
24
25 void dfs1(adjmatrix GA, int i, int n){
26 /*从初始点Vi出发深度优先搜索由邻接矩阵GA表示的图*/
27
int j;
28
/*假定访问顶点Vi以输出该顶点的序号代之*/
29
printf("%d",i);
30
/*标记Vi已被访问过*/
31
visited[i] = 1;
32
/*依次搜索Vi的每个邻接点*/
33
for(j = 0; j<n; j++)
34
/*若Vi的一个有效邻接点Vj未被访问过,则从Vj出发进行递归调用*/
35
if(GA[i][j]!=0 && GA[i][j]!=MaxValue && !visited[j])
36 
dfs1(GA, j, n);
37 }
38
39
40 void bfs1(adjmatrix GA, int i, int n){
41 /*从初始点Vi出发广度优先搜索由邻接矩阵GA表示的图*/
42
/*定义一个顺序队列Q,其元素类型应为整形,初始化队列为空*/
43
int Q[MS];
//MS是一个事先定义的符号常量
44
int front = 0,rear = 0;
45
/*访问初始点Vi,同时标记初始点Vi已访问过*/
46
printf("%d" ,i);
47
visited[i] = 1;
48
/*将已访问过的初始点序号i入队*/
49
rear = (rear+1)%MS;
50
if(front == rear) {
51
printf("队列空间用完!n");
52
exit(1);
53 
}
54
Q[[rear] = i;
55
56
/*当队列非空时进行循环处理*/
57
while(front != rear){
58
int j,k;
59
/*删除队首元素,第一次执行时k的值为i*/
60
front = (front + 1)%MS;
61
k = Q[front];
62
/*依次搜索Vk的每一个可能的邻接点*/
63
for(j = 0; j<n; j++){
64
if(GA[k][j]!=0 && GA[k][j] != MaxValue&&!visited[j]){
65
printf("%d", j);
//访问一个未被访问过的邻接节点Vj
66
visited[j] = 1;
//标记Vj已被访问过
67
rear = (rear+1)%MS;
//修改队尾指针
68
if(front == rear) {
69
printf("队列空间用完!n");
70
exit(1);
71 
}
72
Q[rear] = j;
73 
}
74 
}
75
76 
}
77 }
78