printf("hellow coding");

프림 알고리즘은 크루스칼 알고리즘과 함께 어떤 그래프가 주어졌을 때 그 그래프에서 최소신장트리(MST) 를 찾아내는 알고리즘 입니다. 최소신장트리에 대한 개념은 앞에 포스트했던 크루스컬 알고리즘에서 정리하였으니 참고하시기 바랍니다.

https://buganddog.tistory.com/2

크루스칼 알고리즘에서 먼저 간선을 선택하고 그다음 노드를 하나씩 붙여가는 식이였다면 프림알고리즘은 반대로 시작 정점을 먼저 선택한 후 정점에 연결된 간선을 추가해서 하나씩 붙여나가는 방식으로 알고리즘이 진행됩니다. 말이 참 애매한데; 좀더 명확히 정리해보도록 하겠습니다. 

프림 알고리즘 (Prim's algorithm)

• 대표적인 최소 신장 트리 알고리즘
  • Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘)
• 프림 알고리즘
  • 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식
• Kruskal's algorithm 과 Prim's algorithm 비교
  • 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음)
  • Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 MST를 구함
  • Prim's algorithm은 특정 정점에서 시작, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중치가 작은 간선을 택하는 방식으로 MST를 구함. 

프림알고리즘의 동작을 이해 하기위해선  다음 5단계만 기억하시면 됩니다! 

1. 임의의 정점을 선택, '연결된 노드 집합'에 삽입
2. 선택된 정점에 연결된 간선들을 간선 리스트를 만들어서 리스트에 삽입
3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서,
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵! (cycle 발생을 막기 위함)
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리'에 삽입
4. 추출한 간선은 간선 리스트에서 제거
5. 간선 리스트에 더 이상의 간선이 없을 때까지 3-4번을 반복

처음에는 간선 리스트가 무엇이며, 연결된 노드 집합이라는 건 무엇인지 감이 잘 오지 않으실 겁니다. 

이러한 세부적인 부분들은 후에 구현 부분에서 다루기로하고, 우선 프림알고리즘의 동작방식에 대한 큰 개념을 잡는것을 목표로 하고 이를 그림으로 확인해 보도록하겠습니다. 

먼저 시작단계입니다. 위에서 5단계를 잘 염두하고 그래프를 보도록하겠습니다. 

시작은 임의의 정점을 선택하는 것에서 시작합니다.

여기서는 A라는 정점을 선택했군요! 

그림상에서 보이지는 않지만, 선택한 A 노드를 '연결된 노드집합' 으로 정의된 자료구조에 넣고 선택된 정점에 연결된 

간선들. 또한 '연결된 간선 리스트' 라는 자료구조를 정의해서 그안에 넣어 두도록 합시다. 

앞서 말씀드렸듯이. 어떻게 넣는지에 대해서는 생각을 잠시 미루고, 큰 개념을 우선적으로 보겠습니다.

( 위 그림에서는 리스트에 넣어진 간선은 빨간색, MST에 들어간 노드와 간선들은 파란색으로 표시해줍니다 ) 

그림에서는 노드 A가 선택되고 A와 연결된 가중치 5, 7인 간선 2개가 간선리스트에 추가가되고, 따라서 리스트에 저장된 간선중 가중치가 최소인 (5 ,A->D) 간선을 꺼내서 조사를 합니다. (3단계 과정)   

• 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵! (cycle 발생을 막기 위함)
• 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리'에 삽입

현재 그림에서는 간선에 연결된 노드 D 가 연결된 노드집합에 속해 있지 않으므로 노드 D를 연결된 노드 집합에 추가해 줍니다! 그 후 조사했던 간선 (5 ,A->D) 는 연결된 간선리스트에서  제거해줍니다! 

동작방식이 조금은 이해 되시나요? 

이와 같은 과정을 계속해서 반복하여 더 이상 연산가능한 간선이 없을 때 까지 계속해서 반복하는것이 프림알고리즘 입니다! 계속해서 확인해 보도록 하겠습니다. 

노드 D와 연결된 간선들 리스트에 저장 -> 리스트에서 가중치 최소인 간선 (5, D->F) 추출 ->  연결된 노드집합에 F가 없으므로 노드집합에 추가 ->    (5, D->F) 간선을 '최소 신장 트리'에 삽입  ->  간선리스트에서 (5, D->F)제거

이제 좀 더 감이 확실히 잡히는 느낌입니다. 이제 나머지 동작그림을 한눈에 봐보도록 하겠습니다

