标签: prims-algorithm

我使用的伪代码：

for all V vertices: visited[n]=0

pick any vertex r from graph and set visited[r]=1

For all edges e incident to r
PQ.insert()

while(PQ is not empty)//line 1
  f=PQ.min()//f(r,s) is such that visited[s]=0
  for all edges e(s,t) incident to s//line 2
     if(visited[t]==0)
        PQ.insert(e);//line 3
     else
        PQ.delete(e);//line 4
  visited[s]=1;
end while;

根据我的理解：

• 第 1 行：执行V-1次数。
• 第 2 行：所有顶点的度数总和时间……就是2E时间

对于每一行 2：第 3 行和第 4 行需要log E时间，因为我们正在PQ逐条添加/删除所有边。

所以总time= V-1+2E.logE=E.log E

但是书上说是的 …

正如我的问题所说,我想知道为什么我们在Prim的算法中使用优先级队列？它如何使我们无法使用天真的方式(是的,我听说过它,但不知道为什么).

如果有人能逐步解释邻接列表,我会很高兴.我正在使用Cormen的书.

伪代码:

Prim(G,w,r) //what is w (weight?) and r?
  For each u in V[G]
    do key[u] ? ? // what is key?
       ?[u] ? NIL  
  key[r] ? 0
  Q ? V[G]  
  While Q ? Ø
    do u ? EXTRACT-MIN(Q)
       for each v in Adj[u]
            if v is in Q and w(u,v) < key[v]
                 then ?[v] ? u
                       key[v] ? w(u,v)

我想使用std :: vector然后std :: make_heap(); 作为存储边缘的优先级队列.

有人可以向我解释为什么使用相邻矩阵的Prim算法导致时间复杂度为？O(V2)

Prim 算法和 Kruskal 算法都生成最小生成树。根据 cut 属性，这些算法的树的总成本将是相同的，但是这两种算法是否有可能以相同的总成本给出不同的 MST，因为我们在面临多个选择时按字母顺序选择它. 例如，我们比较 max(source,dest)，对于边 A->B 和 B->C，我们比较 A 中的 A->B 和 B 中的 B->C。

谢谢

我正在尝试实现Prim的算法,为此我需要为优先级队列使用reduceKey方法(以更新优先级队列中的键值).我可以在STL优先级队列中实现吗？

如果它有帮助,这是我遵循的算法:

• 对于图G中的每个顶点u
  • 将你的关键设置为INFINITY
  • 将u的父级设置为NIL
• 将源顶点的键设置为0
• en-queue to priority queue Q图中的所有顶点,如上所示
• 而Q不是空的
  • 在Q中使用最低键弹出顶点u
  • 对于你做的每个相邻顶点v
    • if(v仍在Q中)和(key(u)+ weight-function(u,v)<key(v))然后
      • 设定你是v的父母
      • 更新v键等于键(u)+权重函数(u,v) //这部分给我带来问题,因为我不知道如何在优先级队列中实现reduceKey

我写了这段代码来绘制随机图.我一直试图找到如何在图中选择一条线以便我可以应用prim的算法,因为我选择了一行并查看它们是否找到了最小的树.

 function draw(n,rep){
        var cvs=document.getElementsByTagName('canvas')[0];   
        /** 
         * @type CanvasRenderingContext2D 
         **/
        var ctx=cvs.getContext('2d');
        ctx.beginPath();
        var randomX=[];
        var randomY=[];
        ctx.lineWidth=2;
        ctx.font  = '3'+' Arial';
        var weights=[];
        var lastRandomx=Math.random()*200;
        var lastRandomy=Math.random()*200;
        for (var i = 0; i <n ; i++) {
            var cwidth = cvs.width;
    var cheight = cvs.height;                
            randomX[i] = Math.random()*cwidth*2/3;
    randomY[i] = Math.random()*cheight*2/3;
            weights[i]=Math.round(Math.random()*20);                        
            ctx.fillRect(randomX[i],randomY[i],5,5);        
    ctx.moveTo(lastRandomx,lastRandomy);
    ctx.lineTo(randomX[i],randomY[i]);               
            lastRandomx=randomX[i];
            lastRandomy=randomY[i];
        }
        for (var i = 0; i < rep; i++) {
            var rand=Math.round(rep*Math.random());
            ctx.lineTo(randomX[rand],randomY[rand]);
        } 
        ctx.closePath();
        ctx.stroke();
};  

