Generic Greedy Minimum Spanning Tree Algorithm 편집하기

'''Generic Greedy Minimum Spanning Tree Algorithm''' is a fundamental approach for constructing a Minimum Spanning Tree (MST) by iteratively selecting the smallest available edge that does not form a cycle. It is the basis for well-known MST algorithms such as Kruskal’s and Prim’s algorithms.
==Concept==
The generic greedy MST algorithm follows a greedy strategy:
#'''Initialize''' an empty set to store the MST edges.
#'''Sort''' all edges by weight (if not already sorted).
#'''Iterate''' through edges, selecting 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.
This algorithm ensures that the MST is constructed efficiently by always choosing the lowest-cost option available at each step.
==Algorithm==
The generic greedy MST algorithm can be described as:
#'''Initialize''' an empty set '''T''' for the MST.
#'''Sort''' all edges in non-decreasing order of weight.
#'''For each edge (u, v) in sorted order:'''
#*If adding (u, v) to '''T''' does not form a cycle, include it in the MST.
#'''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 the generic greedy MST algorithm:
#Select '''B - C (1)''' (smallest edge).
#Select '''B - D (2)''' (next smallest).
#Select '''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 the generic greedy MST algorithm using Kruskal's approach:<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 generic_greedy_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 = generic_greedy_mst(edges, 4)
print("Minimum Spanning Tree:", mst)
</syntaxhighlight>
==Properties==
*'''Greedy Approach'''
**Always selects the smallest available edge at each step.
*'''Cycle Avoidance'''
**Ensures no cycles are formed, maintaining the tree structure.
*'''Efficiency'''
**Runs in O(E log E) time complexity when implemented with a priority queue or sorting.
==Applications==
*'''Network Design'''
**Used in designing efficient communication, power, and transportation networks.
*'''Approximation Algorithms'''
**Forms the basis for solving hard problems like the Traveling Salesman Problem (TSP).
*'''Cluster Analysis'''
**Used in hierarchical clustering techniques.
==See Also==
*[[Minimum Spanning Tree]]
*[[Kruskal’s Algorithm]]
*[[Prim’s Algorithm]]
*[[Greedy Algorithm]]
*[[Graph Theory]]