1 #include<stdio.h>
2 #include<stdlib.h>
3 #define OK 1
4 #define NO 0
5 #define FALSE 0
6 #define TRUE 1
7 #define ERROR -1
8
9 #define INFINITY 200000
10 #define MAX_VERTEX_NUM 20
11
12 typedef
int *
SetType;
13 typedef
int Status;
14 typedef
int VRType;
//图、表顶点关系类型
15 typedef
struct ArcCell
16 {
17 VRType adj;
//权值
18 }ArcCell;
19
20 typedef ArcCell AdjMaxtrix[MAX_VERTEX_NUM+
1][MAX_VERTEX_NUM+
1];
//邻接矩阵
21 typedef
char VertexType_M;
//图的顶点类型
22
23
24 typedef
struct
25 {
26 VertexType_M vexs[MAX_VERTEX_NUM+
1];
//顶点向量
27 AdjMaxtrix arcs;
28 int vexnum,arcnum;
29 }MGraph;
30
31 //作用非常的重要,主要是为了实现记录每一个结点的前一个结点以及它们之间的权重
32 typedef
struct
33 {
34 VertexType_M adjvex;
//较早加入当前边的端点
35 VRType lowcost;
//当前边的权值
36
37 }Edge;
38
39 typedef
struct //定义一个边集用来存储图的所有边信息
40 {
41 int begin,end;
42 int weight;
43 }gEdge;
44
45
46 Status visited[MAX_VERTEX_NUM+
1];
47
48 Status CreateUDN_M(MGraph *
G);
49
50 void OutputMGraph(MGraph G);
51
52 int LocateVex_M(MGraph G,VertexType_M u);
53
54 int MinSpanTree_PRIM(MGraph G,VertexType_M u);
55
56 int Minimum(Edge closedge[],
int n);
57
58 void MinSpanTree_KRUSKAL(MGraph G);
59
60
61 gEdge *CreateEdges(MGraph G);
//生成图的排序过的边集数组
62
63 int main(
int argc,
char**
argv){
64 MGraph G;
65 printf(
"初始化并输出无向网..\n");
66 {
67 CreateUDN_M(&
G);
68
69 OutputMGraph(G);
70 printf(
"\n");
71 }
72 printf(
"函数 MinSpanTree_PRIM 测试..\n");
73 {
74 int total;
75
76 printf(
"普里姆算法..\n");
77 printf(
"先后加入最小生成树的各结点及其对应的最小边的权值分别为： \n");
78 total=MinSpanTree_PRIM(G,
'A');
79 printf(
"\n");
80 printf(
"输出最小生成树的总长度为%d\n",total);
81 printf(
"\n");
82 }
83 printf(
"函数 MinSpanTree_KRUSKAL 测试..\n");
84 {
85 printf(
"克鲁斯卡尔算法..\n");
86 printf(
"最小生成树的各边及其对应的权值分别为：\n");
87 MinSpanTree_KRUSKAL(G);
88 printf(
"\n");
89 }
90
91
92 return 0;
93 }
94 Status CreateUDN_M(MGraph *
G){
95 int i,j,k;
96 VertexType_M v1,v2;
97 VRType w;
98 printf(
"输入顶点数 ");
99 scanf(
"%d",&(G->
vexnum));
100 printf(
"输入弧数 ");
101 scanf(
"%d",&(G->
arcnum));
102 printf(
"输入各个顶点值 ");
103 getchar();
104 for(i=
1;i<=G->vexnum;i++
)
105 {
106 scanf(
"%c",&(G->
vexs[i]));
107 }
108
109 printf(
"初始化邻接矩阵\n");
110 for(i=
1;i<=G->vexnum;i++
)
111 {
112 for(j=
1;j<=G->vexnum;j++
)
113 G->arcs[i][j].adj=
INFINITY;
114 }
115 for(k=
1;k<=G->arcnum;k++
)
116 {
117 getchar();
118 printf(
"输入相邻结点（添加弧的信息）");
119 scanf(
"%c%c%d",&v1,&v2,&
w);
120 i=LocateVex_M(*
G,v1);
121 j=LocateVex_M(*
G,v2);
122
123 G->arcs[i][j].adj=
w;
124 G->arcs[j][i]=G->
arcs[i][j];
125 }
126
127
128 return OK;
129 }
130
131 int LocateVex_M(MGraph G,VertexType_M u)
132 {
133 int i;
134 for(i=
1;i<=G.vexnum;i++
)
135 {
136 if(G.vexs[i]==
u)
137 return i;
138 }
139 return 0;
140
141 }
142
143
144 void OutputMGraph(MGraph G){
145 int i,j;
146 if(!G.vexnum&&!
G.arcnum)
147 printf(
"空图（表）！\n");
148 else
149 {
150 printf(
" ");
151 for(i=
1;i<=G.vexnum;i++
)
152 {
153 printf(
"<",G.vexs[i]);
154 }
155 printf(
"\n");
156 for(i=
1;i<=G.vexnum;i++
)
157 {
158 printf(
"%c",G.vexs[i]);
159 for(j=
1;j<=G.vexnum;j++
)
160 {
161 if(G.arcs[i][j].adj==
INFINITY)
162 printf(
" ∞");
163 else
164 printf(
"=",G.arcs[i][j]);
165 }
166 printf(
"\n");
167
168 }
169 }
170 }
171
172 /*Prim算法：
173 本质上是贪心算法，首先输入一个顶点作为起点，提取这个顶点的序号，然后有一个closedge数组来初始化，遍历之后将每个顶点的
174 前一个访问的结点初始化为u,并且将他们之间的弧的权重直接当成二者之间的权重。然后首先输出一个u.Minmum这个函数主要是用来
175 求出所有的边中和u相连的弧的权重最小的顶点值(第一个循环的时候),然后输出这个最小的权值以及顶点。并且将这个顶点的标记为
176 lowcast=0；在后面的访问中就不会用到这个顶点。之后由于这个时候已知的顶点是两个，因此对于所有和第二个结点中连接弧长最小
177 的顶点，需要改变弧的权值以及前一个顶点的位置。然后第二轮循环进来的时候，同样在Minmum这个函数中实现找出所有哦没有被访问
178 过的权值最小的顶点，这个时候不需要担心会访问非前面两个邻接点，因为如果不是邻接点，它们的弧的权重将是无穷大，因此肯定会
179 访问权值最小的结点。然后循环将每一个结点都输出。*/
180
181 int MinSpanTree_PRIM(MGraph G,VertexType_M u){
182 int i,j,k;
183 int total=
0;
184 Edge closedge[G.vexnum+
1];
185 k=
LocateVex_M(G,u);
186 /*将辅助矩阵初始化使每一个结点都标记为前一个结点是u,并且它们之间的距离是无穷大，若是邻接点那么就是adj的值*/
187 for(j=
1;j<=G.vexnum;j++
)
188 {
189 if(j!=
k)
190 {
191 closedge[j].adjvex=u;
//标记j这个顶点的前一个顶点的信息
192 closedge[j].lowcost=
G.arcs[k][j].adj;
193 }
194 }
195 closedge[k].lowcost=
0;
//自己到自己的cost标记为0
196 printf(
" %c\n", u);
197 for(i=
1;i<=G.vexnum-
1;i++)
//总共需要这么多此找出最小边
198 {
199 k=
Minimum(closedge,G.vexnum);
200 total+=
closedge[k].lowcost;
201 printf(
"-,%c\n",closedge[k].lowcost,G.vexs[k]);
202 closedge[k].lowcost=
0;
203 for(j=
1;j<=G.vexnum;j++
)
204 {
205 if(G.arcs[k][j].adj<
closedge[j].lowcost)
206 {
207 closedge[j].adjvex=
G.vexs[k];
208 closedge[j].lowcost=
G.arcs[k][j].adj;
209 }
210 }
211 }
212 return total;
213 }
214
215 //找到所有和结点邻接的点中权值最小的并且返回j（用来标记最小的值所在的下标）
216 int Minimum(Edge closedge[],
int n){
217 int i,j;
218 int min=
INFINITY;
219 i=
1;
220 j=
0;
221 for(;i<=n;i++
){
222 if(closedge[i].lowcost)
//从权值不为0的边中选择拥有最小权值的边
223 {
224 if(closedge[i].lowcost<=
min)
225 {
226 min=
closedge[i].lowcost;
227 j=
i;
228 }
229 }
230 }
231 return j;
232 }
233
234 gEdge *
CreateEdges(MGraph G){
235 int i,j;
236 int k=
1;
237 int EdgeNum=
G.arcnum;
238 int VertexNum=
G.vexnum;
239 gEdge temp;
240 gEdge *p=(gEdge*)
malloc(
sizeof(gEdge)*VertexNum*VertexNum);
//之前程序报错 是因为申请的空间不够大，越界了
241
242 for(i=
1;i<=VertexNum;i++)
//边集数组初始化
243 for(j=i;j<=VertexNum;j++)
//为了避免无向图的每条边被记录两次，只考虑上三角矩阵
244 if(G.arcs[i][j].adj!=
0&&G.arcs[i][j].adj!=
INFINITY){
245 p[k].begin=
i;
246 p[k].end=
j;
247 p[k].weight=
G.arcs[i][j].adj;
248 k++
;
249 }
250 //首个p[i]与后面i+1……最后个依次比较，每一次都将小的放在第i个
251 for(i=
1;i<EdgeNum;i++)
//对边集数组进行选择排序
252 for(j=i+
1;j<=EdgeNum;j++
)
253 if(p[i].weight>
p[j].weight){
254 // temp.begin=p[i].begin;
255 // temp.end=p[i].end;
256 // temp.weight=p[i].weight;
257
258
259 temp=
p[i];
260 p[i]=
p[j];
261 p[j]=
temp;
262 }
263 return p;
//这个时候返回的p是已经从小到大排好序的，并且拥有一共EdgeNumt个大小的数组
264 }
265
266 void MinSpanTree_KRUSKAL(MGraph G){
267 int VertexNum=
G.vexnum;
268 int EdgeNum=
G.arcnum;
269 gEdge *p=CreateEdges(G);
//边数组
270 int *index=(
int*)
malloc(
sizeof(
int)*
VertexNum);
271 //index 数组，其元素为连通分量的编号，index[i]=index[j]表示编号为i,j的顶点在一个连通分量里
272 int *MSTEdge = (
int *)
malloc(
sizeof(
int)*VertexNum);
//用来存储已经确定的MST的边的编号共VertexNum-1条边
273 int k=
1;
274 int WeightSum=
0;
275 int IndexBegin,IndexEnd;
276 int i,j,n;
277
278
279
280 for(i=
1;i<=VertexNum;i++)
//初始化所有的index=-1;
281 index[i]=-
1;
282
283 for(i=
1;i<VertexNum;i++
)
284 {
285 for(j=
1;j<=EdgeNum;j++
)
286 {
287 if(!(index[p[j].begin]>=
0&&index[p[j].end]>=
0&&index[p[j].begin]==index[p[j].end])){
//找到当前还没有加入到同一个连通分量权值最小的边
288 MSTEdge[i]=j;
//将每一个不同的弧复制给MSTEdge 一共有VertexNum条边
289 if((index[p[j].begin]==-
1)&&(index[p[j].end]==-
1))
290 index[p[j].begin]=index[p[j].end]=i;
//将两个点之间直接连通
291 else if((index[p[j].begin]==-
1)&&(index[p[j].end]>=
0)){
292 index[p[j].begin]=
i;
293 IndexEnd=
index[p[j].end];
294 for(n=
1;n<=VertexNum;n++
)
295 if(index[n]==
IndexEnd)
296 index[n]=
i;
297 //如果j这条弧中，有一个结点已经被连通，但是另一个结点还没有被连通，那么这个时候因为这个时候
298 //要加入这一段弧，因此相当于将这两个结点连接起来，因此我们就直接把，和另一个结点连接的所有的相同的结点都幅值为i
299
300 }
301 else if((index[p[j].end]==-
1)&&(index[p[j].begin]>=
0))
302 {
303 index[p[j].end]=
i;
304 IndexBegin=
index[p[j].begin];
305 for(n=
1;n<=VertexNum;n++
)
306 {
307 if(index[n]==
IndexBegin)
308 index[n]=
i;
309 }
310
311 }
312 else //也就是两个结点都被包含进去了 但是还没有连通
313 {
314 IndexEnd=
index[p[j].end];
315 IndexBegin=
index[p[j].begin];
316 for(n=
1;n<=VertexNum;n++
)
317 {
318 if(index[n]==IndexBegin||index[n]==
IndexEnd)
319 index[n]=
i;
320 }
321
322 }
323 break;
324 //里面执行完一次之后直接跳出循环，i进入下一条边，而j仍然从0开始，而之前幅值过的边不会再进去
325 //因此能够保证进去的边第一次，而对于新的边中如果两个结点已经是同一个集合中的元素，也不会再进去
326
327 }
328 }
329 }
330
331
332
333
334 printf(
"MTS的边为：\n");
335 for(i=
1;i<VertexNum;i++
){
336 printf(
"%c--%c\n",G.vexs[p[MSTEdge[i]].begin],G.vexs[p[MSTEdge[i]].end]);
337 WeightSum+=
p[MSTEdge[i]].weight;
338 }
339 printf(
"MST的值为：%d\n",WeightSum);
340
341 }
参考 http://www.cnblogs.com/kangjianwei101/p/5222014.html
http://blog.csdn.net/u014488381/article/details/41447229
转载于:https://www.cnblogs.com/lovecodepql/p/7768443.html
相关资源：带权邻接矩阵-最小生成树.rar
