-
Notifications
You must be signed in to change notification settings - Fork 0
/
MST
150 lines (150 loc) · 4.49 KB
/
MST
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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MaxSize 140
typedef char VertexType;
typedef struct Graph { //定义图的邻接矩阵表示法结构
int ver;
double edg[MaxSize][MaxSize];
}Graph;
typedef struct gEdge{ //定义一个边集结构,用来存储图的所有边信息
int begin;
int end;
double weight;
}gEdge;
void CreateGraph( Graph *g ){ //邻接矩阵法图的生成函数
int i = 0;
int j = 0;
int VertexNum;
printf("请输入图的顶点个数:\n");
scanf("%d",&g->ver);
VertexNum = g->ver;
printf("请输入相应的的邻接矩阵:\n");
for( i=0; i<VertexNum; i++ )
for( j=0; j<VertexNum; j++ )
scanf("%lf", &g->edg[i][j]);
}
void PrintGraph( Graph g ) //打印图的结点标识符和邻接矩阵
{
int i, j;
int VertexNum = g.ver;
printf("图的顶点为:\n");
for( i=0; i<VertexNum; i++ )
printf("%d ", i+1);
printf("\n");
printf("图的邻接矩阵为:\n");
for( i=0; i<VertexNum; i++ )
{
for( j=0; j<VertexNum; j++ )
printf("%lf", g.edg[i][j]);
printf("\n");
}
}
int CalVerNum( Graph g ) //求图的顶点数
{
return g.ver;
}
int CalEdgNum( Graph g ) //获取图的边数
{
Graph p = g;
int count = 0;
int VertexNum = CalVerNum( p );
for( int i=0; i<VertexNum; i++ )
for( int j=i; j<VertexNum; j++ ) //邻接矩阵对称,计算上三角元素和即可
if( 0 != p.edg[i][j] )
count++;
return count;
}
gEdge *CreateEdges( Graph g ) //生成图的排序过的边集数组
{
int i, j;
int k = 0;
int EdgNum = CalEdgNum( g );
int VertexNum = CalVerNum( g );
gEdge temp;
gEdge *p = (gEdge *)malloc(sizeof(gEdge)*EdgNum);
for( i=0; i<VertexNum; i++ ) //边集数组初始化,同样只考虑上三角矩阵
for( j=i; j<VertexNum; j++ )
if( 0 != g.edg[i][j] )
{
p[k].begin = i;
p[k].end = j;
p[k].weight = g.edg[i][j];
k++;
}
for( i=0; i<EdgNum-1; i++ ) //对边集数组进行选择排序
for( j=i+1; j<EdgNum; j++ )
if( p[i].weight > p[j].weight )
{
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
return p;
}
//Kruskal算法生成MST
void Kruskal( Graph g )
{
int i;
int VertexNum = CalVerNum( g );
int EdgNum = CalEdgNum( g );
gEdge *p = CreateEdges( g );
int *index = (int *)malloc(sizeof(int)*VertexNum);
//index数组,其元素为连通分量的编号,index[i] = index[j] 表示编号为i 和 j的顶点在同一个连通分量中,反之则不在同一个连通分量
int *MSTEdge = (int *)malloc(sizeof(int)*VertexNum-1);
//MSTEdge数组,用来存储已确定的MST的边的编号,共VertexNum-1条边
int k= 0;
float WeightSum = 0;
int IndexBegin, IndexEnd;
for(int i=0; i<VertexNum; i++ ) //初始化所有index = -1
index[i] = -1;
for( i=0; i<VertexNum-1; i++ )
{
for(int j=0; j<EdgNum; j++ )
{
if( !(index[p[j].begin]>=0 && index[p[j].end]>=0 && index[p[j].begin]==index[p[j].end]) ) { //找到当前还没加入到同一个连通分量且权值最下的边
MSTEdge[i] = j; //将其加入到MST中去
if( (-1 == index[p[j].begin]) && (-1 == index[p[j].end]) ) //该边的两个顶点都没加入过任何一个连通分量
index[p[j].begin] = index[p[j].end] = i;
else if( (-1 == index[p[j].begin]) && (index[p[j].end] >= 0) ) { //该边的尾end已在一个连通分量,头begin未加入过任何连通分量
index[p[j].begin] = i;
IndexEnd = index[p[j].end];
for(int n=0; n<VertexNum; n++ )
if( index[n] == IndexEnd )
index[n] = i;
}
else if( (-1 == index[p[j].end]) && (index[p[j].begin] >= 0) ){ //该边的头begin已在一个连通分量,尾end未加入过任何连通分量
index[p[j].end] = i;
IndexBegin = index[p[j].begin];
for(int n=0; n<VertexNum; n++ )
if( index[n] == IndexBegin )
index[n] = i;
}
else{
IndexEnd = index[p[j].end];
IndexBegin = index[p[j].begin];
for(int n=0; n<VertexNum; n++ ) //该边的两个顶点都已经存在于两个不同的连通分量中
if( index[n] == IndexBegin || index[n] == IndexEnd )
index[n] = i; //将该连通分量编号全部修改为相同的值
}
break;
}
}
}
printf("MST的边为:\n"); //输出MST的边
for( i=0; i<VertexNum-1; i++ ){
printf("%d--%d\n", p[MSTEdge[i]].begin+1 , p[MSTEdge[i]].end+1 );
WeightSum+=p[MSTEdge[i]].weight;
}
printf("MST的权值为:%lf\n", WeightSum); //输出MST的权值
}
int main(){
double a=100.00;
printf("%lf\n",a);
Graph g;
CreateGraph( &g );
PrintGraph( g );
Kruskal( g );
system("pause");
return 0;
}