A. 普里姆算法
可以这么理解：因为最小生成树是包含所有顶点的所以开始lowcost先储存到第一个点的所有值，然后执行下面算法，找到最小值并记录是第几个点，比如说这个点是3，这样有了一条1-3得道路已经确定，现在从3出发找从3出发到其他顶点的路径，如果这个从3出发到达的路径长度比从1出发的短，则更新lowcost，这样使得lowcost保存一直到达该顶点的最短路径。比如1-4是5，3-4是4，则lowcost从原来的5被改为4。
B. 什么是Prim算法
Prim算法
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](i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）
（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
参考程序
/* Prim.c
Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
/* The impact of the situation of articulation point exists can be omitted in Prim algorithm but not in Kruskal algorithm */
#include "stdio.h"
#define maxver 10
#define maxright 100
int main()
{
int G[maxver][maxver],in[maxver]=,path[maxver][2];
int i,j,k,min=maxright;
int v1,v2,num,temp,status=0,start=0;
restart:
printf("Please enter the number of vertex(s) in the graph:\n");
scanf("%d",&num);
if(num>maxver||num<0)
{
printf("Error!Please reinput!\n");
goto restart;
}
for(j=0;j<num;j++)
for(k=0;k<num;k++)
{
if(j==k)
G[j][k]=maxright;
else
if(j<k)
{
re:
printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);
scanf("%d",&temp);
if(temp>=maxright||temp<-1)
{
printf("Invalid input!\n");
goto re;
}
if(temp==-1)
temp=maxright;
G[j][k]=G[k][j]=temp;
}
}
for(j=0;j<num;j++)
{
status=0;
for(k=0;k<num;k++)
if(G[j][k]<maxright)
{
status=1;
break;
}
if(status==0)
break;
}
do
{
printf("Please enter the vertex where Prim algorithm starts:");
scanf("%d",&start);
}while(start<0||start>num);
in[start-1]=1;
for(i=0;i<num-1&&status;i++)
{
for(j=0;j<num;j++)
for(k=0;k<num;k++)
if(G[j][k]<min&&in[j]&&(!in[k]))
{
v1=j;
v2=k;
min=G[j][k];
}
if(!in[v2])
{
path[i][0]=v1;
path[i][1]=v2;
in[v1]=1;
in[v2]=1;
min=maxright;
}
}
if(!status)
printf("We cannot deal with it because the graph is not connected!\n");
else
{
for(i=0;i<num-1;i++)
printf("Path %d:vertex %d to vertex %d\n",i+1,path[i][0]+1,path[i][1]+1);
}
return 1;
}
Prim算法。
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2)
参考程序
//Prim 算法 读入顶点数(n)、边数(m)，边的起始点和权值 用邻接矩阵储存
//例如
//7 12 (7个顶点12条边)
//1 2 2
//1 4 1
//1 3 4
//2 4 3
//2 5 10
//3 4 2
//4 5 7
//3 6 5
//4 6 8
//4 7 4
//5 7 6
//6 7 1
#include <stdio.h>
#include <string.h>
int main()
{
int m , n;
int a[201][201] , mark[201] , pre[201] , dist[201];
int s , t , w;
int i , j , k , min , tot;
freopen("Prim.txt" , "r" , stdin);
//读入数据
memset(a , 0 , sizeof(a));
scanf("%d %d" , &n , &m);
for (i = 0; i < m; i ++)
{
scanf("%d %d %d" , &s , &t , &w);
a[s][t] = w; a[t][s] = w;
}
//赋初值
memset(mark , 0 , sizeof(mark));
memset(pre , 0 , sizeof(pre));
memset(dist , 9999 , sizeof(dist));
dist[1] = 0;
//Prim
for (i = 1; i <= n; i ++)
{
min = 9999; k = 0;
for (j = 1; j <= n; j ++)
if ((mark[j] == 0) && (dist[j] < min)) {min = dist[j]; k = j;}
if (k == 0) break;
mark[k] = 1;
for (j = 1; j <= n; j ++)
if ((mark[j] == 0) && (a[k][j] < dist[j]) && (a[k][j] > 0))
{
dist[j] = a[k][j];
pre[j] = k;
}
}
tot = 0;
for (i = 1; i <= n; i ++) tot += dist[i];
printf("%d\n" , tot);
return 0;
}
C. 谁能帮我画个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步。
明白了没？不明白再问我啊，希望对你有所帮助。
D. 什么是普利姆算法
Prim算法：是图的最小生成树的一种构造算法。
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，TV 是 WN 上最小生成树中顶点的集合，TE 是最小生成树中边的集合。显然，在算法执行结束时，TV=V，而 TE 是 E 的一个子集。在算法开始执行时，TE 为空集，TV 中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有 n-1条边为止。
如果看不懂还可以找一本数据结构的书看，这个算法挺简单的。
btw：其实你有空问，应该有空网络啊~网络就有了。懒得写，我还是直接从网络过来的~
E. Prim 算法和 Kruskal 算法
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
反证法 ：假设prim生成的不是最小生成树
1).设prim生成的树为G0
2).假设存在Gmin使得cost(Gmin)<cost(G0) 则在Gmin中存在<u,v>不属于G0
3).将<u,v>加入G0中可得一个环，且<u,v>不是该环的最长边(这是因为<u,v>∈Gmin)
4).这与prim每次生成最短边矛盾
5).故假设不成立，命题得证.
1).记Graph中有v个顶点，e个边
2).新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边
3).将原图Graph中所有e个边按权值从小到大排序
4).循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中
如果这条边连接的两个节点于图Graphnew中不在同一个连通分量中，添加这条边到图Graphnew中
归纳基础：
n=1，显然能够找到最小生成树。
归纳过程：
假设Kruskal算法对n≤k阶图适用，那么，在k+1阶图G中，我们把最短边的两个端点a和b做一个合并操作，即把u与v合为一个点v'，把原来接在u和v的边都接到v'上去，这样就能够得到一个k阶图G'(u,v的合并是k+1少一条边)，G'最小生成树T'可以用Kruskal算法得到。
我们证明T'+{<u,v>}是G的最小生成树。
用反证法，如果T'+{<u,v>}不是最小生成树，最小生成树是T，即W(T)<W(T'+{<u,v>})。显然T应该包含<u,v>，否则，可以用<u,v>加入到T中，形成一个环，删除环上原有的任意一条边，形成一棵更小权值的生成树。而T-{<u,v>}，是G'的生成树。所以W(T-{<u,v>})<=W(T')，也就是W(T)<=W(T')+W(<u,v>)=W(T'+{<u,v>})，产生了矛盾。于是假设不成立，T'+{<u,v>}是G的最小生成树，Kruskal算法对k+1阶图也适用。
由数学归纳法，Kruskal算法得证。
F. 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的评分