위상정렬1 위상 정렬 알아보기 위상 정렬(Topological Sorting)이란?방향 그래프의 정점들을 방향을 거스르지 않도록 나열하는 것.각 정점에 순서를 매기고, 그 순서를 거스르지 않도록 정점들을 정렬하는 것을 의미한다. ex) 선수 과목 구조(과목마다 먼저 들어야 하는 과목의 순서가 정해져 있음)여기서 순서란, 그래프의 정점 순서를 가리킴.ex) 정점 v1과 v2이 v1 → v2 방향으로 연결되어 있으면, v1이 선행된다고 본다.위상 정렬에 사용될 그래프는 순환이 없어야 함(비순환 방향 그래프여야 함). 알고리즘Kahn 알고리즘자신을 향하는 간선(즉, 자신으로 들어오는 간선)이 없는 정점을 찾는다.이러한 정점이 여러 개라면, 그 중 아무거나 한 개를 고른다.해당 정점을 그래프에서 제거한다.남은 그래프에서 정점이 더 이상 존재.. 2024. 8. 31. 이전 1 다음