[알고리즘] 최소 신장 트리 (feat.크루스칼 알고리즘)

---

<목차>

1. 최소 신장 트리 알고리즘

2. Disjoint Set (Union-Find, Union-by-Rank)

3. 크루스칼 알고리즘(Kruskal Algorithm)

---

1. 최소 신장 트리 알고리즘

: Minimum Spanning Tree(MST).

 

* Spanning Tree : 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 

 

최소 신장 트리란 Spanning Tree 중 사용된 간선들의 가중치의 합이 최소인 트리입니다. 

신장 트리에서 최소 신장 트리를 찾는 알고리즘에는 크루스칼 알고리즘, 프림 알고리즘이 있습니다.

 

* 최소 신장 트리의 특징

1) 간선의 가중치의 합이 최소여야 함

2) n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 함

3) 사이클이 포함되어서는 안 됨

4) 그래프의 모든 노드를 포함해야 함

 

(ex) 신장트리, 최소신장트리 예시

출처 :&amp;nbsp;https://ratsgo.github.io/data%20structure&amp;amp;algorithm/2017/11/28/MST/

---

2. Disjoint Set (Union-Find, Union-by-rank)

크루스칼 알고리즘에 들어가기에 앞서 Disjoint Set, Union-Find, Union-by-Rank 의 개념을 알아보도록 하겠습니다.

최소 신장 트리 알고리즘은 사이클이 포함되어서는 안 된다는 조건이 들어있는데요, Disjoint Set, Union-Find, Union-by-rank 방법을 이용해 이를 구현합니다.

 

1) Disjoint Set : 서로소 집합. 서로 공통 원소가 없는 집합을 Disjoint Set 이라 합니다.

 

Disjoint Set은 각각의 노드가 부모 노드를 가리키는 포인터를 갖고 있고, 그 노드가 속한 집합을 찾기 위해 부모 노드를 타고 올라가 루트 노드를 찾습니다. 이 때, 하나의 노드 집합에 여러 노드가 일렬로 연결되는걸 막기 위한 방법이 Union-by-rank 방법입니다. 여러 노드가 전부 일렬로 연결되면 O(n)의 시간이 걸리는데, 이를 방지하면 탐색 시간을 O(logn)으로 줄일 수 있습니다.

 

2) Union-by-rank : 각 트리의 높이(rank)를 기억한 다음, 두개의 트리를 비교해 높이가 작은 트리를 높이가 큰 트리에 붙이는 방법입니다. 

Union-by-rank 예시. 출처 :&nbsp;https://fenslett.tistory.com/entry/Union-Find-Disjoint-Set-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C

 

3) Union-Find 알고리즘 : 트리 구조를 사용해 Disjoint Set 을 표현하는 알고리즘. 

Union-Find 알고리즘은 다음과 같은 3개의 단계를 거칩니다.

3-1) 초기화 :  n개의 원소를 개별 집합으로 만듬

public void makeSet(string node)
{
    parent.Add(node, node);
    rank.Add(node, 0);
}

 

3-2) Union(합치기) : 두 원소 a, b가 속한 서로 다른 두 집합을 하나의 트리로 만듬. 그 과정에서 Union-by-rank 방법을 사용

public void union(string node1, string node2)
{
    string root1 = find(node1);
    string root2 = find(node2);

    //랭크가 더 높은 쪽을 루트로 삼음
    if ((int)rank[root1] > (int)rank[root2]) parent.Add(root2, root1);
    else
    {
        parent.Add(root1, root2);
        if ((int)rank[root1] == (int)rank[root2]) 
            rank.Add(root2, (int)rank[root2] + 1);
    }
}

 

3-3) Find(찾기) : 서로의 루트 노드가 같은지 확인할 때 쓰는 메서드

public string find(string node)
{
    if ((string)parent[node] != node) 
        parent[node] = find((string)parent[node]);
    return (string)parent[node];
}

 

---

3. 크루스칼 알고리즘(Kruskal Algorithm)

: 탐욕 알고리즘. 모든 간선의 가중치를 작은 순서대로 정렬하고, 작은 간선부터 양 끝의 두 정점을 비교해서 연결하는 알고리즘입니다. 

 

* 탐욕 알고리즘

https://geukggom.tistory.com/173

 

1) Edge 만들기

public class Edge : IComparable
{
    public int weight; //가중치
    public string node1;
    public string node2;
    public Edge(int weight, string node1, string node2)
    {
        this.weight = weight;
        this.node1 = node1;
        this.node2 = node2;
    }

    public int CompareTo(object obj)
    {
        Edge edge = obj as Edge;
        return edge.weight;
    }

    public string myData()
    {
        return this.weight + ":" + this.node1 + "," + this.node2;
    }
}

 

2) 그래프 생성

예시 그래프 :

출처 :&nbsp;https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

List<Edge> edgeList = new List<Edge>();
List<string> nodeList = new List<string>() { "A", "B" , "C" , "D" , "E" , "F" , "G" };
edgeList.Add(new Edge(29, "A", "B"));
edgeList.Add(new Edge(10, "A", "F"));
edgeList.Add(new Edge(16, "B", "C"));
edgeList.Add(new Edge(15, "B", "G"));
edgeList.Add(new Edge(18, "D", "G"));
edgeList.Add(new Edge(12, "C", "D"));
edgeList.Add(new Edge(25, "G", "E"));
edgeList.Add(new Edge(22, "D", "E"));
edgeList.Add(new Edge(27, "E", "F"));

 

2-1) 가중치 순서대로 정렬

edgeList.Sort();
for (int i = 0; i < edgeList.Count; i++)
{
    Debug.Log(edgeList[i].myData());
}

 

3) 크루스칼 알고리즘

 

3-1) 초기화 단계

for (int i = 0; i < nodeList.Count; i++)
{
    makeSet(nodeList[i]); //Union-Find에서 1)초기화 단계
}

 

3-2) 가중치가 작은 간선 순서대로 연결하되, 사이클이 되는 것은 피함

public List<Edge> kruskalFunc(List<string> nodeList, List<Edge> edgeList)
{
    Edge currentEdge;
    List<Edge> mst = new List<Edge>();
    for (int i = 0; i < edgeList.Count; i++)
    {
        currentEdge = edgeList[i];
        if (find(currentEdge.node1) != find(currentEdge.node2)) //사이클 방지
        {
            union(currentEdge.node1, currentEdge.node2);
            mst.Add(currentEdge);
        }
    }
    return mst;
}

 

전체 코드 : GitHub