数据结构（C实现）------- 最小生成树之Prim算法
程序员文章站
2022-03-23 20:08:09
算法描述
如果连通图是一个网，则称该网中所有生成树中权值总和最小的生成树为最小生成树，也称最小代价生成树。利用Prim算法构造的最小生成树方法思想：
假...
算法描述
如果连通图是一个网，则称该网中所有生成树中权值总和最小的生成树为最小生成树，也称最小代价生成树。利用Prim算法构造的最小生成树方法思想：
假设G=(V,E)是一个具有n个顶点的连通网，顶点集V={v1,v2,...,vn}.设所求的最小生成树T=(U,TE),其中U是T的顶点集，TE是T的边集，U和TE初值均为空集。
Prim算法的基本思想如下：首先从V中任取一个顶点(假定取v1),将生成树T置为仅有一个结点v1的树，即U={v1};然后只要U是V的真子集，就在所有那些一个端点在T中，另一个端点在T外的边中，找一条最短（即权值最小 )的边。假定符合条件的最短边为(vi,vj),则把该条边和其不在T中的顶点vj，分别并入T的边集TE和顶点集U。如此进行下去，每次往生成树里并入一个顶点和一条边，直到把所有顶点都包括进生成树T为止。此时，必有U=V，TE中有n-1条边，则T=(U,TE)是G的一棵最小生成树。
算法实现
设一个edge数组，记录从顶点Ｕ集到Ｖ－Ｕ的代价最小的边，每条边的信息包括边的始点和，终点和权值。从顶点u出发，利用prim算法求最小生成树步骤如下：
(1) 初始化edge数组，记录顶点u到图中其余结点的代价最小的n-1的边。
(2) 将顶点u加入Ｕ中。
(3) 当U不等于V时，做如下处理。
1) 从edge数组中选一条代价最小的边。
2) 将该边的终点加入U中。
3) 调整edges数组，使它始终记录顶点U到V-U的代价最小的边。
算法代码
// 定义边结构体
typedef struct{
int start;
int end;
int cost;
}Edge;
/*
*Prim算法求最小生成树
* */
void Prim_MG(MGraph MG,char vs){
Edge edge[MAX_VEX_NUM];
int i,j,k,v,min;
int s = getIndexOfVexs(vs,&MG);
//初始化边
for(i = 1;i <= MG.vexnum;i++){
if(s != i){
edge[i].start = s;
edge[i].end = i;
edge[i].cost = MG.arcs[s][i];
}
}
//首先将s加入生成树集合中
edge[s].cost = 0;
for(i = 2;i <= MG.vexnum;i++){
min = 1000;
for(j = 1;j<= MG.vexnum;j++){
if(edge[j].cost != 0 && edge[j].cost < min ){
min = edge[j].cost;
k = j;
}
}
v = edge[k].end;
edge[v].cost = 0; // 加入新节点
//输出生成树中的边
printf(%c %c %d
,MG.vexs[edge[v].start],MG.vexs[edge[v].end],MG.arcs[edge[v].start][edge[v].end]);
//重新调整数组
for(j = 1;j <= MG.vexnum;j++){
if(edge[j].cost != 0 && MG.arcs[v][j] != 0 && MG.arcs[v][j] < edge[j].cost){
edge[j].start = k;
edge[j].end = j;
edge[j].cost = MG.arcs[v][j];
}
}
}
}
算法说明
假设图中有n个顶点，则第一个进行初始化的循环语句的频度为n,第二个循环语句频度为n-1。其中有两个内循环；其一是在edge数组中找权值最小的边，其频度为n-1,其二是重新调整edge数组的边，频度为n,所以Prim算法的时间复杂度为O(n^2)，而与图中的边数无关，因此适用于求稠密的最小生成树。
完整代码
/*
* =====================================================================================
*
* Filename: Prim.c
*
* Description: 最小生成树算法之Prim算法
*
* Version: 1.0
* Created: 2015年03月11日 15时27分19秒
* Revision: none
* Compiler: gcc
*
* Author: jesson20121020 (), 997287955@qq.com
* Organization:
*
* =====================================================================================
*/
#include
#include
#define MAX_VEX_NUM 50
#define UN_REACH 1000
typedef char VertexType;
typedef enum {
DG, UDG
} GraphType;
typedef struct {
VertexType vexs[MAX_VEX_NUM];
int arcs[MAX_VEX_NUM][MAX_VEX_NUM];
int vexnum, arcnum;
GraphType type;
} MGraph;
/**
* 根据名称得到指定顶点在顶点集合中的下标
* vex 顶点
* return 如果找到，则返回下标，否则，返回０
*/
int getIndexOfVexs(char vex, MGraph *MG) {
int i;
for (i = 1; i <= MG->vexnum; i++) {
if (MG->vexs[i] == vex) {
return i;
}
}
return 0;
}
/**
* 创建邻接矩阵
*/
void create_MG(MGraph *MG) {
int i, j, k,weight;
int v1, v2, type;
char c1, c2;
printf(Please input graph type DG(0) or UDG(1) :);
scanf(%d, &type);
if (type == 0)
MG->type = DG;
else if (type == 1)
MG->type = UDG;
else {
printf(Please input correct graph type DG(0) or UDG(1)!);
return;
}
printf(Please input vexmun : );
scanf(%d, &MG->vexnum);
printf(Please input arcnum : );
scanf(%d, &MG->arcnum);
getchar();
for (i = 1; i <= MG->vexnum; i++) {
printf(Please input %dth vex(char):, i);
scanf(%c, &MG->vexs[i]);
getchar();
}
//初始化邻接矩阵
for (i = 1; i <= MG->vexnum; i++) {
for (j = 1; j <= MG->vexnum; j++) {
if(i == j)
MG->arcs[i][j] = 0;
else
MG->arcs[i][j] = UN_REACH;
}
}
//输入边的信息，建立邻接矩阵
for (k = 1; k <= MG->arcnum; k++) {
printf(Please input %dth arc v1(char) v2(char) weight(int): , k);
scanf(%c %c %d, &c1, &c2,&weight);
v1 = getIndexOfVexs(c1, MG);
v2 = getIndexOfVexs(c2, MG);
if (MG->type == 1)
MG->arcs[v1][v2] = MG->arcs[v2][v1] = weight;
else
MG->arcs[v1][v2] = weight;
getchar();
}
}
/**
* 打印邻接矩阵和顶点信息
*/
void print_MG(MGraph MG) {
int i, j;
if(MG.type == DG){
printf(Graph type: Direct graph
);
}
else{
printf(Graph type: Undirect graph
);
}
printf(Graph vertex number: %d
,MG.vexnum);
printf(Graph arc number: %d
,MG.arcnum);
printf(Vertex set:
);
for (i = 1; i <= MG.vexnum; i++)
printf(%c , MG.vexs[i]);
printf(
Adjacency Matrix:
);
for (i = 1; i <= MG.vexnum; i++) {
j = 1;
for (; j < MG.vexnum; j++) {
printf(%d , MG.arcs[i][j]);
}
printf(%d
, MG.arcs[i][j]);
}
}
// 定义边结构体
typedef struct{
int start;
int end;
int cost;
}Edge;
/*
*Prim算法求最小生成树
* */
void Prim_MG(MGraph MG,char vs){
Edge edge[MAX_VEX_NUM];
int i,j,k,v,min;
int s = getIndexOfVexs(vs,&MG);
//初始化边
for(i = 1;i <= MG.vexnum;i++){
if(s != i){
edge[i].start = s;
edge[i].end = i;
edge[i].cost = MG.arcs[s][i];
}
}
//首先将s加入生成树集合中
edge[s].cost = 0;
for(i = 2;i <= MG.vexnum;i++){
min = 1000;
for(j = 1;j<= MG.vexnum;j++){
if(edge[j].cost != 0 && edge[j].cost < min ){
min = edge[j].cost;
k = j;
}
}
v = edge[k].end;
edge[v].cost = 0; // 加入新节点
//输出生成树中的边
printf(%c %c %d
,MG.vexs[edge[v].start],MG.vexs[edge[v].end],MG.arcs[edge[v].start][edge[v].end]);
//重新调整数组
for(j = 1;j <= MG.vexnum;j++){
if(edge[j].cost != 0 && MG.arcs[v][j] != 0 && MG.arcs[v][j] < edge[j].cost){
edge[j].start = k;
edge[j].end = j;
edge[j].cost = MG.arcs[v][j];
}
}
}
}
/**
* 主函数
*/
int main(void) {
MGraph MG;
char startVex;
create_MG(&MG);
print_MG(MG);
printf(
Please input the start vex(char):);
scanf(%c,&startVex);
printf(
The result of Prim:
);
Prim_MG(MG,startVex);
return EXIT_SUCCESS;
}
运行演示
jesson@jesson-HP:~/develop/workspace/c_learning/csdn/Prim$ gcc -o Prim Prim.c jesson@jesson-HP:~/develop/workspace/c_learning/csdn/Prim$ ./Prim Please input graph type DG(0) or UDG(1) :1 Please input vexmun : 4 Please input arcnum : 5 Please input 1th vex(char):a Please input 2th vex(char):b Please input 3th vex(char):c Please input 4th vex(char):d Please input 1th arc v1(char) v2(char) weight(int): a b 1 Please input 2th arc v1(char) v2(char) weight(int): a c 3 Please input 3th arc v1(char) v2(char) weight(int): a d 4 Please input 4th arc v1(char) v2(char) weight(int): b c 2 Please input 5th arc v1(char) v2(char) weight(int): c d 3 Please input the start vex(char):a The result of Prim: a b 1 b c 2 c d 3