运行的最小生成树的时间？ （普里姆法） [英] Running time of minimum spanning tree? ( Prim method )

问题描述

我已经写了code，使用普里姆方法解决了MST。我看，这种实现（使用优先级队列）应该有O（E + VlogV）= O（VlogV），其中E是边和边了V号的数量，但是当我看到我的code它只是没有按'T外观，way.I将AP preciate，如果有人可以清除此为我说话。

要我来说，似乎运行时间是这样的：

while循环需要O（E）次（直到我们经过所有的边） 在该循环中，我们提取这需要O（包厢）时间在Q的元素。 而第二个内循环需要O（V）时间（尽管我们不运行这个循环每次 很显然，这将是运行V时代，因为我们必须添加所有顶点）

我的结论是，该运行时间为：O（E（LOGE + V））= O（E * V）

这是我的code：

 的#define p_int对＆LT; INT，INT＆GT;

INT N，M; // N  - 顶点NMB，男 - 边缘NMB
INT图表[100] [100] = {0}; //形容词。矩阵
布尔in_tree [100] = {假}; //如果一个节点，如果在MST
priority_queue＆LT; p_int，矢量＆lt; p_int＆gt;中更大＆其中; p_int＆GT; ＆GT; Q;
/ *
跟踪的内容是在MST树连接节点最小的边缘
外树的一个节点。对第一部分是边缘和的重量
第二是节点。我们不记得父节点beaceuse我们不需要它:-)
* /

诠释mst_prim（）
{
 Q.push（make_pair（0,0））;

 INT nconnected = 0;
 INT mst_cost = 0;
 而（nconnected n种）
 {
      p_int节点= Q.top（）; Q.pop（）;

      如果（in_tree [node.second] == FALSE）
      {
           mst_cost + = node.first;
           in_tree [node.second] = TRUE;

           的for（int i = 0; I＆LT; N ++ I）
                如果（图[node.second] [I]大于0＆安培;＆安培; in_tree [Ⅰ] ==假）
                     Q.push（make_pair（图表[node.second] [I]，i））的;

           nconnected ++;
      }
 }

 返回mst_cost;
}
 

解决方案

您可以用邻接表来加速解决方案（但不能用于密集图形），但即使是这样，你是不会得到O（V登录V ）没有一个斐波那契堆..

也许秩算法会更简单让你明白。它具有无优先级队列，你只需要边的数组排序一次。它是这样的基本上是：

• 将所有的边缘到一个数组和重量进行排序
• 迭代排序边缘，并为每个边缘连接节点i和j，检查是否i和j连接起来。如果是这样，跳过边缘，否则增加了边到MST。

，唯一的缺点就是要迅速地能够说，如果两个节点连接。为此，您使用的联盟 - 查找数据结构，它是这样的：

  INT T [MAX _＃_ OF_NODES]

INT的getParent（INT一）
{
  如果（T [一个] ==  -  1）返回一个;
  返回T [α] =的getParent（T [A]）;
}
团结无效（INT A，INT B）
{
  如果（RAND（）及1）
     T [A] = B;
  其他
     T [B] =一个;
}
 

在开始的时候，只是初始化T可所有的-1，然后你想了解每次当节点A和B连接，只是比较他们的父母 - 如果他们是一样的，他们是连接（这样的的getParent（A）==的getParent（B））。当你插入边缘MST，请务必更新联盟查找与联合起来（的getParent（A）的getParent（B））。

分析很简单，你排序的边缘，并使用了用友的需要O（1）迭代。因此，它是O（E LOGE + E）等于O（ē日志E）。

这是它; - ）

I have written a code that solves MST using Prim method. I read that this kind of implementation(using priority queue) should have O(E + VlogV) = O(VlogV) where E is the number of edges and V number of Edges but when I look at my code it simply doesn't look that way.I would appreciate it if someone could clear this up for me.

To me it seems the running time is this:

The while loop takes O(E) times(until we go through all the edges) Inside that loop we extract an element from the Q which takes O(logE) time. And the second inner loop takes O(V) time(although we dont run this loop everytime it is clear that it will be ran V times since we have to add all the vertices )

My conclusion would be that the running time is: O( E(logE+V) ) = O( E*V ).

This is my code:

#define p_int pair < int, int >

int N, M; //N - nmb of vertices, M - nmb of edges
int graph[100][100] = { 0 }; //adj. matrix
bool in_tree[100] = { false }; //if a node if in the mst
priority_queue< p_int, vector < p_int >, greater < p_int > > Q; 
/*
keeps track of what is the smallest edge connecting a node in the mst tree and
a node outside the tree. First part of pair is the weight of the edge and the 
second is the node. We dont remember the parent node beaceuse we dont need it :-)
*/

int mst_prim()
{
 Q.push( make_pair( 0, 0 ) );

 int nconnected = 0;
 int mst_cost = 0;
 while( nconnected < N )
 {
      p_int node = Q.top(); Q.pop();

      if( in_tree[ node.second ] == false )
      {
           mst_cost += node.first;
           in_tree[ node.second ] = true;

           for( int i = 0; i < N; ++i )
                if( graph[ node.second ][i] > 0 && in_tree[i]== false )
                     Q.push( make_pair( graph[ node.second ][i], i ) );

           nconnected++;
      }
 }

 return mst_cost;
}

解决方案

You can use adjacency lists to speed your solution up (but not for dense graphs), but even then, you are not going to get O(V log V) without a Fibonacci heap..

Maybe the Kruskal algorithm would be simpler for you to understand. It features no priority queue, you only have to sort an array of edges once. It goes like this basically:

• Insert all edges into an array and sort them by weight
• Iterate over the sorted edges, and for each edge connecting nodes i and j, check if i and j are connected. If they are, skip the edge, else add the edge into the MST.

The only catch is to be quickly able to say if two nodes are connected. For this you use the Union-Find data structure, which goes like this:

int T[MAX_#_OF_NODES]

int getParent(int a)
{
  if (T[a]==-1)return a;
  return T[a]=getParent(T[a]);
}
void Unite(int a,int b)
{
  if (rand()&1)
     T[a]=b;
  else
     T[b]=a;
}

In the beginning, just initialize T to all -1, and then every time you want to find out if nodes A and B are connected, just compare their parents - if they are the same, they are connected (like this getParent(A)==getParent(B)). When you are inserting the edge to MST, make sure to update the Union-Find with Unite(getParent(A),getParent(B)).

The analysis is simple, you sort the edges and iterate over using the UF that takes O(1). So it is O(E logE + E ) which equals O(E log E).

That is it ;-)

这篇关于运行的最小生成树的时间？ （普里姆法）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！