2020-2021:teams:namespace:最小生成树

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:namespace:最小生成树 [2020/07/10 17:32]
great_designer [Prim算法（反圈法）]
+++ 2020-2021:teams:namespace:最小生成树 [2020/07/10 17:37] (当前版本)
great_designer [Prim算法（反圈法）]
@@ 行 61: / 行 61: @@
 第三步：若在某一步，反圈为空集，则图中没有支撑树。若在某一步，已经选择了图的所有顶点，则所有被选择的边构成最小树，算法终止。
-可以看一个程序示例：
+因此可以用优先队列的STL来维护割集（反圈），方法是每次选元素后判断，新堆顶不在割集中就pop掉这个元素。
-<code C++>
+注意，我们要实现最小堆。默认优先队列是最大堆。因此要想办法颠倒过来。
-//weights为权重数组、n为顶点个数、src为最小树的第一个顶点、edge为最小生成树边
-void Prim(int weights[][512], int n, int src, int edges[])
-{
-    int minweight[512],min;
-    int i,j,k;
-    for(i=0;i<n;i++)//初始化相关数组
-    {
-        minweight[i]=weights[src][i];  //将src顶点与之有边的权值存入数组
-        edges[i]=src;  //初始化第一个顶点为src
-    }
-    minweight[src]=0;   //将第一个顶点src顶点加入生成树
-    for(i=1;i<n;i++)
-    {
-        min=32767;
-        for(j=0,k=0;j<n;j++)
-        {
-            if(minweight[j]!=0&&minweight[j]<min)//在数组中找最小值，其下标为k
-            {
-                min=minweigth[j];
-                k=j;
-            }
-        }
-        minweight[k]=0;  //找到最小树的一个顶点
-        for(j=0;j<n;j++)
-        {
-             if(minweight[j]!=0;&&weights[k][j]<minweight[j] )
-             {
-                  minweight[j]=weights[k][j];    //将小于当前权值的边(k,j)权值加入数组中
-                  edges[j]=k;   //将边(j,k)信息存入边数组中
-             }
-         }
-    }
-}
-</code>
-上面这个版本没有被优化。若想看优化，可以参照下面两个版本。
 <code C++>

2020-2021/teams/namespace/最小生成树.1594373531.txt.gz · 最后更改: 2020/07/10 17:32 由 great_designer