求分析，关于Prim算法的实现过程？

Question

Prim算法的实现过程？精髓部分

Answer 1

贪心过程.首先,把图中的点分成两种,已连通和未连通的,我把它们分别称为"黑"和"白"点.一开始时,图中全是白点,没有黑点.算法的第一步,随机选出一个白点,染成黑色.然后开始一个重复的过程:从当前图的边中寻找这样的一些边:它的其中一个端点是黑点,而另一个端点是一个白点. 我们可以把这类边称为"可扩展边". 然后算法需要从所有的可扩展边之中选出权值最小的一条.把这条可扩展边加入生成树之中,且把这条边的白色端点染成黑色.重复这个过程,直到全部的节点都为黑色.算法可以优化的地方是,在选择权值最小的可行边时可以使用堆.

Answer 2

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。