본문 바로가기

(탈퇴) 테슬라's Post

그래프 - Kruskal식 최소신장트리??

안녕하세요~ 모두 잘 지내시죠~ 테슬라 입니다.

오늘은 저번 포스트에 이어 최소신장트리에 대해서 하고자 합니다.

오늘의 주제는 무엇인고 하니 최소신장트리를 구성하는 방법중에 하나인 Kruskal식의 최소신장트리입니다.


Kruskal식이란 무엇인가? 하니 가중치가 적은 순서대로 연결하는 방식을 말합니다.

각각의 간선마다 가중치가 존재하지요?

이 가중치들을 적은 순서대로 놓아보세요.

그 다음에 차근차근 작은 순서대로 간선들을 연결하지요.

단! 저번 포스트에서 말씀드린대로 최소신장트리는 사이클이 없어야겠죠?

오늘도 역시 예를 들어보지요~
사용자 삽입 이미지

자 이 그래프에는 5개의 간선들이 존재합니다. (저번거와는 가중치가 다릅니다. 네)

(1,2), (1,3), (1,4), (2,3), (3,4) 이렇게 5개가 있습니다.

이걸 가중치 순으로 늘여놓아보죠.
 (1,4), (3,4), (1,3), (2,3), (1,2) 이런 순입니다.

자, 연결해보죠.
사용자 삽입 이미지
왜 (2)에서 (3)으로 넘어갈 때 (1,3)으로 연결 안하느냐고 하시는 분들!!

아까 말씀드렸다시피 사이클이 생기면 안됩니다. 하지만 (1,4), (3,4)를 연결하었기 때문에 (1,3)을 연결하면
사이클이 생겨버리게 되는 것이지요.

그것을 막기 위해 (1,3)를 버리고 다음 간선인 (2,3) (이건 사이클이 안생기죠?)을 연결한 것입니다.

네, 그런식으로 정점보다 하나 적은 갯수를 연결합니다. 여기서 더 이으면 사이클이 생기지요.

이런식으로 그래프를 신장트리로 변환시키는 것입니다.

Kruskal식은 그렇게 어렵지 않지요?


자 Kruskal식은 이정도로 설명하겠습니다.
오타나 잘못된 부분은 지적해주시면 감사하겠습니다~
그럼 다음 포스트 때 만나요~