1. 首页
  2. 文章中心
  3. 算法

图的最小生成树算法实现（Prim + Kruskal）

131 阅读 0 评论
我是靠谱客的博主 幽默小笼包，这篇文章主要介绍图的最小生成树算法实现（Prim + Kruskal），现在分享给大家，希望可以做个参考。

1、采用书上第 161 页定义的图的邻接矩阵存储表示，编程实现构造最小生成树的 Prim 算法。

2、采用书上第 161 页定义的图的邻接矩阵存储表示，编程实现构造最小生成树的 Kruskal 算法。

例题一（Prim 算法实现）：

复制代码
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef int Status;
typedef int VRType;
typedef int infoType;
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef struct ArcCell
{
	VRType adj;
	infoType* info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef char VertexType;
typedef struct
{
	VertexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum, arcnum;
	GraphKind kind;
}MGraph;

typedef struct {
	VertexType adjvex;
	VRType lowcost;
}Closedge[MAX_VERTEX_NUM];

int LocateVex(MGraph G, char v)
{
	int i;
	for (int i = 0; i < G.vexnum; i++)
		if (G.vexs[i] == v)	return i;
	return -1;
}
Status CreateDG(MGraph& G)
{
	int i, j, k;
	VertexType v1, v2;
	printf("输入顶点数G.vexnum: ");		scanf("%d", &G.vexnum);
	printf("输入边数G.arcnum: ");		scanf("%d", &G.arcnum);
	getchar();
	for (i = 0; i < G.vexnum; i++)
	{
		printf("输入顶点G.vexs[%d]:", i);
		scanf("%c", &G.vexs[i]);
		getchar();
	}
	for (i = 0; i < G.vexnum; i++)
		for (j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j].adj = 0;
			G.arcs[i][j].info = NULL;
		}
	for (k = 0; k < G.arcnum; k++)
	{
		printf("输入第%d条边vi、vj:n", k + 1);
		scanf("%c %c", &v1, &v2);
		getchar();
		i = LocateVex(G, v1);	j = LocateVex(G, v2);
		G.arcs[i][j].adj = 1;
	}
	return OK;
}
Status CreateUDG(MGraph& G)
{
	int i, j, k;
	VertexType v1, v2;
	printf("输入顶点数G.vexnum: ");		scanf("%d", &G.vexnum);
	printf("输入边数G.arcnum: ");		scanf("%d", &G.arcnum);
	getchar();
	for (i = 0; i < G.vexnum; i++)
	{
		printf("输入顶点G.vexs[%d]:", i);
		scanf("%c", &G.vexs[i]);
		getchar();
	}
	for (i = 0; i < G.vexnum; i++)
		for (j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j].adj = 0;
			G.arcs[i][j].info = NULL;
		}
	for (k = 0; k < G.arcnum; k++)
	{
		printf("输入第%d条边vi、vj:n", k + 1);
		scanf("%c %c", &v1, &v2);
		getchar();
		i = LocateVex(G, v1);	j = LocateVex(G, v2);
		G.arcs[i][j].adj = 1;
		G.arcs[j][i].adj = G.arcs[i][j].adj;
	}
	return OK;
}
Status CreateUDN(MGraph& G)
{
	int i, j, k, w;
	VertexType v1, v2;
	printf("输入顶点数G.vexnum: ");		scanf("%d", &G.vexnum);
	printf("输入边数G.arcnum: ");		scanf("%d", &G.arcnum);
	getchar();
	for (i = 0; i < G.vexnum; i++)
	{
		printf("输入顶点G.vexs[%d]:",i);
		scanf("%c", &G.vexs[i]);
		getchar();
	}
	for(i=0;i<G.vexnum;i++)
		for (j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j].adj = INFINITY;
			G.arcs[i][j].info = NULL;
		}
	for (k = 0; k < G.arcnum; k++)
	{
		printf("输入第%d条边vi、vj和权值w(int):n", k + 1);
		scanf("%c %c %d", &v1, &v2, &w);
		getchar();
		i = LocateVex(G, v1);	j = LocateVex(G, v2);
		G.arcs[i][j].adj = w;
		G.arcs[j][i].adj = G.arcs[i][j].adj;
	}
	return OK;
}
Status CreateDN(MGraph& G)
{
	int i, j, k, w;
	VertexType v1, v2;
	printf("输入顶点数G.vexnum: ");		scanf("%d", &G.vexnum);
	printf("输入边数G.arcnum: ");		scanf("%d", &G.arcnum);
	getchar();
	for (i = 0; i < G.vexnum; i++)
	{
		printf("输入顶点G.vexs[%d]:", i);
		scanf("%c", &G.vexs[i]);
		getchar();
	}
	for (i = 0; i < G.vexnum; i++)
		for (j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j].adj = INFINITY;
			G.arcs[i][j].info = NULL;
		}
	for (k = 0; k < G.arcnum; k++)
	{
		printf("输入第%d条边vi、vj和权值w(int):n", k + 1);
		scanf("%c %c %d", &v1, &v2, &w);
		getchar();
		i = LocateVex(G, v1);	j = LocateVex(G, v2);
		G.arcs[i][j].adj = w;
	}
	return OK;
}
Status CreateGraph(MGraph& G)
{
	printf("请输入图的种类：0表示DG，1表示DN，2表示UDG，3表示UDNn");
	scanf("%d", &G.kind);
	switch (G.kind)
	{
	case DG:return CreateDG(G);
	case DN:return CreateDN(G);
	case UDG:return CreateUDG(G);
	case UDN:return CreateUDN(G);
	default:return ERROR;
	}
}
void list(MGraph G)
{
	int i, j;
	printf("输出邻接矩阵：n");
	for (i = 0; i < G.vexnum; i++)
	{
		printf("%c----", G.vexs[i]);
		for (j = 0; j < G.vexnum; j++)
			if (G.arcs[i][j].adj == INFINITY)
				{printf("%4s", "∞"); }
			else
				printf("%4d", G.arcs[i][j].adj);
		printf("n");
	}
}
Status minimum(MGraph G,Closedge closedge)
{
	int i, j;
	double k = 1000;
	for (i = 0; i < G.vexnum; i++)
	{
		if (closedge[i].lowcost != 0 && closedge[i].lowcost < k)
		{
			k = closedge[i].lowcost;
			j = i;
		}
	}
	return j;
}

