Время работы минимального остовного дерева? (Метод Prim)

Question

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

Мне кажется, время работы заключается в следующем:

в то время как цикл занимает 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; 
} 

Answer 1

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

Может быть, Kruskal algorithm было бы проще для вас понять. Он не имеет очереди с приоритетом, вам нужно только отсортировать массив ребер. Это идет как это в основном:

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

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

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, а затем каждый раз, когда вы хотите, чтобы выяснить, если узлы А и В связанные, просто сравните их родителей - если они одинаковые, они связаны (например, это getParent(A)==getParent(B)). Когда вы вставляете ребро в MST, обязательно обновите Union-Find с помощью Unite(getParent(A),getParent(B)).

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

То есть это ;-)

Answer 2

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

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

Это дает

 
     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) 

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