위상정렬 Topological sort (1) 썸네일형 리스트형 위상정렬 (Topological Sort) 알고리즘 위상정렬 해당 내용을 이해하기 위해선 DFS(링크)에 대한 이해가 필요하다. 위상정렬(Topological Sort)는 DFS를 사용하는 대표적인 알고리즘이다. DFS말고 indegree의 개수를 측정하는 방법도 있다. 알고리즘의 목표는 일의 순서를 정하는 것이다. 예를 들어 W1, W2, W3 (W는 할 일이다)이 있다고 가정하자. W2는 W1을 끝내야만 할 수 있고, W3은 W2를 끝내야만 할 수 있다. 그렇다면 일의 순서는 W1 → W2 → W3로 하면 될 것이다. 예시는 3개밖에 없어서 간단한 암산으로 금방 해결할 수 있지만, 주어진 정보가 많아진다면 골치가 아파진다. 이때 사용하는 알고리즘이 바로 위상정렬이다. 다음과 같은 그래프가 있다. 각 노드는 위에서 언급한 '일'이라고 생각한다. 모든 노.. 이전 1 다음
