# prim算法

prim算法在严蔚敏树上有解释，但是都是数学语言，很深奥。

prim算法过程为：

#include<stdio.h>
#include<stdlib.h>
typedef int bool;
typedef char VertexType;
typedef int  EdgeType;
#define false 0
#define true 1
#define MAXVEX 100
#define IFY 65535

VertexType g_init_vexs[MAXVEX] = {'A','B','C','D','E','F','G','H','I'};

EdgeType g_init_edges[MAXVEX][MAXVEX] = {
{0,11,IFY,IFY,IFY,9,IFY,IFY,6},    //'A'
{11,0,10,IFY,IFY,IFY,IFY,IFY,8},  //'B'
{IFY,10,0,17,IFY,IFY,IFY,IFY,IFY},//'C'
{IFY,IFY,17,0,9,IFY,IFY,IFY,IFY},//'D'
{IFY,IFY,IFY,9,0,7,5,8,IFY},    //'E'
{9,IFY,IFY,IFY,7,0,3,IFY,IFY},    //'F'
{IFY,IFY,IFY,IFY,5,3,0,IFY,IFY},    //'G'
{IFY,IFY,IFY,IFY,8,IFY,IFY,0,IFY},    //'H'
{6,8,IFY,IFY,IFY,IFY,IFY,IFY,0},    //'I'
};

typedef struct {
VertexType vexs[MAXVEX];
EdgeType Mat[MAXVEX][MAXVEX];
int numVexs,numEdges;
}MGraph;

//打印矩阵,使用二维指针
void prt_maxtix(EdgeType (*p)[MAXVEX],int vexs)
{
int i,j;
for(i=0;i<vexs;i++)
{
printf("\t");
for(j=0;j<vexs;j++)
{
if( *(*p + j) == IFY)
{
printf("  \$ ");
}
else
{
printf(" %2d ", *(*p + j));
}
}
p++;
printf("\n");
}
}

//check the number of vextex
int getVexNum(VertexType *vexs)
{
VertexType *pos = vexs;
int cnt=0;
while(*pos <= 'Z' && *pos >= 'A')
{
cnt++;
pos++;
}
return cnt;
}
//检查矩阵是否对称
bool checkMat(EdgeType *p,VertexType numvex)
{
int i,j;
for (i=0;i<numvex;i++)
{
for(j=i+1;j<numvex;j++)
{
//printf("[%d][%d] = %d\t",i,j,*(p + MAXVEX*i + j));
//printf("[%d][%d] = %d\n",j,i,*(p + MAXVEX*j + i));
if (*(p + MAXVEX*i + j) != *(p + MAXVEX*j +i) )
{
printf("ERROR:Mat[%d][%d] or Mat[%d][%d] not equal!\n",i,j,j,i);
return false;
}
}
}
return true;
}
//用已知的一维数组和二维数组分别初始化顶点和边
void init_Grp(MGraph *g,VertexType *v,EdgeType *p)
{
int i,j;
// init vex num
(*g).numVexs = getVexNum(v);

//init vexter
for (i=0;i<(*g).numVexs;i++)
{
(*g).vexs[i]=*v;
v++;
}

//init Mat
for (i=0;i<(*g).numVexs;i++)
{
for (j=0;j<(*g).numVexs;j++)
{
(*g).Mat[i][j] = *(p + MAXVEX*i + j);
}
}
if(checkMat(&((*g).Mat[0][0]),(*g).numVexs) == false)
{
printf("init error!\n");
exit(0);
}
}

/*void prim(MGraph G,int num)
{
int sum=0;
int min,i,j,k;
int lowcost[MAXVEX];

lowcost[num] = 0;

for (i = 0; i < G.numVexs;i++ )
{
if (num == i)
{
continue;
}
lowcost[i]=G.Mat[num][i];    //存放起始顶点到各个顶点的权值。
}

for (i=0;i<G.numVexs;i++)
{
//1.找权最短路径
//2.把权最短路径的顶点纳入已找到的顶点集合中，重新查看新集合中最短路径
if(num == i)
{
continue;
}
min = IFY;
j=0;k=0;
while (j<G.numVexs)
{
if (lowcost[j] != 0 && lowcost[j] < min)
{
min = lowcost[j];
k = j;

}
j++;
}
lowcost[k]=0;
for (j=0;j<G.numVexs;j++)
{

if (lowcost[j] != 0 && G.Mat[k][j] < lowcost[j])
{
lowcost[j] = G.Mat[k][j];
}
}

}
printf("total:sum=%d\n",sum);
}*/

void Prim(MGraph G,int num)
{
int sum,i,j,min,k;
int lowcost[MAXVEX];
sum=0;
lowcost[num]=0;
for(i=0;i<G.numVexs;i++)
{
if(i==num)
continue;
lowcost[i]=G.Mat[num][i];
}
for(i=0;i<G.numVexs;i++)
{
if(i==num)
continue;
min=IFY;
k=0;
//求出代价最小的点
for(j=0;j<G.numVexs;j++)
{
if(lowcost[j]!=0&&lowcost[j]<min)
{
min=lowcost[j];
k=j;
}
}
lowcost[k]=0;
for(j=0;j<G.numVexs;j++)
{
if(lowcost[j]!=0&&G.Mat[k][j]<lowcost[j])
{
lowcost[j]=G.Mat[k][j];
}
}
}
printf("total:sum=%d\n",sum);
}

int main(int argc, char* argv[])
{
MGraph grp;
//init
init_Grp(&grp,g_init_vexs,&g_init_edges[0][0]);
//print Matix
prt_maxtix(grp.Mat,grp.numVexs);

//prim(grp,4);
int i;
for (i=0;i<grp.numVexs;i++)
{
Prim(grp,i);
}
//prim(grp,3);

getchar();
return 0;
}

|
9月前
|

177 0
|
18天前
|

15 0
|
1月前
|

16 0
|
8月前
|

62 0
|
12月前
|

java数据结构最经济的地下通道建设方案prim算法
MX是世界上第一大传媒娱乐企业，该公司数十年的经营历史中创作了很多经典影片，此外还经营着很多的规模十分宏大世界级的主题娱乐公园。最近MX公司刚和C国X城市达成协定，共同投资建设C国国内唯一一家主题娱乐公园。
51 0
|

13.1.概述 最小生成树，包含图的所有顶点的一棵树，树的边采用包含在图中的原有边中权重和最小的边。翻译成人话就是遍历一遍全图所有顶点的最短路径，这条路径就叫最小生成树。 最小生成树存在和图是连通图互为充要条件，顶点都不连通，肯定不可能有路能遍历一遍全图。 求解最小生成树有两种常用算法：
131 0
|

Prim算法和Kruskal算法到底哪个好？
Prim算法和Kruskal算法到底哪个好？
168 0
|

102 0
|

90 0
|

190 0