Время работы минимального связующего дерева? (Прим метод) - PullRequest
Новая
       23

Время работы минимального связующего дерева? (Прим метод)

3 голосов
/ 19 ноября 2009

Я написал код, который решает MST, используя метод Prim. Я читал, что реализация такого типа (с использованием очереди приоритетов) должна иметь O (E + VlogV) = O (VlogV), где E - это число ребер, а V - число ребер, но когда я смотрю на свой код, он просто не выглядит таким образом. Я был бы признателен, если бы кто-то мог прояснить это для меня.

Мне кажется, что время работы таково:

Цикл while занимает O (E) раз (пока мы не пройдем все ребра) Внутри этого цикла мы извлекаем элемент из Q, который занимает время O (logE). И второй внутренний цикл занимает время O (V) (хотя мы не запускаем этот цикл каждый раз ясно, что оно будет выполнено V раз, так как мы должны добавить все вершины)

Мой вывод: время работы: O (E (logE + V)) = O (E * V).

Это мой код: 

#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;
}

Ответы [ 2 ]

2 голосов
/ 09 января 2010

Вы можете использовать списки смежности, чтобы ускорить решение (но не для плотных графов), но даже тогда вы не получите O (V log V) без кучи Фибоначчи.

Возможно, алгоритм Крускала будет проще для вас понять. Он не имеет очереди приоритетов, вам нужно только один раз отсортировать массив ребер. В основном это выглядит так:

  • Вставить все ребра в массив и отсортировать их по весу
  • Переберите отсортированные ребра, и для каждого ребра, соединяющего узлы i и j, проверьте, соединены ли i и j. Если они есть, пропустите край, иначе добавьте край в MST.

Единственный улов - быстро определить, связаны ли два узла. Для этого вы используете структуру данных Union-Find, которая выглядит следующим образом: 

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;
}

В начале, просто инициализируйте T для всех -1, а затем каждый раз, когда вы хотите узнать, связаны ли узлы A и B, просто сравните их родителей - если они одинаковые, они связаны (как это getParent(A)==getParent(B)). Когда вы вставляете ребро в MST, обязательно обновите Union-Find с помощью Unite(getParent(A),getParent(B)).

Анализ прост: вы сортируете ребра и перебираете, используя UF, который принимает O (1). Таким образом, O (E logE + E) равно O (E log E).

Вот и все; -)

1 голос
/ 19 ноября 2009

Раньше мне не приходилось иметь дело с алгоритмом, но то, что вы реализовали, не соответствует алгоритму, как описано в Википедии . Алгоритм там работает следующим образом.

  1. Но все вершины в очередь. O (V)
  2. Пока очередь не пуста ... O (V)
    1. Возьмите край с минимальным весом из очереди. O (журнал (V))
    2. Обновление весов смежных вершин. O (E / V), это среднее количество смежных вершин.
    3. Восстановить структуру очереди. O (журнал (V)) * * 1014

Это дает 

        O(V) + O(V) * (O(log(V)) + O(V/E))
      = O(V) + O(V) * O(log(V)) + O(V) * O(E / V)
      = O(V) + O(V * log(V)) + O(E)
      = O(V * log(V)) + O(E)

именно то, что ожидаешь.

...