prim의 알고리즘 설명

Question

최소 힙 기반 우선 순위 큐를 사용하여 Prim의 알고리즘을 구현해야합니다. 내 그래프 아래 undirected 인접리스트와 정점 A, B, C 및 D를 포함하는 경우 ...

A -> B,4 -> D,3 
B -> A,4 -> C,1 -> D,7 
C -> B,1 
D -> B,7 -> A,3 

거친 그래프 [그것은 (정점 이름 중량 인접 정점)으로 분류된다]

A-4-B-1-C 
| /
3 7 
|/
D 

우선 순위 대기열은 어떤 모양입니까? 나는 무엇을 넣어야할지 모른다. 나는 모든 것을 넣어야합니까? 나는 A B C와 D를 넣어야합니까? 나는 단서가 없으며 대답을 정말로 원할 것입니다.

Answer 1

Prim's: grow the tree by adding the edge of min weight with exactly one end in the tree. 
The PQ contains the edges with one end in the tree. 
Start with vertex 0 added to tree and add all vertices connected to 0 into the PQ. 
DeleteMin() will give you the min weight edge (v, w), you add it to the MST and add all vertices connected to w into the PQ. 

is this enough to get you started? 
--- 
so, in your example, the in the first iteration, the MST will contain vertex A, and the PQ will contain the 2 edges going out from A: 
A-4-B 
A-3-D 

Answer 2

여기의 꼼꼼한 알고리즘입니다 :

Choose a node. 
Mark it as visited. 
Place all edges from this node into a priority queue (sorted to give smallest weights first). 
While queue not empty: 
    pop edge from queue 
    if both ends are visited, continue 
    add this edge to your minimum spanning tree 
    add all edges coming out of the node that hasn't been visited to the queue 
    mark that node as visited 

그래서 귀하의 질문에 대답하기 위해, 당신은 하나 개의 노드에서의 가장자리를 넣어.

우선 순위 대기열에 모든 가장자리를 넣으면 Kruskal의 알고리즘이 있으며 최소 스패닝 트리에도 사용됩니다.

실행 시간을 그래프로 표현하는 방법에 따라 다릅니다. 인접리스트는 피보나치 힙 (fibonacci heap)을 사용하지 않는 한 Kruskal과 Prim의 복잡성 O (E log E)를 O (E log V)로 만듭니다.이 경우 O (E + V log V)를 얻을 수 있습니다.

Answer 3

정점에 가중치를 할당 할 수 있습니다. 그런 다음이 가중치에 따라 우선 순위 대기열을 사용하십시오. 이 위키에서 참조입니다 : http://en.wikipedia.org/wiki/Prim's_algorithm

MST-PRIM (G, w, r) { 
for each u ∈ G.V 
u.key = ∞ 
u.parent = NIL 
r.key = 0 
Q = G.V 
while (Q ≠ ø) 
u = Extract-Min(Q) 
for each v ∈ G.Adj[u] 
if (v ∈ Q) and w(u,v) < v.key 
v.parent = u 
v.key = w(u,v) 
} 

Q 당신의 우선 순위 큐 될 것입니다. 구조체를 사용하여 정점의 정보를 보유 할 수 있습니다.