void MiniSpanTree_PRIM(MGraph G, VertexType u) {
	int i, j,k;
	Closedge closedge;
	k = LocateVex(G, u);
	for (j = 0; j < G.vexnum; ++j)
		if (j != k) closedge[j] = { u,G.arcs[k][j].adj };
	closedge[k].lowcost = 0;
	for (i = 1; i < G.vexnum; ++i)
	{
		k = minimum(G,closedge);
		printf("%c%c ",closedge[k].adjvex, G.vexs[k]);
		closedge[k].lowcost = 0;
		for (j = 0; j < G.vexnum;++j) 
			if (G.arcs[k][j].adj < closedge[j].lowcost)
				closedge[j] = { G.vexs[k],G.arcs[k][j].adj };
		}
	}
	
int main()
{
    MGraph G;
	CreateGraph(G);
	list(G);
	printf("输出最小生成树：n");
    MiniSpanTree_PRIM(G, 'A');
    printf("n");
}

例题二（Kruskal 算法实现）：

复制代码
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
104
105
106
107
108
109
110
111
112
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef int Status;
typedef int VRType;
typedef int infoType;
typedef char VertexType;
typedef struct ArcCell
{
	VRType adj;
	VertexType start, finish;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM];
typedef struct
{
	VertexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum, arcnum;
}MGraph;
int LocateVex(MGraph G, char v)
{
	int i;
	for (int i = 0; i < G.vexnum; i++)
		if (G.vexs[i] == v)	return i;
	return -1;
}
Status CreateGraph(MGraph& G)
{
	int i, j, k, w;
	VertexType v1, v2;
	printf("输入顶点数G.vexnum: ");		scanf("%d", &G.vexnum);
	printf("输入边数G.arcnum: ");		scanf("%d", &G.arcnum);
	getchar();
	for (i = 0; i < G.vexnum; i++)
	{
		printf("输入顶点G.vexs[%d]:", i);
		scanf("%c", &G.vexs[i]);
		getchar();
	}
	for (k = 0; k < G.arcnum; k++)
	{
		printf("输入第%d条边vi、vj和权值w(int):n", k + 1);
		scanf("%c %c %d", &v1, &v2, &w);
		getchar();
		G.arcs[k].start = v1;	G.arcs[k].finish = v2;
		G.arcs[k].adj = w;
	}
	for (i = 0; i < G.arcnum-1; i++)
	{
		for (j = i + 1; j < G.arcnum; j++)
		{
			ArcCell Temp;
			if (G.arcs[i].adj > G.arcs[j].adj)
			{
				Temp = G.arcs[i];	G.arcs[i] = G.arcs[j];	G.arcs[j] = Temp;
			}
		}
	}
	return OK;
}
Status FindStuation(int partern[], int e)
{
	while (partern[e] != 0)
	{
		e = partern[e];
	}
	return e;
}
Status FinishFind(MGraph& G, int partern[])
{
	int i, num = 0;
	for (i = 0; i < G.vexnum; i++)
	{
		if (partern[i])	num++;
	}
	if (num == G.vexnum - 1)	return OK;
	return FALSE;
}
Status MiniSpanTree_Kruskal(MGraph& G)
{
	int i, sit, hit;
	int partern[MAX_VERTEX_NUM];
	for (i = 0; i < G.vexnum; i++)
	{
		partern[i] = 0;
	}
	for (i = 0; i < G.arcnum; i++)
	{
		sit = FindStuation(partern,LocateVex(G,G.arcs[i].start));
		hit = FindStuation(partern,LocateVex(G,G.arcs[i].finish));
		if (sit != hit)
		{
			partern[sit] = hit;
			printf("%c%c ", G.arcs[i].start, G.arcs[i].finish);
		}
		if(FinishFind(G,partern))	return OK;
	}
}
int main()
{
	MGraph G;
	CreateGraph(G);
	printf("输出最小生成树：n");
	MiniSpanTree_Kruskal(G);
	printf("n");
}

最后

以上就是幽默小笼包最近收集整理的关于图的最小生成树算法实现（Prim + Kruskal）的全部内容，更多相关图的最小生成树算法实现（Prim内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(87)

相关文章

如何暴力解决弱N皇后问题（比较sb的做法）
如何暴力解决弱N皇后问题（比较sb的做法）
Python如何实现穷举搜索?
Python如何实现穷举搜索?
穷举，百鸡问题
穷举，百鸡问题
算法系列之一 ：Google方程式
算法系列之一 ：Google方程式
图的最小生成树算法实现（Prim + Kruskal）
图的最小生成树算法实现（Prim + Kruskal）
【算法设计与分析】最小生成树最小生成树 Minimum Spanning Tree
【算法设计与分析】最小生成树最小生成树 Minimum Spanning Tree
最小生成树的Prim算法和Kruskal算法--Java
最小生成树的Prim算法和Kruskal算法--Java
输入一个任意整形数并进行反转（java）
输入一个任意整形数并进行反转（java）

评论列表共有 0 条评论

立即
投稿
返回
顶部