- 현재
- 준비됨 또는 방문 중
- 배치됨
- 사이클
위상 정렬
양말 다음에 신발, 기초 다음에 벽, 선수 과목 다음에 그 과목이 필요한 과목. 위상 정렬은 단방향 간선이 있는 그래프의 노드를 모든 간선이 앞에서 뒤로 향하는 한 줄로 나열합니다. 칸 알고리즘이나 DFS 방식을 골라 단계별로 진행하며 순서가 늘어나는 모습을 보고, 사이클을 추가해 그때는 왜 순서가 불가능한지 확인하세요. 재생을 눌러 순서가 늘어나는 모습을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 모든 간선은 화살표가 보여 주듯 한 방향입니다. "이것이 저것보다 먼저"라는 뜻으로 생각하세요. 방법을 고르세요. 칸 알고리즘은 들어오는 간선이 없는 노드부터 놓으며, 각 노드의 숫자는 아직 남은 들어오는 간선의 수입니다. DFS 방식은 어떤 노드 뒤에 올 것이 모두 놓이면 그 노드를 맨 앞에 놓습니다. 그래프 아래의 줄은 지금까지의 순서입니다. 사이클 추가를 체크하면 각 방법이 사이클을 찾는 모습을 볼 수 있습니다. 새 그래프는 다른 그래프를 만듭니다. 노드와 간선 수를 고를 수 있습니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.
작동 원리
- 칸 알고리즘이나 DFS 방식을 고르세요.
- 재생을 누르거나, 단계와 뒤로로 한 단계씩 이동하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다.
- 그래프 아래에서 순서가 늘어나는 모습을 지켜보세요. 사이클 추가를 체크하면 각 방법이 사이클을 찾는 모습을 볼 수 있습니다.
칸 알고리즘
모든 노드에 대해 그 노드를 가리키는 간선이 몇 개인지 셉니다. 하나도 없는 노드는 아무것에도 의존하지 않으므로 맨 먼저 올 수 있습니다. 그런 노드를 놓고 그 노드에서 나가는 간선을 지웁니다. 그 간선들이 가리키던 노드는 들어오는 간선이 하나 줄고, 일부는 0이 되어 준비됩니다. 준비된 노드가 없을 때까지 계속 놓습니다. 끝내 준비되지 않은 노드가 있다면 그 노드들은 사이클 안에서 서로를 기다리는 것이고, 위상 순서는 없습니다.
DFS 방식
방문하지 않은 각 노드에서 깊이 우선 탐색을 실행합니다. 어떤 노드에서 도달할 수 있는 것이 모두 끝나면 그 노드도 끝나므로, 그 뒤에 와야 할 것은 이미 모두 놓여 있습니다. 끝난 노드를 순서의 맨 앞에 놓으면 올바른 순서가 나옵니다. 탐색이 아직 그 안에 있는 노드로 가는 간선을 따라가면 그 간선이 사이클을 닫으며, 역시 순서는 없습니다.
자주 묻는 질문
위상 정렬이란?
방향 그래프의 노드를 모든 간선이 앞의 노드에서 뒤의 노드로 가도록 나열한 순서입니다. 간선이 "먼저 해야 한다"를 뜻한다면, 모든 작업을 해낼 수 있는 순서입니다.
위상 순서는 언제 존재하나요?
그래프에 방향 사이클이 없을 때, 즉 방향 비순환 그래프(DAG)일 때만 존재합니다. 사이클이 있으면 그 위의 모든 노드가 자기 자신보다 먼저 와야 합니다.
위상 순서는 하나뿐인가요?
보통은 아닙니다. 두 노드가 간선의 사슬로 이어져 있지 않으면 어느 쪽이 먼저 와도 되므로, 한 그래프에 올바른 순서가 여러 개 있을 수 있습니다. 칸 알고리즘과 DFS 방식은 서로 다른 순서를 내는 경우가 많습니다.
위상 정렬은 얼마나 빠른가요?
두 방법 모두 모든 노드와 모든 간선을 정해진 횟수만큼 보므로, 작업량은 노드 수와 간선 수의 합에 비례해 늘어납니다.
내 그래프가 어딘가로 전송되나요?
아니요. 그래프는 브라우저 안에서 만들어지고 정렬되며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동