마지막 6번에서 리스트에 저장된 간선들(빨간색 간선)을 모두 조사를 하지만 (9,E-G)를 잇고 나서는 모든 노드들이 

연결되어있고, 최소신장트리가 완성되어 있으므로 그 이외의 나머지 간선들은 위 단계3 에서 정의한 조건

• 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵! (cycle 발생을 막기 위함) 을 

만족하지 못하기 때문에 리스트에 추가되는 과정없이 스킵이 됩니다! 이렇게 모두 스킵이 되어 더이상 연산을 진행할 간선이 없게 된다면 알고리즘이 종료되는 것입니다. 

여기까지 이해를 하셨다면 프림알고리즘을 구현하는데 있어서 필요한 동작개념을 완벽히 이해를 하신겁니다 ㅎ 

다음 포스트에서는 이 개념을 염두해서 파이썬으로 프림 알고리즘을 구현해 보도록 하겠습니다.  

이번 포스트에서는 파이썬으로 크루스칼 알고리즘을 구현해 보도록 하겠습니다. 

(게시글의 자료들은 잔재미코딩(https://www.fun-coding.org/Chapter20-prim-live.html) 사이트를 참조하였습니다)

먼저 앞선 포스트에서 다룬 그래프를 다음과 같은 그래프를 딕셔너리 형태로 구현하도록 하겠습니다. 

이제 구현까지 살펴 보았으니 시간복잡도를 살펴봅시다. 

시간 복잡도

• 크루스컬 알고리즘의 시간 복잡도는 O(E log E)
  • 다음 단계에서 2번, 간선을 비용 기준으로 정렬하는 시간에 좌우됨
    (즉 간선을 비용 기준으로 정렬하는 시간이 가장 많이 든다)
  • 모든 정점을 독립적인 집합으로 만든다. - 복잡도 O(V) 
  • 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
    • 퀵소트를 사용한다면 시간 복잡도는 O(n log n) 이며, 간선이 n 이므로 O(E log E)
  • 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것임)
    • union-by-rank 와 path compression 기법 사용시 시간 복잡도가 결국 상수값에 가까움, O(1)

이상으로 크루스칼 알고리즘에 대한 포스트를 마치도록하겠습니다. 

지난 포스트에서는 크루스칼 알고리즘이 동작하는 개념에 대해서 살펴보았는데요

이번 포스트에서는 그 동작에 대한 세부적인 기준과 알고리즘을 살펴보도록 하겠습니다.

(게시글의 자료들은 잔재미코딩(https://www.fun-coding.org/Chapter20-prim-live.html) 사이트를 참조하였습니다)

지난 포스트에서 노드를 이를 떄 트리로 묶어 두 노드가 같은 집합인지, 다른집합인지 판단했었던것 기억하시나요? 

이를 Union-Find 알고리즘이라 하는데 그림을 통해서 다시한번 확인해 보도록 하겠습니다. 

Union-Find 알고리즘

• Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘
• 간단하게, 노드들 중에 연결된 노드를 찾거나, 노드들을 서로 연결할 때 (합칠 때) 사용
• Disjoint Set이란
  • 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
  • 공통 원소가 없는 (서로소) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조를 의미함
  • Disjoint Set = 서로소 집합 자료구조

요약하자면 

initial - 각각의 집합요소들을 개별적인 집합으로 분할하는 초기화 과정 
union - 합치는 알고리즘 
find - 중복되는지 검사(사이클 검사) 

크루스칼은 모든 간선이 비용기준으로 정렬을해서 비용이 작은 간선부터 사이클이 생기지않는선에서 모든노드들을 연결합니다.  다만 여기서 두노드를 이었을때 사이클이 생기는지 안생기는지를 판단하기 위해서 union find알고리즘을 사용하는데,  간선끼리 이미 연결된 노드들을 부분집합으로 관리하고 특정 두노드를 뽑아서 그 노드 2개가 루트노드가 동일하다고 한다면  사이클이 생긴다고 가정 , 그게아니면 사이클이 아니라고 판단하고 union 로직을 사용해서 둘을 합친다 .

여기까지가 지난시간에 살펴보았던 내용이었습니다. 그렇다면 과연 Union이란 두 집합을 합치는 과정은 어떠한 기준으로 합치는 걸까요? 지난 포스트에서 막연하게 루트노드끼리 갖다 붙이라고만했지 정확한 방침이 나와있지않은데 
잘못하면 일렬로 나열하게되어 최악의 시간복잡도를 가지게 될 수도 있습니다. 

  특별한 기준없이 위와 같이 그저 한쪽 방향으로만 노드를 이어나가는 방식으로 트리를 구현해 보았다고 가정합시다. 위와 같이 구현하였다고 가정한다면 Union 순서에 따라 최악의 경우 링크드 리스트와 같은 형태가 될 수도 있습니다.  즉 Union, Find 동작시 계산량이 O(N)으로 트리구조를 만드는 이점이 없는 겁니다;; 이러한 사태를 방지하기위해 

nion-by-rank, path compression 기법을 사용합니다.

union-by-rank 기법

• 각 트리에 대해 높이(rank)를 기억해 두고,

• Union시 두 트리의 높이(rank)가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙임 (즉, 높이가 큰 트리의 루트 노드가 합친 집합의 루트 노드가 되게 함)

• 높이가 h - 1인 두 개의 트리를 합칠 때는 한 쪽의 트리 높이를 1 증가시키고, 다른 쪽의 트리를 해당 트리에 붙임

초기화시, 모든 원소는 높이(rank) 가 0 인 개별 집합인 상태에서, 하나씩 원소를 합칠 때, union-by-rank 기법을 사용한다면,

• 높이가 h 인 트리가 만들어지려면, 높이가 h - 1 인 두 개의 트리가 합쳐져야 함
• 높이가 h - 1 인 트리를 만들기 위해 최소 n개의 원소가 필요하다면, 높이가 h 인 트리가 만들어지기 위해서는 최소 2n개의 원소가 필요함
• 따라서 union-by-rank 기법을 사용하면, union/find 연산의 시간복잡도는 O(N) 이 아닌, O(logN) 로 낮출 수 있음

path compression 기법 

• Find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결하는 기법
• Find를 실행한 노드는 이후부터는 루트 노드를 한번에 알 수 있음

#참고

union-by-rank 와 path compression 기법 사용시 시간 복잡도는 다음 계산식을 만족함이 증명 되었다.

• 𝑂(𝑀𝑙𝑜𝑔∗𝑁)O(Mlog∗N)
• 𝑙𝑜𝑔∗𝑁log∗N 은 다음 값을 가짐이 증명되었음
  • N이 265536265536 값을 가지더라도, 𝑙𝑜𝑔∗𝑁log∗N 의 값이 5의 값을 가지므로, 거의 O(1), 즉 상수값에 가깝다고 볼 수 있음

find 를 실행해서 해당 노드의 루트노드를 찾고, 만약 A-B-C-D로 이어진 트리가 있다면 D노드의 루트노드를 찾을 때 그 중간노드가아닌 바로 A노드를 찾아주는 것을 path compressino기법이라고 합니다.

무작위로 트리를 구성하였을 때 O(N)의 시간복잡도를 가졌던 것이 두 알고리즘 기법을 통해 거의 상수에 가까운 시간복잡도를 갖게 되었습니다.  위 방법들을 염두해 두고 다음 포스트에서는 드디어 크루스컬 알고리즘을 파이썬으로 구현 해 보도록 하겠습니다. 

이번 포스트에서는 크루스칼 알고리즘을 다루도록 하겠습니다

긴호흡의 글이 될 것 같아 3개의 글로 나눠 포스트 하도록 하겠습니다. 

이번 포스트에서는 크루스칼알고리즘의 개념을 이해하는데 중점을 두고 구현은 다음 글에서 작성하도록 하겠습니다. 

(게시글의 자료들은 잔재미코딩(https://www.fun-coding.org/Chapter20-prim-live.html) 사이트를 참조하였습니다)

먼저 크루스칼 알고리즘을 이해하기 위해서 최소 신장트리의 개념을 알아야 합니다. 

왜냐면 크루스칼 알고리즘이 어떠한 그래프가 주어졌을 때 그래프의 최소신장 트리를 찾아내는 알고리즘이니까요

신장 트리(Spanning Tree) 란?

• 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프

• 신장 트리의 조건

  • 본래의 그래프의 모든 노드를 포함해야 함
  • 모든 노드가 서로 연결
  • 트리의 속성을 만족시킴 (사이클이 존재하지 않음

이 부분은 그림을 보시면 한눈에 확인 할 수 있습니다. 

보시는 바와같이 그래프의 모든노드가 빠짐없이 이어져 있으며, 각 간선들이 사이클을 생성하지 않습니다, 사이클이란 쉽게 말하면 간선들이 이어진 모양이 태두리로 둘러싸여 막힌 모양이라고 생각하시면 되겠습니다. 

그렇다면 최소신장트리란 무엇인지 감이 오시나요? 

최소 신장 트리

• Minimum Spanning Tree, MST 라고 불리움
• 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함

왼쪽과 같이 간선에 가중치가 설정된 original그래프가 있다고 가정합시다. MST란 이 가중치가 설정된 그래프에서 

spanning tree를 구현하였을 때 각 간선들의 가중치합이 가장작은 신장트리를 의미합니다. 만약 최소 가중치합 6이라 가정했을때 신장트리중에 가중치 합이 6인 트리가 여러개라면, MST도 여러개 존재할 수 있습니다. 위 예시에서는 하나만 존재하는군요 

따라서 이번 포스트에서 알아볼 크루스칼 알고리즘이란 어떠한 그래프가 주어졌을 때 최소 신장 트리를 찾을 수 있는 알고리즘입니다. 대표적인 최소 신장 트리 알고리즘은 Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘)이 있는데, 순차적으로 알아보도록 하겠습니다.  

크루스칼 알고리즘 (Kruskal's algorithm)

1. 모든 정점을 독립적인 집합으로 만든다.
2. 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
3. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것임)

위 단계는 크루스칼 알고리즘을 구현하기 위한 단계를 크게 분류해 놓은겁니다. 

당장은 글이 잘 이해가 안될 수 도 있습니다. 먼저 그림으로 어떻게 동작하는지에 대한 개념을 살펴봅시다 .

먼저 모든 간선들이 가중치가 작은순서대로 정렬되어있다고 가정합시다. 

따라서 간선의 가중치가 가장작은 A-D 간선을 선택하여 해당 노드를 이어줍니다. 그리고 차례대로 그다음으로 가중치가 같거나 작은 간선을 선택하여 노드를 이어줍니다. 위 예시에서는 E와 C노드가 되겠네요 

그 다음으로 가중치가 작은 간선인 D-F노드를 선택합니다. A의 루트노드는 D, B는 독립적인 노드로 자기자신이 루트노드이니, 서로의 루트노드가 다르기 때문에 아래와 같이 트리형식으로 한 집합으로 묶어줍니다. 이 노드들을 묶는 방법에 대해서는 다음 포스트에서 설명할 예정이니 우선 개념적인 부분만 이해하는걸 목표로 합시다 ㅎ 

그 다음으로 작은 가중치는 7이므로 먼저 A-B 간선을 추가하여 이어봅시다. A-B 역시 서로 한 집합에 있지않은 독립적인 집합이었으므로 이어주는 것이 가능합니다. A의 루트노드는 D, B는 기존에 없던 독립적인 노드이니 하나로 합쳐주는 것이 가능합니다. 

이제 B-E간선을 선택해서 이어봅시다. 마찬가지로 트리에서 각각 B , E 노드의 루트노드가 다르기에 두 집합을 하나로 묶을 수 있습니다. 

이제 다음으로 가중치가 작은 D,E 간선을 선택했다고 가정합시다.  D,E 를 연결하게 되면 사이클이 생기게 됌을 확인할 수 있습니다. 트리 구조를 확인해 보면 역시나 D의 루트노드는 E, E 노드는 본인이 루트노드 이므로 서로의 루트노드가 같습니다. 즉, D,E는 서로 같은 집합(트리)에 속해있다고 볼 수 있는거지요 

이제 왜 간선을 추가 할 떄마다 각 노드를 잇는 집합을 트리로 표시하는지, 감이 조금 오시나요? 

크루스칼 알고리즘은 간선을 선택했을 때 간선이 사이클을 생성하는지의 여부를 두 노드가 서로 같은 집합에 속하는지 여부로 판단을 합니다.  이 같은 집합에 속한다는것을 판단하기 위한 도구로 각 간선을 선택할 때 해당노드들을 트리로 만들어 확인하는 겁니다. (이 트리를 생성하는 방법에 대해서는 다음 포스트에서 설명하도록 하겠습니다) 

따라서 위와 같은 사이클이 생기는 경우들을 배제하고, 순차대로 가중치가 작은 간선들을 선택해서 묶어주다보면 위와 같이 주어진 그래프에서 MST를 찾아 낼 수 있는겁니다 ! 

여기까지가 크루스칼 알고리즘이 동작하는 아주 큰 관점에서의 개념을 살펴보았습니다. 

다음 포스트에서는 그렇다면 어떤 방식으로 노드들을 묶고 트리를 생성 하는지에 대한 방법을 다루도록 하겠습니다