我在stackoverflow中发现了这个并没有多大帮助.如何选择在HTML5 Canvas上绘制的线条？.我想知道是否有预编写的代码,所以我不需要从头开始编写代码. …

我一整天都在努力理解Dijkstra的算法并且没有显着的结果.我有一个城市矩阵和他们的距离.我想要做的是给出一个原点和一个目的地点,找到城市之间的最短路径.

例:

     __0__ __1__ __2__ 
 0  |  0  | 34  |  0  |
    |-----|-----|-----|
 1  | 34  |  0  | 23  |
    |-----|-----|-----|
 2  |  0  | 23  |  0  |
     ----- ----- -----

我开始想知道是否还有其他方法可以解决这个问题.如果我从原点开始应用Prim算法然后遍历整个树,直到找到目标点,该怎么办？

在您已经知道任何给定重量的最小值的情况下,如何修改prim算法？例如,如果图形由边缘权重0和1组成,那么如何使prim的算法更快？

我查看了以下prim的算法(为了创建最小生成树),我不确定下面代码中的输入值是什么,我认为G当然是发送的图形(邻接矩阵或列表图)我认为值s是起点应该在哪里？此外,如果它是开始,那么您将以何种方式将起始值发送到以下算法？:

from heapq import heappop, heappush

def prim(self, G, s): 
    P, Q = {}, [(0, None, s)] 
    while Q: 
        _, p, u = heappop(Q) 
        if u in P: continue 
        P[u] = p 
        for v, w in G[u].items(): 
            heappush(Q, (w, u, v)) 
    return P 

任何帮助将不胜感激,谢谢!

可能的重复：
克鲁斯卡尔 vs 普里姆

你什么时候会使用 Kruskal 算法而不是 Prim 算法来找到最小生成树？哪种输入图和节点更适合每种类型？在什么情况下，在空间和时间方面使用其中之一更有效？

他们的特定输入是否使一个比另一个好得多？

我在C(www.bubblellicious.es/prim.tar.gz)中实现了Prim的算法,但我只是想知道如何将其转换为Kruskal的算法.

看起来它们非常相似,但我无法想象如何将旧代码修改为新代码.如果你给出一些建议或东西,这将是美味的.我知道这很简单,但我仍然是C编程中的n00b ...

我正在尝试使用STL在C++中实现Prim的MST算法.

但是对于下面的程序,它似乎进入了一个无限循环.然后退出并出错.

Prim的MST算法的伪代码;

我的代码:

#include<algorithm>
#include<vector>
#include<iostream>
#include<queue>
using namespace std;

typedef vector<int>         vi;
typedef pair<int,int>       ii;
typedef vector<ii>          vii;

#define REP(i,a,b)  for(int i=int(a);i<b;i++)
#define TRvii(c,it) for(vii::iterator it=(c).begin();it!=(c).end();it++)

#define INF 2000000000

void Prims(int V, int s, vector<vii> &AdjList)
{
    vector<int> dist(V,INF);
    dist[s] = 0;
    priority_queue<ii,vector<ii>,greater<ii> > pq; 
    pq.push(ii(0,s));

    REP(i,1,V) pq.push(ii(i,INF));

    bool inPriorityQueue[V];
    REP(i,0,V) inPriorityQueue[i] = true;

    while(!pq.empty())
    {
        ii top = pq.top(); pq.pop();
        int d = top.first,u = top.second;

        inPriorityQueue[u] = false;

        TRvii(AdjList[u],it)
        {
            int v = it->first, weight_u_v = …