Kruskal’s Algorithm 편집하기

'''Kruskal’s Algorithm''' is a greedy algorithm used to find a '''Minimum Spanning Tree (MST)''' for a weighted, connected, and undirected graph. It works by sorting all edges by weight and adding them one by one while ensuring no cycles are formed.
==Concept==
Kruskal’s Algorithm follows these principles:
#'''Sort all edges''' in non-decreasing order of weight.
#'''Select the smallest edge''' that does not form a cycle.
#'''Repeat''' until the MST contains exactly (N - 1) edges, where N is the number of vertices.
The algorithm uses the '''Union-Find''' data structure to efficiently check and merge connected components.
==Algorithm Steps==
#'''Initialize''' an empty set for the MST.
#'''Sort''' all edges by weight.
#'''Iterate''' through edges:
#*If the edge connects two different components, add it to the MST.
#*Merge the components using the Union-Find data structure.
#'''Repeat''' until the MST contains (N - 1) edges.
==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
|}Applying Kruskal’s Algorithm:
#Sort edges by weight: '''B - C (1), B - D (2), A - C (3), A - B (4), C - D (5)'''.
#Add '''B - C (1)''' (smallest edge).
#Add '''B - D (2)''' (next smallest).
#Add '''A - C (3)''' (next smallest, does not form a cycle).
#The MST is complete with edges '''B - C, B - D, A - C'''.
Total MST weight: '''1 + 2 + 3 = 6'''
==Implementation==
A simple implementation of Kruskal’s Algorithm in Python:<syntaxhighlight lang="python">
class UnionFind:
    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):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            self.parent[root_u] = root_v

def kruskal_mst(edges, n):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst = []
    
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
        if len(mst) == n - 1:
            break

    return mst

edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 5)]
mst = kruskal_mst(edges, 4)
print("Minimum Spanning Tree:", mst)
</syntaxhighlight>
==Properties==
*'''Greedy Algorithm'''
**Always selects the smallest available edge at each step.
*'''Cycle Prevention'''
**Uses Union-Find to prevent cycles in the MST.
*'''Efficiency'''
**Runs in O(E log E) time complexity due to sorting.
==Applications==
*'''Network Design'''
**Used to design cost-efficient communication and transportation networks.
*'''Cluster Analysis'''
**Forms the basis of some hierarchical clustering techniques.
*'''Approximation Algorithms'''
**Helps solve NP-hard problems like the Traveling Salesman Problem.
==See Also==
*[[Minimum Spanning Tree]]
*[[Prim’s Algorithm]]
*[[Borůvka’s Algorithm]]
*[[Greedy Algorithm]]
*[[Graph Theory]]

*