Ⅰ Prim算法的实现过程
G=（V,E）
①初始化：读入的数据用邻接矩阵x存储，一个一维布尔型数组chosen，记录第i个节点是否已选，初始值除1外全部设为false，记录权值的变量cost赋值为0；
以下②到④循环执行v-1次（每次生成一条边，运行（点的个数减1）次后，生成一棵最小生成树）：
②临时变量p赋值为无限大，用于记录当前最小值；
③二重循环（外循环i，内循环j）扫描邻接矩阵：如果chosen[i]=true（也就是说第i个点已选），那么扫描x[i]，如果not(chosen[j])（也就是说第j个点未选），那么如果x[i,j]<p，那么p赋值为x[i,j],临时变量q赋值为j;
④把cost赋值为cost+o，把chosen[q]赋值为true（也就是说第j个点已选）；
⑤输出cost。
一、以上给出具体的运行过程。这个算法的策略就是贪心，和dijkstra差不多，每次都选择未选的边中权值最小的那一条，直到生成最小生成树。用chosen的目的就是保证生成过程中没有环出现，也就是说保证选择的边不会通向一个已经包含在生成树中的点。
二、这个只输出最小生成树的每条边权值之和，如果要输出整棵最小生成树，加一个[1..n,1..2]的数组，在第④步的时候把每次选的边记录下来就可以了。
三、用小顶堆在第③步优化一下的话就不用每次都扫描那么多边了，只不过建堆维护堆代码写起来很麻烦。
四、prim适合用于比较稠密的网，点数和边数差不多的时候效率很恶心，一般都用kruskal。
Ⅱ 题目1:一个简单的算法演示程序(java语言实现)
1. 选择一个算法（提供选择见下），利用各种方法（图形、动画等）演示算法的演示过程。
2. 可以进行手动演示，也可以自动步进式演示。
3. 允许用户设置算法的各个输入参数，以及自动步进式演示中的时间间隔。
4. 不同的算法输入要求见下。
界面要求：
1. 尽量使用图形界面实现，要符合日常软件使用规范来设计菜单和界面。
2. 如果无法实现图形界面，则在命令行方式下也需要提供菜单，方便用户操作。
其他要求：
1. 标识符命名遵循Windows命名规范。
2. 能够注意各种异常处理，注重提高程序运行效率。
提交内容：
1. 全部源代码。
2. 软件设计和使用说明书（UML类图；实现的功能、主要技术；使用帮助文档）
参考算法：
1. 最小生成树算法：Prim算法、Kruskal算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。
2. 单源最短路算法：Dijkstra算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。
3. 最优编码算法：Huffman编码算法。允许用户输入一段英文文字，或者打开一个txt文档（英文内容），据此文档内容进行编码。要求动态列出每个字符的出现概率统计结果以及对应编码。
4. 其他可供演示的具有一定难度的算法，如关键路径问题、有向图的极大连通分支等。
Ⅲ 普里姆算法
可以这么理解：因为最小生成树是包含所有顶点的所以开始lowcost先储存到第一个点的所有值，然后执行下面算法，找到最小值并记录是第几个点，比如说这个点是3，这样有了一条1-3得道路已经确定，现在从3出发找从3出发到其他顶点的路径，如果这个从3出发到达的路径长度比从1出发的短，则更新lowcost，这样使得lowcost保存一直到达该顶点的最短路径。比如1-4是5，3-4是4，则lowcost从原来的5被改为4。
Ⅳ 普里姆算法
测试结果:
610
123456
016
021
035
125
143
235
246
254
352
456
1---31
3---64
6---42
3---25
2---53
//图最小生成树Prim算法
#include"stdio.h"
#include"stdlib.h"
#defineMAXVEX200
#defineINFINITY65535
typedefstruct
{
charvexs[MAXVEX];//顶点
intarc[MAXVEX][MAXVEX];//边的权值
intnumVertexes;//顶点总数
intnumEdges;//边的总数
}MGraph;
voidCreateMGraph(MGraph*G)/*构件图*/
{
charstr[200];
intbeginVert,endVert,weight;
inti,j;
//输入顶点总数,边的总数
scanf("%d%d",&i,&j);
G->numVertexes=i;
G->numEdges=j;
//输入顶点符号
scanf("%s",str);
for(i=0;i<G->numVertexes;i++)
{
G->vexs[i]=str[i];
}
for(i=0;i<G->numVertexes;i++)/*初始化图*/
{
for(j=0;j<G->numVertexes;j++)
{
if(i==j)
{
G->arc[i][j]=0;
}
else
{
G->arc[i][j]=G->arc[j][i]=INFINITY;
}
}
}
//输入所有边的权值
for(i=0;i<G->numEdges;i++)
{
scanf("%d%d%d",&beginVert,&endVert,&weight);
G->arc[beginVert][endVert]=weight;
}
for(i=0;i<G->numVertexes;i++)
{
for(j=i;j<G->numVertexes;j++)
{
G->arc[j][i]=G->arc[i][j];
}
}
}
/*Prim算法生成最小生成树*/
voidMiniSpanTree_Prim(MGraphG)
{
intmin,i,j,k;
intadjvex[MAXVEX]; /*保存相关顶点下标*/
intlowcost[MAXVEX]; /*保存相关顶点间边的权值*/
charbeginVert,endVert;
lowcost[0]=0;/*初始化第一个权值为0，即v0加入生成树*/
/*lowcost的值为0，在这里就是此下标的顶点已经加入生成树*/
adjvex[0]=0; /*初始化第一个顶点下标为0*/
for(i=1;i<G.numVertexes;i++) /*循环除下标为0外的全部顶点*/
{
lowcost[i]=G.arc[0][i]; /*将v0顶点与之有边的权值存入数组*/
adjvex[i]=0; /*初始化都为v0的下标*/
}
for(i=1;i<G.numVertexes;i++)
{
min=INFINITY; /*初始化最小权值为∞，*/
/*通常设置为不可能的大数字如32767、65535等*/
j=1;k=0;
while(j<G.numVertexes) /*循环全部顶点*/
{
if(lowcost[j]!=0&&lowcost[j]<min)/*如果权值不为0且权值小于min*/
{
min=lowcost[j]; /*则让当前权值成为最小值*/
k=j; /*将当前最小值的下标存入k*/
}
j++;
}
beginVert=G.vexs[adjvex[k]];
endVert=G.vexs[k];
//打印当前顶点边中权值最小的边
printf("%c---%c%d ",beginVert,endVert,min);
lowcost[k]=0;/*将当前顶点的权值设置为0,表示此顶点已经完成任务*/
for(j=1;j<G.numVertexes;j++) /*循环所有顶点*/
{
if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j])
{//如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
lowcost[j]=G.arc[k][j];//将较小的权值存入lowcost相应位置
adjvex[j]=k; //将下标为k的顶点存入adjvex
}
}
}
}
intmain(void)
{
MGraphG;
CreateMGraph(&G);
MiniSpanTree_Prim(G);
return0;
}
Ⅳ 谁能帮我画个PRIM算法的流程图
对于这种比较高级的算法代码直接看程序会比较蒙，你就光看我的算法流程吧，prim算法用的是贪心算法的思想，即每一步都作出局部的最优解，关于prim算法为什么能用贪心算法的证明，你可以参考《计算机算法设计与分析》这本书。（我反正不想看那么无聊的证明，也看不明白，呵呵）。
定义一个集合v 和 a，其中v是全体节点（总节点数为n）的集合，v初始为空。定义一个记录最小生成数边数的变量c。
1.在v中任选一个节点，并加入到a中。在v中删除该节点。
2.选一个在所有连接v集合和a集合权值最小的边（即一个节点是v的某一个节点，一个是a中的某一个节点）
3。将两个节点连接。将c加1
4.将第3步才在v中节点删除并加入到a中.
5.如果c为n-1则完成最小生成树，否则回到第2步。
明白了没？不明白再问我啊，希望对你有所帮助。
Ⅵ cs61b实验记录（三）project 2 prim迷宫随机生成算法
nothing special
具体详见我的GitHub： https://github.com/BoL0150/Berkeley-cs61b/tree/main/hw1
Random对象是一个“伪随机数”生成器，它可以产生一串无穷的看起来是随机数的数字序列，调用nextInt方法获取序列中的每一个数字。
它之所以叫“伪随机数”是因为它产生的序列并不是真正随机的。我们获取不同的序列的方式是向Random的构造器中传入一个数字，这个数字被称为“seed”，如果我们用相同的seed构造Random，那么我们一定会获得完全相同的序列。
java.lang.Math中也有一个名为random()的静态方法可以生成随机数
Math.random() 方法生成[0, 1)范围内的double类型随机数；Random类中的nextXxxx(n)系列方法生成0（包括）到n（不包括）之间的随机数；
绘制地图：
从宏观上来看，主要分为这么几步：
创建一个Room类，将每一个房间当作一个对象，随机生成房间的坐标以及长和宽，然后判断房间是否重叠，
同时设置一个参数，控制房间重复生成的上限次数。 将所有生成的房间对象放在一个List中 ，因为在修建完迷宫后还需要对每一个房间与它旁边的迷宫进行打通，以便获取房间的位置和参数。
此时在房间中填GRASS以及使用两个数组的原因稍后进行解释。
我们将这一步分解来看，首先：如何在一张空的图上生成迷宫？
我们采用 prim迷宫随机生成算法 ，此算法的原理及具体实现如下：
原理：
具体实现：
生成迷宫时要注意 随机 从候选列表中选取点，否则生成的迷宫会朝着同一个方向
我们知道了如何在空的图上生成迷宫，也可以由此推断出如何在房间的周围生成迷宫
这一步没什么好说的，对每一个房间随机选取一条边上的一点向外打通，如果不符合条件（如碰到NOTHING等）就重新选取一点。
然而，此时的图中还有很多的死胡同（即三面都是墙的FLOOR），以及房间中依然是GRASS，所以我们需要填补所有的死胡同，将GRASS替换为FLOOR。
去除死胡同我们需要对每一个点，查看周围的四个点是否是WALL，然后改变这个点，再进入下一个点。这会让人想起DFS，但是原本的DFS是沿着一条路线，从一头走到另一头，对路上的每一个点都只是 依次 查看周围的点，一旦找到可以通过的点，就立马进入， 无法确定这一点周围是否有3个WALL 。只有当走到头时，扫描了周围的四个点，发现都无法通过，才会往后退。也就是说，只有后退的时候，我们才能知道某一点周围所有点的情况。而填补所有的死胡同需要我们从所有的死胡同的终点出发，向中间汇聚，一边移动一边填补。
所以我们需要将DFS改造成 前进和后退时都要查看周围所有点的情况 ，才能进行下一步。
我们还需要移除所有多余的墙，也就是四个角上没有FLOOR的WALL
最后，再添加上Player和Lock_Door就完成了
附上autograder的评分
Ⅶ 利用Prim（普里姆）算法 构造最小生成树 程序
算法同样是解决最小生成树的问题。
其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个集合当中，这就用到了并查集的知识。直到边的集合达到了n-1个。
与prim算法的不同：prim算法为单源不断寻找连接的最短边，向外扩展，即单树形成森林。而Kruskal算法则是不断寻找最短边然后不断将集合合并，即多树形成森林。
复杂度的不同：prim算法的复杂度是O(n^2),其中n为点的个数。Kruskal算法的复杂度是O(e*loge)，其中e为边的个数。两者各有优劣，在不同的情况下选择不同的算法。
Prim算法用于求无向图的最小生成树
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2)
Prim算法实现：
（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）
（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
{先选定一个点，然后从该点出发，与该点相连的点取权值最小者归入集合，然后再比较在集合中的两点与其它各点的边的权值最小者，再次进入集合，一直到将所有的点都归入集合为止。}
Ⅷ 有什么无权无向图的最短路径算法比较好，求一个用java实现的
有什么无权无向图的最短路径算法比较好
带权图也分有向和无向两种，基本的算法可以看看书咯。 带权的无向图的最短路径又叫最小生成树，Prim算法和Kruskal算法； 带权的有向图的最短路径算法有迪杰斯特拉算法和佛洛依德算法；
String[]s={"January","February","March","April","May","June","July","August","September","October","November","December"};
System.out.print("请输入数字（1-12）：");
BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));
Stringstr=br.readLine();
intm=Integer.parseInt(str);
if(m<=0||m>=13)
{
Ⅸ 一个简单的算法演示程序(JAVA语言实现)
这么大的程序起码得写好几天呢 楼主就给十分啊……