Prim's Algorithm 편집하기

'''Prim's Algorithm''' is a greedy algorithm used to find a Minimum Spanning Tree (MST) for a weighted, connected, and undirected graph. The algorithm builds the MST by starting from an arbitrary vertex and iteratively adding the smallest edge that connects a vertex in the tree to a vertex outside the tree.
==Definition==
Given a weighted, connected, undirected graph '''G = (V, E)''', Prim's Algorithm constructs a spanning tree '''T''' such that the total weight of the edges in '''T''' is minimized. At each step, the algorithm selects the edge with the lowest weight that connects a vertex in '''T''' to a vertex not yet in '''T'''.
==Concept==
Prim's Algorithm works on the following principles:
#'''Initialization:''' Start with an arbitrary vertex; mark it as part of the MST.
#'''Edge Selection:''' Among all edges that connect vertices in the MST to those not in the MST, select the edge with the smallest weight.
#'''Expansion:''' Add the selected edge and the new vertex to the MST.
#'''Repeat:''' Continue the process until all vertices are included in the MST.
==Algorithm Steps==
#'''Initialize''' the MST with a starting vertex.
#'''While''' the MST does not contain all vertices:
#*Find the edge with the minimum weight that connects a vertex in the MST to a vertex outside the MST.
#*Add the selected edge and the corresponding vertex to the MST.
#'''End While'''
==Example==
Consider the following weighted graph:
{| class="wikitable"
!Vertex Pair!!Edge Weight
|-
|A - B||4
|-
|A - C||3
|-
|B - C||1
|-
|B - D||2
|-
|C - D||5
|}One possible execution of Prim's Algorithm starting at vertex A:
#Start with vertex A.
#The available edges are A - B (4) and A - C (3). Choose A - C (3) because 3 is the smallest.
#Now the MST contains A and C. The available edges are A - B (4), C - B (1), and C - D (5). Choose C - B (1).
#MST now contains A, C, and B. The remaining available edge is B - D (2) and C - D (5). Choose B - D (2).
#The MST now includes all vertices with the edges A - C (3), C - B (1), and B - D (2). The total weight is 3 + 1 + 2 = 6.
==Implementation==
A simple implementation of Prim's Algorithm in Python:<syntaxhighlight lang="python">
import heapq

def prim_mst(graph, start):
    mst = []
    visited = set([start])
    # Priority queue: (edge_weight, from_vertex, to_vertex)
    edges = [(weight, start, to) for to, weight in graph[start].items()]
    heapq.heapify(edges)

    while edges:
        weight, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, weight))
            for next_to, next_weight in graph[to].items():
                if next_to not in visited:
                    heapq.heappush(edges, (next_weight, to, next_to))
    return mst

# Example graph represented as an adjacency dictionary
graph = {
    'A': {'B': 4, 'C': 3},
    'B': {'A': 4, 'C': 1, 'D': 2},
    'C': {'A': 3, 'B': 1, 'D': 5},
    'D': {'B': 2, 'C': 5}
}

mst = prim_mst(graph, 'A')
print("Minimum Spanning Tree:", mst)
</syntaxhighlight>
==Advantages==
*'''Greedy Approach''' – Always selects the smallest available edge.
*'''Efficient for Dense Graphs''' – Performs well when there are many edges.
*'''Simple Implementation''' – Easy to understand and implement.
==Limitations==
*'''Requires a Connected Graph''' – Prim's Algorithm works only on connected graphs.
*'''Potential for High Memory Usage''' – Maintaining a priority queue can require extra memory in very large graphs.
==Applications==
*'''Network Design''' – Used in designing efficient communication, transportation, or power networks.
*'''Cluster Analysis''' – Forms the basis for some hierarchical clustering techniques.
*'''Approximation Algorithms''' – Serves as a component in algorithms for solving NP-hard problems like the Traveling Salesman Problem.
==See Also==
*[[Minimum Spanning Tree]]
*[[Kruskal’s Algorithm]]
*[[Borůvka’s Algorithm]]
*[[Greedy Algorithm]]
*[[Graph Theory]]
[[Category:Algorithm]]
설명	입력하는 내용	문서에 나오는 결과
기울임꼴	''기울인 글씨''	기울인 글씨
굵게	'''굵은 글씨'''	굵은 글씨
굵고 기울인 글씨	'''''굵고 기울인 글씨'''''	*굵고 기울인 글씨*