위상 정렬 (Topological Sort)

HunkiKim·2022년 9월 21일
0

위상 정렬이란 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬을 말한다.

만약 그래프안에 사이클이 존재할 경우엔 올바른 위상정렬이 존재할 수 없다. deadlock과 같은 느낌이다.

사이클이 존재하지 않은 방향 그래프를 DAG(Directed Acyclic Graph)라고 부른다. 위상 정렬은 DAG에서만 적용이 가능하다.

구현 방법

우선 가장 먼저 앞에 오는 것을 생각해야 한다. 제일 앞에 오기 위해서는 자신보다 앞에 위치해야 하는 원소들이 없어야 한다. 즉 자신에게 들어오는 간선이 없음을 의미한다. 이 말은 indegree가 0이라고 표현할 수 있다.

indegree는 자신에게 들어오는 간선의 수를 의미한다.

위의 사진을 예시로 진행해보자.

A,C,G의 경우 indegree가 0임을 알 수 있다. 따라서 제일 앞에오는 원소이다.

A,C,G아무거나 상관없지만 위상정렬의 첫 번째 정점을 A라고 하자. A를 추가한 뒤에는 이제 신경 쓸 것이 없기 때문에 A와 A에서 뻗어나가는 간선을 모두 지운다.

이후 C를 추가한다.(G도 상관없다.) 따라서 두 번째 원소는 C이다. 이후 C를 삭제해주자.

이후 자신에게 들어오는 간선이 없는 정점을 골라야 한다. A원소와 C원소가 삭제되었기 때문에 D,G가 남았다.

그리고 D를 선택하자.(G도 상관없다.) 이후 D를 지우면 B와 G가 선택될 수 있다.

그리고 이 같은 과정으로 G를 지우고 E를 지우고 B를 지우고 F를 지우면 끝나게 된다.

결과로 A->C->D->G->E->B->F가 되며 매 순간마다 indegree가 0인 노드를 골라서 결과에 넣는 방식으로 진행하면 된다.

실제로 구현에서는 정점과 간선을 실제로 지울 필요 없이 미리 indegree의 값을 저장한 뒤 정점들의 indegree 값만 1 감소시키면 과정을 수행할 수 있다.

그리고 indegree가 0인 정점을 구하는 것은 매번 모든 정점을 확인하는 것이 아닌 따로 저장하고 있다가 직전에 제거한 정점에서 연결된 정점들을 확인한 뒤 0인 정점을 추가하는 방식으로 하면 된다.

위의 구현 과정을 생각하고 다시 사이클을 이 있는 그래프를 본다면 사이클은 indegree가 0인 정점이 없기 때문에 시작도 못하고 끝나게 된다.

시간복잡도는 V와 E에 대한 이벤트들이 한 번씩만 발생하기 때문에 O(V+E)이다.

0개의 댓글