최소 스패닝 트리 실행 시간? (Prim 메서드)

Question

Prim 메서드를 사용하여 MST를 해결하는 코드를 작성했습니다. 나는 (우선 순위 큐를 사용하는) 이런 종류의 구현은 O (E + VlogV) = O (VlogV)를 가져야한다는 것을 읽었다. 여기서 E는 가장자리의 수와 V 수의 가장자리이지만, 내 코드를 보면 단순히 보이지 않는다. 그런 식으로. 누군가 나를 위해 이것을 정리해 주면 고맙겠습니다. 나에게

실행 시간이 보인다 :

우리가 O 걸리는 Q에서 요소를 추출하는 루프 내부 (우리가 모든 가장자리를 통과 할 때까지) 루프는 O (E) 시간을 소요하면서 (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은 더 쉽게 이해할 수 있습니다. 우선 순위 대기열이 없으므로 가장자리 배열을 한 번만 정렬하면됩니다. 배열로

• 삽입 모든 모서리를 무게에 의해 분류 가장자리를 통해
• 으로 반복 그들을 분류하고, i와 j가 연결되어있는 경우 노드를 연결하는 각 에지 i와 j는 확인 : 그것은이 기본적으로 같이 간다. 그럴 경우 가장자리를 건너 뛰고 MST에 가장자리를 추가하십시오.

두 노드가 연결되어 있는지를 신속하게 알 수 있습니다.단지 모든 -1 T를 초기화 한 다음 원하는 때마다 노드 A와 B가 있는지 확인하기 위해, 처음에는

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

:이를 위해이 같이가는 연합 찾기 데이터 구조를 사용 연결되어 있으면 부모를 비교하면됩니다. 동일하면 연결됩니다 (예 : getParent(A)==getParent(B)). MST에 가장자리를 삽입하는 경우 Union-Find를 Unite(getParent(A),getParent(B))으로 업데이트해야합니다.

분석은 간단합니다. 가장자리를 정렬하고 O (1)이 필요한 UF를 사용하여 반복합니다. 따라서 O (E log E + 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) 

을 제공합니다.