构造非连通图 ST=( V,{ } );
k = i = 0; // k 计选中的边数
while (k<n-1) {
++i;
检查边集 E 中第 i 条权值最小的边(u,v);
**若(u,v)加入ST后不使ST中产生回路,
则 输出边(u,v); 且 k++;**
}
typedef struct {
// 增加边结构定义
int beginvex, endvex; // 边的起点、终点
VRType cost; // 边的权值
} edgetype;
edgetype edges[MAX_VERTEX_NUM];
void MiniSpanTree_Kruskal(ALGraph &G){
int parents[MAX_VERTEX_NUM];
cin >> G.vexnum >> G.arcnum; // 顶点数、弧数
for(i = 0; i < G.vexnum; i++){
// 建立顶点表
G.vertices[i].data = new char[10];
cin >> G.vertices[i].data; // 读入顶点信息并初始化
G.vertices[i].firstarc = NULL;
}
for(k = 0; k < G.arcnum; k++){
// 建立边表
v1 = new char[10];
v2 = new char[10];
cin >> v1 >> v2 >> w;
i = LocateVex_ALG(G, v1);
j = LocateVex_ALG(G, v2);
edges[k].beginvex = i;
edges[k].endvex = j;
edges[k].cost = w;
p = new ArcNode;
p->info = NULL;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
}
Sort(G, edges); // 按权值大小,对边进行排序
for(i = 0; i < G.vexnum; i++)
parents[i] = 0;
for(i = 0; i < G.arcnum; i++){
bnf = Find(parents, edges[i].beginvex); // 查找边头分量
edf = Find(parents, edges[i].endvex); // 查找边尾分量
if(bnf != edf){
parents[bnf] = edf;
cout << edges[i].beginvex << edges[i].endvex;
cout << " " << edges[i].cost << endl;
}
}
}
int Find(int parents[], int f){
// 查找函数
while(parents[f] > 0) f = parents[f];
return f;
}
算法名 | Prim | KrusKal
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。