최소 신장 트리 편집하기 (부분)

==최소 신장 트리 알고리즘==
MST를 찾는 대표적인 알고리즘은 다음과 같다.
===[[크루스칼 알고리즘]] (Kruskal's Algorithm)===
크루스칼 알고리즘은 간선을 오름차순으로 정렬한 후,  사이클을 형성하지 않는 간선을 하나씩 선택하여 MST를 구성하는 방식이다.

'''알고리즘 과정:'''
#그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.
#사이클을 만들지 않는 간선을 선택하여 MST에 추가한다.
#V-1개의 간선이 선택될 때까지 반복한다.
'''슈도코드:'''<pre>
KruskalMST(graph):
    result = []
    edges = graph.edges sorted by weight
    disjointSet = new DisjointSet(graph.vertices)

    for each edge (u, v, weight) in edges:
        if disjointSet.find(u) != disjointSet.find(v):
            result.append((u, v, weight))
            disjointSet.union(u, v)

    return result
</pre>'''파이썬 코드:'''<syntaxhighlight lang="python">
class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        rootU = self.find(u)
        rootV = self.find(v)
        if rootU != rootV:
            self.parent[rootU] = rootV

def kruskal_mst(graph):
    edges = sorted(graph, key=lambda x: x[2])  # 간선 정렬 (u, v, weight)
    ds = DisjointSet(len(graph))
    mst = []

    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):
            ds.union(u, v)
            mst.append((u, v, weight))
    
    return mst
</syntaxhighlight>
===[[프림 알고리즘]] (Prim's Algorithm)===
프림 알고리즘은 시작 정점에서 출발하여,  MST에 포함되지 않은 정점 중 최소 가중치의 간선을 추가하는 방식이다.

'''알고리즘 과정:'''
#임의의 정점에서 시작하여 MST에 추가한다.
#MST에 연결된 간선 중 최소 가중치를 가지는 간선을 선택한다.
#선택된 간선을 MST에 추가한 후, 해당 간선의 도착 정점을 MST에 포함시킨다.
#모든 정점이 포함될 때까지 반복한다.
'''슈도코드:'''<pre>
PrimMST(graph, start):
    MST = []
    minHeap = PriorityQueue()
    visited = set()

    minHeap.push((0, start))  # 시작 정점

    while minHeap is not empty:
        weight, u = minHeap.pop()
        if u in visited:
            continue
        visited.add(u)
        MST.append(u)

        for v, w in graph[u]:
            if v not in visited:
                minHeap.push((w, v))

    return MST
</pre>'''파이썬 코드:'''<syntaxhighlight lang="python">
import heapq

def prim_mst(graph, start=0):
    mst = []
    visited = set()
    min_heap = [(0, start)]  # (가중치, 정점)
    
    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if u in visited:
            continue
        visited.add(u)
        mst.append(u)

        for v, w in graph[u]:
            if v not in visited:
                heapq.heappush(min_heap, (w, v))

    return mst
</syntaxhighlight>
설명	입력하는 내용	문서에 나오는 결과
기울임꼴	''기울인 글씨''	기울인 글씨
굵게	'''굵은 글씨'''	굵은 글씨
굵고 기울인 글씨	'''''굵고 기울인 글씨'''''	*굵고 기울인 글씨*