크루스칼(Krusckal)알고리즘

6mn12j·2020년 9월 3일
0

크루스칼(Kruskal)알고리즘 이란?

정의

  • 크루스칼 알고리즘은 최소 비용으로 모든 노드를 연결할때 사용 하는 알고리즘 입니다.

예시

1. 최소 비용 신장 트리(Minimum Spanning Tree)


위의 그래프가 있을때 숫자가 적힌 원들을 노드', 정점 이라고 부릅니다. 선의 빨간 숫자들은 가중치,비용, 엣지 라고 합니다. 트리로 된 그래프 이기 때문에 하나의 노드는 하나의 노드만 가리킵니다.

2.최소 비용 신장 트리 연결


처음에 각 노드들은 자기 자신만을 포함한 부분 집합 입니다. 가중치가 적은 순서대로 노드들을 하나씩 연결 합니다. 노드가 연결 될때 노드들은 같은 집합에 속하게 됩니다. 그리고 모든 노드들이 같은 집합에 속한다면 모든 노드가 연결이 되었으므로 '최소비용신장트리'(Minumum Spanning Tree)가 만들어지고 끝이 납니다.

최소비용 10부터 시작 2노드와 5노드 연결




다음 최소비용인 45지만 3과 5는 이미 한 집합 (연결) 되어 있으므로 넘어간다.트리는 사이클이 생기면 안됨.

마지막 최소 비용 77을 연결하면 최소비용 신장 트리가 만들어 짐.

사이클일 경우

4번에서 그래프를 연결 할때 사이클이 형성될 경우에는 넘어갔다.이 사이클을 체크할때 최상위 노드가 같으면 같은 집합으로 생각하고 최상위 노드가 다르다면 다른 집합에 있다고 판단한다.최상위 노드를 찾을때는 find를 이용하고 최상위노드가 다르다면(연결이 안된경우)에 연결 해주기 위해서는 union을 이용한다 ->'Union-find'알고리즘

참고한 블로그

https://blog.naver.com/world9604/221997800902

profile
TIL 쩨끼럽 남기는 중 💻

0개의 댓글