[ Algorithm ] Kruskal & UnionFind 알고리즘

 

 

크루스칼 알고리즘을 이해하는데 필요한

최소신장트리, UnionFind 알고리즘과 함께 공부 내용을 정리해보려고 합니다.

 

📌 최소신장트리

• 최소 비용 신장트리, 최소신장트리, MinimumspanningTree , MST 등등으로 불림
• 그래프 내의 최소 비용으로 모든 정점을 포함하는 트리
  • 트리라는 말 속 노들들의 연결과 함께 사이클이 존재하지 않음을 내포하고 있음
• 크루스칼알고리즘과 프림 알고리즘등을 통해 구현가능

📌 크루스칼 알고리즘

1. 코스트, 거리 등에 대해 오름차순으로 정렬한다.
2. 오름차순으로 순회하며 사이클이 발생하지 않는다면 해당 노드를 연결 시킨다.
   • 사이클에대한 판단은 UnionFind 알고리즘을 사용한다.

노드 연결에서의 사이클 상태

📌 Union-Find 알고리즘

• 여러개의 노드가 존재할 때 노드들 끼리 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다.
• 노드의 루트(부모를 찾아내는) Find 함수, 두노드의 연결을 통해 두 노드를 포함하고있는 그래프들를 합치는 Union 함수로 이루어졌습니다.
• 노드 들에 대한 부모를 표기할 수 있는 자료구조가 필요합니다.

📍 find 함수

• 노드들에 대한 부모노드를 구해내는 함수 입니다.
• 부모노드에 도달 할때까지 재귀적으로 함수를 호출합니다.

private fun findParent(parentList: IntArray ,idx: Int): Int {
    return if (parentList[idx] == idx) idx
    else findParent(parentList , parentList[idx])
}

📍 Union 함수

• 두 노드가 연결 되었을때 부모 노드를 일치화시켜주는 함수입니다.
• 두 노드의 부모를 찾고 두 보모중 대표값을 결정하여 부모값을 변경해준다.
• 주의) 부모의 노드값을 변경하는 것이 아닌 중간 노드를 변경하면 연결이 끊겨 문제가 생긴다.

// 옳바른 코드
private fun unionParent(parentList: IntArray, aNode: Int, bNode: Int) {
        val aParent = findParent(parentList, aNode)
        val bParent = findParent(parentList, bNode)
        val newParent = min(aParent,bParent)
        parentList[aParent] = newParent
        parentList[bParent] = newParent
    }

// 문제가 있는 코드
private fun unionParent(parentList: IntArray, aNode: Int, bNode: Int) {
    val newParent = min(findParent(parentList , aNode), findParent(parentList, bNode))
    parentList[aNode] = newParent
    parentList[bNode] = newParent
}

https://blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)