- 현재
- 트리에 포함
- 사이클을 만듦
크러스컬 알고리즘
크러스컬 알고리즘은 모든 노드를 잇는 가장 저렴한 간선 집합인 최소 신장 트리를 상상할 수 있는 가장 단순한 방법으로 만듭니다. 간선을 짧은 것부터 긴 것 순서로 가져와, 사이클을 만들지 않는 한 모두 남깁니다. 단계를 진행하며 떨어진 조각들이 자라서 트리 하나로 합쳐지는 모습과 건너뛰는 간선을 지켜보세요. 재생을 눌러 트리가 자라는 모습을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 각 간선의 숫자는 그 길이입니다. 그래프 아래에는 아직 시도할 간선이 짧은 것부터 긴 것 순서로 표시됩니다. 양 끝이 이미 연결된 간선은 사이클을 만들므로 빨간 점선으로 그려집니다. 새 그래프는 다른 그래프를 만듭니다. 노드와 간선 수를 고를 수 있습니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.
작동 원리
- 재생을 누르거나, 단계와 뒤로로 한 단계씩 이동하세요.
- 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 아직 시도할 간선은 그래프 아래에 짧은 것부터 표시됩니다.
- 빨간 점선으로 그려진 간선을 눈여겨보세요. 사이클을 만드는 간선입니다. 새 그래프로 다른 그래프를 시도할 수 있습니다.
크러스컬 알고리즘의 작동 방식
모든 간선을 짧은 것부터 긴 것 순서로 정렬합니다. 처음에는 모든 노드가 각자 하나의 조각입니다. 간선을 차례로 시도합니다. 간선이 서로 다른 두 조각을 이으면 트리에 들어가고 두 조각은 하나가 됩니다. 양 끝이 이미 같은 조각에 있으면 사이클을 만들므로 건너뜁니다. 모두가 한 조각이 되면 멈춥니다. 이는 노드 수보다 하나 적은 간선을 더한 뒤이며, 마지막 간선을 시도하기 훨씬 전인 경우가 많습니다.
유니온-파인드
크러스컬 알고리즘은 간선마다 양 끝이 이미 연결되어 있는지 물어야 합니다. 유니온-파인드 구조는 이 질문에 빠르게 답합니다. 각 조각에는 대표 노드가 하나 있고, find는 링크를 따라 대표를 찾으며, union은 한 대표를 다른 대표에 연결합니다. 경로 압축과 크기 기준 합치기라는 두 가지 간단한 기법을 쓰면 질문 하나에 거의 상수 시간이 걸리므로, 가장 느린 부분은 간선 정렬이고 작업량은 E log E에 비례해 늘어납니다.
자주 묻는 질문
크러스컬 알고리즘이란 무엇인가요?
모든 간선을 짧은 것부터 긴 것 순서로 정렬하고, 이미 고른 간선과 사이클을 만들지 않는 간선을 하나씩 더해 최소 신장 트리를 만드는 그리디 알고리즘입니다.
크러스컬 알고리즘은 사이클을 어떻게 찾나요?
간선은 양 끝이 이미 고른 간선으로 연결되어 있을 때에만 사이클을 만듭니다. 유니온-파인드 구조는 어떤 노드들이 연결되어 있는지 추적하며 이 질문에 거의 즉시 답합니다.
크러스컬 알고리즘은 왜 옳은가요?
사이클 속성 때문입니다. 어떤 사이클에서든 가장 긴 간선은 최소 신장 트리에 결코 필요하지 않습니다. 크러스컬이 건너뛰는 간선은 앞선 간선이 모두 더 짧거나 같으므로, 그 간선이 만들 사이클에서 가장 긴 간선입니다.
프림 대신 크러스컬을 언제 써야 하나요?
크러스컬 알고리즘은 단순하고 희소 그래프에서 빠르며, 간선의 단순한 목록에 바로 쓸 수 있습니다. 프림 알고리즘은 밀집 그래프와 인접 리스트로 저장된 그래프에 알맞습니다. 둘 다 같은 총길이의 트리를 찾습니다.
내 그래프가 어딘가로 전송되나요?
아니요. 그래프와 트리는 브라우저 안에서 만들어지며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동