数据结构之---C语⾔实现最⼩⽣成树之prim（普⾥姆）算法
//最⼩⽣成树之Prim算法
//杨鑫
#include
#include
#define n 6
#define MaxNum 10000 /*定义⼀个最⼤整数*/
/*定义邻接矩阵类型*/
typedef int adjmatrix[n + 1][n + 1]; /*0号单元没⽤*/
typedef struct
{
int fromvex, tovex; //⽣成树的起点和终点
int weight; //边的权重
}Edge;
typedef Edge *EdgeNode; //定义⽣成树的别名
int arcnum; /*边的个数*/
/*建⽴图的邻接矩阵*/
void CreatMatrix(adjmatrix GA)
{
int i, j, k, e;
printf("=============================\n");
printf("图中有%d个顶点\n", n);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(i==j)
{
GA[i][j]=0; /*对⾓线的值置为0*/
}
else
{
GA[i][j]=MaxNum; /*其他位置的值置初始化为⼀个最⼤整数*/
}
}
}
printf("请输⼊边的个数：\n");
scanf("%d", &arcnum);
printf("请输⼊边的信息，依照起点，终点，权值的形式输⼊：\n");
for(k=1;k<=arcnum;k++)
{
scanf("%d,%d,%d",&i,&j,&e); /*读⼊边的信息*/
GA[i][j]=e;
GA[j][i]=e;
}
}
/*初始化图的边集数组*/
void InitEdge(EdgeNode GE,int m)
{
int i;
for(i=1;i<=m;i++)
{
GE[i].weight=0;
《魔鬼与普里姆小姐》经典读后感十篇
《魔鬼与普里姆小姐》是一本由[巴西] 保罗·柯艾略著作，南海出版公司出版的 平装 图书，本书定价：22.00元，页数：192，特精心从网络上整理的一些读者的读后感，希望对大家能有帮助。
《魔鬼与普里姆小姐》读后感(一)：摘录一
表面上宽厚仁慈，不过是不敢在生活中表态罢了。相信自己善良要比站起来捍卫权利容易的多；逆来顺受要比鼓起勇气与更强大的人抗争容易得多。我们总会说，哪些被人丢过来的石头没有砸到自己，可当深夜人静，伴侣或室友都已酣然入睡时，我们才默默的为自己的懦弱留下眼泪。
《魔鬼与普里姆小姐》读后感(二)：随便写写感受
＂当亚哈明白圣萨文跟自己一样时，也就明白了自己跟圣萨文一样。＂
一点我没有明白啦，最后尚尔塔为什么独吞了金条呢...三天前她跟外国人不是做过约定，就算没有人死，也是会把十根金条平分给小镇里的每一位居民么，这样尚尔塔只能得到一根的...
难道是因为其实最后人们还是邪恶的想把贝尔达杀死，但是同样出于恐惧而没有这么做？即使是因为这样自己独吞金条也不好吧...额...尚塔尔的天使呢？不是醒了么...
《魔鬼与普里姆小姐》读后感(四)：每个人的灵魂里都住着善与恶
只有神才是良善的。 相信自己的善是无知之举，大多数时候我们只是不需要作恶或者是不能肆无忌惮的作恶而已吧。如果给予我们机会，在生与死的抉择问题上，我们灵魂中的那个魔鬼就会出来。
就和公正公开课里面的电车问题，还有英国那个纠结了很久的案子一样。
在选择自己和他人的命运关头，谁不会希望命运之秤向自己倾斜。
书中想要表达，这一切都要靠自制，无比的同意。若是简单的相信人性，那么，我们将要承担难以挽回的后果，所以，维持现有的一切秩序，最根本的是要靠法律，所谓的法律，也就是书中说的意思一样，依靠恐惧来抑制人心中的恶吧。
保罗柯艾略，最爱的作家，再一次教给了我好多。
Prim算法
Prim 算法
普⾥姆算法介绍
普⾥姆 (Prim) 算法，是⽤来求加权连通图的最⼩⽣成树的算法。
基本思想对于图 G ⽽⾔，V 是所有顶点的集合；现在，设置两个新的集合 U 和 T，其中 U ⽤于存放 G 的最⼩⽣成树中的顶点，T 存放 G 的最⼩⽣成树中的边。 从所有 uЄU，vЄ(V-U) (V-U 表⽰出去 U 的所有顶点)的边中选取权值最⼩的边 (u, v)，将顶点 v 加⼊集合 U 中，将边(u, v) 加⼊集合 T 中，如此不断重复，直到U=V 为⽌，最⼩⽣成树构造完毕，这时集合 T 中包含了最⼩⽣成树中的所有边。
普⾥姆算法图解
以上图 G4 为例，来对普⾥姆进⾏演⽰ (从第⼀个顶点 A 开始通过普⾥姆算法⽣成最⼩⽣成树)。
初始状态：V 是所有顶点的集合，即 V={A,B,C,D,E,F,G}；U 和 T 都是空！第 1 步：将顶点 A 加⼊到 U 中。此时，U={A}。第 2 步：将顶点 B 加⼊到 U 中。上⼀步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边 (A,B) 的权值最⼩。将顶点 B 添加到 U 中；此时，U={A,B}。第 3 步：将顶点 F 加⼊到 U 中。上⼀步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边 (B,F) 的权值最⼩。将顶点 F 添加到 U 中；此时，U={A,B,F}。第 4 步：将顶点 E 加⼊到 U 中。上⼀步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边 (F,E) 的权值最⼩。将顶点 E 添加到 U 中；此时，U={A,B,F,E}。第 5 步：将顶点 D 加⼊到 U 中。上⼀步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边 (E,D) 的权值最⼩。将顶点 D 添加到 U 中；此时，U={A,B,F,E,D}。第 6 步：将顶点 C 加⼊到 U 中。上⼀步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边 (D,C) 的权值最⼩。将顶点 C 添加到 U 中；此时，U={A,B,F,E,D,C}。第 7 步：将顶点 G 加⼊到 U 中。上⼀步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边 (F,G) 的权值最⼩。将顶点 G 添加到 U 中；此时，U=V。
最⼩⽣成树---普⾥姆算法（Prim算法）和克鲁斯卡尔算法
（Kruskal算法）
最⼩⽣成树的性质：MST性质（假设N=(V,{E})是⼀个连通⽹，U是顶点集V的⼀个⾮空⼦集，如果（u，v）是⼀条具有最⼩权值的边，
其中u属于U，v属于V-U，则必定存在⼀颗包含边（u，v）的最⼩⽣成树）
普⾥姆算法（Prim算法)
思路：以点为⽬标构建最⼩⽣成树
1.将初始点顶点u加⼊U中，初始化集合V-U中各顶点到初始顶点u的权值；
2.根据最⼩⽣成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最⼩。循环n-1次如下操作：
（1）从数组lowcost[k]中找到vk到集合U的最⼩权值边，并从数组arjvex[k] = j中找到该边在集合U中的顶点下标
(2)打印此边，并将vk加⼊U中。
（3）通过查找邻接矩阵Vk⾏的各个权值，即vk点到V-U中各顶点的权值，与lowcost的对应值进⾏⽐较，若更⼩则更新
lowcost，并将k存⼊arjvex数组中
以下图为例
#include
using namespace std;
#define MAXVEX 100
#define INF 65535
typedef char VertexType;
typedef int EdgeType;
typedef struct {
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
void CreateMGraph(MGraph *G) {
int m, n, w; //vm-vn的权重w
scanf("%d %d", &G->numVertexes, &G->numEdges);
for(int i = 0; i < G->numVertexes; i++) {
getchar();
scanf("%c", &G->vexs[i]);
