- 현재
- 트리에 포함
- 트리와 인접
- 지금까지 최선의 간선
- 사이클을 만듦
최소 신장 트리
모든 마을을 케이블로, 모든 집을 수도관으로, 또는 네트워크의 모든 컴퓨터를 최대한 적은 재료로 연결하고 싶다고 해 봅시다. 그 답이 최소 신장 트리입니다. 모든 노드를 가장 작은 총길이로 연결하는 간선의 집합이죠. 크러스컬이나 프림 알고리즘을 고르고 단계별로 진행하며, 허용되는 가장 짧은 간선이 하나씩 더해지면서 트리가 자라는 모습을 보세요. 재생을 눌러 트리가 자라는 모습을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 알고리즘을 고르세요. 크러스컬은 간선을 짧은 것부터 긴 것 순서로 시도하고, 프림은 시작 노드에서 트리 하나를 키웁니다. 노드를 클릭하면 프림의 시작 노드가 됩니다. 각 간선의 숫자는 그 길이입니다. 그래프 아래에는 아직 시도할 간선 목록, 또는 트리에 합류하기를 기다리는 노드와 트리로 이어지는 가장 좋은 간선의 길이가 표시됩니다. 새 그래프는 다른 그래프를 만듭니다. 노드와 간선 수를 고를 수 있습니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.
작동 원리
- 크러스컬이나 프림 알고리즘을 고르세요. 프림은 노드를 클릭해 시작 노드로 정합니다.
- 재생을 누르거나, 단계와 뒤로로 한 단계씩 이동하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다.
- 간선이 트리에 합류하고 총길이가 늘어나는 모습을 지켜보세요. 새 그래프로 다른 그래프를 시도할 수 있습니다.
크러스컬 알고리즘
모든 간선을 짧은 것부터 긴 것 순서로 정렬하고 그 순서대로 시도합니다. 간선이 아직 연결되지 않은 두 조각을 잇는다면 트리에 들어갑니다. 두 끝이 이미 트리를 통해 연결되어 있다면 사이클을 만들므로 건너뜁니다. 트리의 간선 수가 노드 수보다 하나 적어지면 멈춥니다. 두 노드가 이미 연결되어 있는지 빠르게 알기 위해, 크러스컬 알고리즘은 조각들을 유니온-파인드 구조로 관리합니다.
프림 알고리즘
노드 하나로 된 트리에서 시작합니다. 트리 밖의 각 노드는 트리로 가는 가장 짧은 간선을 기억합니다. 간선이 가장 짧은 노드를 그 간선과 함께 트리에 더하고, 그 노드의 간선을 확인하는 일을 반복합니다. 어떤 간선은 이웃 노드에게 트리로 들어오는 더 짧은 길을 줄 수 있습니다. 프림 알고리즘은 다익스트라 알고리즘과 비슷해 보이지만, 시작 노드로부터의 전체 거리가 아니라 간선 하나하나를 비교합니다. 두 알고리즘은 항상 같은 총길이로 끝납니다.
자주 묻는 질문
최소 신장 트리란 무엇인가요?
간선에 길이가 있는 연결 그래프에서, 신장 트리는 사이클 없이 모든 노드를 연결하는 간선의 집합입니다. 노드가 n개면 간선은 항상 n − 1개입니다. 최소 신장 트리는 총길이가 가능한 한 작은 신장 트리입니다.
크러스컬 알고리즘과 프림 알고리즘은 무엇이 다른가요?
크러스컬 알고리즘은 그래프 전체의 간선을 짧은 것부터 긴 것 순서로 보며 떨어진 조각들을 하나의 트리로 합칩니다. 프림 알고리즘은 시작 노드에서 트리 하나를 키우며, 트리에서 나가는 가장 짧은 간선을 항상 더합니다. 둘 다 그리디 알고리즘이고 총길이가 같은 트리를 찾습니다. 크러스컬은 희소 그래프에, 프림은 밀집 그래프에 알맞습니다.
최소 신장 트리는 하나뿐인가요?
모든 간선의 길이가 다르면 그렇습니다. 같은 길이가 있으면 가장 작은 총길이가 같은 트리가 여러 개 있을 수 있고, 알고리즘은 동점을 처리하는 방식에 따라 서로 다른 트리를 고를 수 있습니다.
최소 신장 트리는 최단 경로와 같은가요?
아니요. 최소 신장 트리는 모든 간선의 총길이를 작게 유지하지만, 트리 안에서 두 노드 사이의 경로는 최단 경로보다 훨씬 길 수 있습니다. 최단 경로를 구하려면 다익스트라 알고리즘을 쓰세요.
내 그래프가 어딘가로 전송되나요?
아니요. 그래프와 트리는 브라우저 안에서 만들어지며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동