prim算法模板

⑴ 请教prim算法正确性的证明

为了减少不必要的麻烦，可以不妨设图中所有边的权重都不同，这样最小生成树是唯一的
然后直接用反证法就行了
如果Prim算法得到G，而最小生成树是T
设在生成G的过程中第一次产生的不在T中的边是e，而在G中去掉e得到的两个连通分支记为V1和V2，那么e连接了V1和V2

把e加入T之后会出现环，在这个环里面V1的顶点和V2的顶点至少还被另一条边f连接（否则T本身就不连通了），由Prim算法的贪心策略可知e比f权重低，那么在T里面把f换成e可得一个总权重更小的生成树，与T的最小性矛盾

（因为最小生成树的总权重的边的权重的连续函数，对于有权重重复出现的情况可以利用连续性取极限，这样即使最小生成树不唯一仍然可以保证Prim算法生成的树具有最小权重）

⑵ Prim算法的实现过程

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

重复这个过程,直到全部的节点都为黑色.

算法可以优化的地方是,在选择权值最小的可行边时可以使用堆.

⑶ prim算法是什么

prim算法是：图论中的一种算法。

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

通过邻接矩阵图表示的简易实现中，找到所有最小权边共需O（V）的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为O(ElogV)，其中E为连通图的边数，V为顶点数。如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为O(E+VlogV)，这在连通图足够密集时（当E满足Ω（VlogV）条件时），可较显着地提高运行速度。

⑷ 谁能帮我画个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步。

明白了没？不明白再问我啊，希望对你有所帮助。

⑸ Prim算法的题怎么做

按产生最小生成树边的次序
<2,4>, <2, 6>, <6, 1>, <1, 3>, <4, 5>

⑹ 用prim算法从下面图中的顶点1开始逐步构造最小代价生成树

⑺ 数学建模用prim算法求解最小树模型时，怎样构建模型

用 0-1规划模型

⑻ prim算法

指的是最小生成树的一种算法么，和dijstra算法思想接近，
但是第一步是先将权最小的边的两个点加入以确定set。
然后一步步
从un set加入与这个集合距离最短的点,然后更新这个set到unset的每一点的最短距离，
直到全部加入

⑼ 数据结构（prim算法）

开始时将v1加入U后，更新ee中的值应该是0 6 1 2 无穷 无穷；
将v3加入U后，更新ee中的值应该是0 5 0 2 6 4；
怎么会出现你说的0 6 0 5 无穷无穷的情况呢？
for(j = 0;j < G.vexnum;j++)中不是有条件判断么，要在k到j的距离小于ee[j]的value值时才会更新ee[j]啊。

⑽ Prim算法c语言表示，求源程序。。。。。。。。。

我原来自己写的模板

//朴素prim算法
//复杂度 O(n^2)
//flag[SIZE] 顶点标记
//mindis[SIZE] 当前最短距离
//dis[SIZE][SIZE] 任意两点间距离 邻接矩阵表示

int prim()
{
memset(flag,false,sizeof(bool)*(n+1));
flag[0] = true;
for(int i=1;i<n;i++)
mindis[i] = dis[0][i];
int ans = 0;
for(int i=1;i<n;i++)
{
int min = 10000;
int pos;
for(int j=1;j<n;j++)
{
if(!flag[j] && min > mindis[j])
{
min = mindis[j];
pos = j;
}
}
ans+=min;
flag[pos] = true;
for(int j=1;j<n;j++)
{
if(!flag[j] && mindis[j] > dis[pos][j])
mindis[j] = dis[pos][j];
}
}
return ans;
}