자료구조 - 그래프 위상정렬 그림으로 쉽게 이해하기

자료구조 - 그래프 위상정렬 그림으로 쉽게 이해하기

 

안녕하세요.

로스윗의 코딩캠프입니다.

오늘은 많은 사람들이 궁금해하시고 많이들 헷갈려하시는 내용을 바탕으로

자료구조 - 그래프 위상정렬 그림으로 쉽게 이해하기에 대해서 같이 알아보겠습니다.

그림으로 쉽게 이해할 수 있으니 끝까지 잘 따라와주세요 :)

바로 시작하겠습니다.

 

 

 

 

 

- 위상정렬 Topological sorting

이번 포스팅에서는 위상정렬에 대해서 알아보도록 하겠습니다.
위상정렬이 이름만 들어서는 무엇인지 잘 감이 안오실 것 같아요. 위상정렬은 사이클이 없고 방향이 있는 비순환 방향그래프에서 vertex를 순서대로 출력하는 알고리즘 입니다. 아래의 그림과 같은 방향그래프에서 E노드는 C와 F노드 모두의 의존성이 있어서 C와 F가 모두 방문된 후에 방문되어야 하는 순서의 노드로 보시면 됩니다.

 

 

위상정렬 예시

 

 

그래프 방문 결과가 순서대로 출력 되어야 하기 때문에 그래프의 시작점과 방향이 존재해야 하고, 그래서 사이클이 있으면 위성정렬로 sorting을 하는게 불가능합니다. 리스트같은 경우는 그 자체가 순서이지만 그래프 처럼 비선형적인데 순서가 있는 작업에서 그 순서를 찾아주는 알고리즘이라고 생각하시면 됩니다. 위상정렬의 개념은 이게 전부입니다. 말이 어려워서 그렇지 개념만 알면 별거 없습니다.

 

 

- 위상정렬을 구현하는 두 가지 방법

위성정렬을 구현하는 방법으로는 큐를 써서 구현하는 방법과 스택을 써서 구현하는 방법이 있습니다.
큐를 써서 구현하는 방법은 진입 차수를 계산하면서 sorting하는 방법이고, 스택을 써서 구현하는 방법은 DFS 매커니즘을 사용해서 구현하게 됩니다.

 

- 큐를 써서 위상정렬 구현하기

큐로 구현하는 것이 스택으로 구현하는 것보다 조금 더 간단합니다.

큐는 진입차수를 계산해서 sorting하는 방법인데, 진입차수(indegree)는 한 노드 vertex에 있어서 자신을 가리키고 있는 모든 edge의 수를 말합니다. 그래서 큐 구현에서는 우선 모든 vertex에서 indgree의 개수를 센 후에 indgree의 개수가 0인 vertex 즉, 자신을 가리키고 있는 edge가 하나도 없으니까 시작점이 될 수 있는 노드겠죠. 그래서 indgree가 0인 vertex를 큐에 삽입을 합니다. 그리고 큐에서 vertex를 꺼내고 이 vertex는 자신이 가리키고 있는 나가는 방향의 edge(outdegree)를 제거합니다. 이를 통해 indgree가 0이 된 vertex를 다시 큐에 삽입합니다. 이렇게 큐가 빌때까지 이 과정을 반복합니다. 이때 그래프의 사이클이 존재한다면 모든 노드를 방문하기 전에 큐가 비어서 종료가 됩니다. 그래서 위상정렬은 사이클이 없어야 됩니다.

 

 

위상정렬 큐로 구현하기

 

사이클이 없는 방향 그래프에서는 큐 구현 위상정렬을 하게 되면 우선 진입차수가 0인 A노드부터 시작을 하게 됩니다. 그래서 일단 큐에 A가 삽입이 되면서 시작이 됩니다.

 

 

큐에 A가 삽입된 모습

 

 

그러면 이제 큐에서 pop을 하게 되면은 A노드가 빠지게 되겠죠. 그래서 A에서 나가는 outdegree를 없애보면 진입차수가 0인 노드가 B와 C 두개가 생깁니다. 그래서 B와 C를 큐에 삽입해줍니다. 그러면 현재까지 방문 순서는 A입니다.

 

 

큐에 B와 C가 삽입된 모습

 

 

그 다음으로 B를 큐에서 빼서 outdegree를 없애면 진입차수가 0인 D가 생기죠. 이 D를 큐에 넣어줍니다. 그러면 현재까지 방문 순서는 A - B입니다.

 

 

큐에 C와 D가 삽입된 모습

그 다음으로 C를 큐에서 빼서 ourdegree를 없애주면 진입차수가 0인 vertex가 없기때문에 이때는 큐에 새로 삽입되는 노드는 따로 없습니다. E를 자세히 보면 F로부터 indgree가 존재하기 때문에 진입차수가 1임으로 삽입되지 않는 것입니다. 그러면 현재까지 방문 순서는 A - B - C입니다.

 

 

큐에 D가 남아있는 모습

이제 큐에서 D가 빠지게 되면서 outdegree를 제거하면 F노드가 큐에 추가가 되고, F노드가 가리키고 있던 indegree가 제거되면서 E가 큐에 삽입됩니다. 그러면 현재까지 방문 순서는 A - B - C - D입니다.

 

 

큐에 F가 남아있는 모습

 

 

이제 남은 E노드와 G노드를 같은 매커니즘으로 방문하고 나면 큐가 비면서 알고리즘이 종료가 됩니다. 그래서 위상정렬이 종료가 되면 A - B - C - D - F - E - G의 순서로 노드를 방문하게 되는 겁니다.

 

 

사이클이 있는 그래프 예시

 

반응형

그런데 이렇게 C와 E노드간에 사이클이 존재하는 그래프에서 앞에 매커니즘대로 vertex를 방문해보면 A, B, D, F, E는 방문할 수 있지만 C는 방문하지 못하고 알고리즘이 종료가 됩니다. 사이클에 속하는 vertex가 있다면 그 vertex는 항상 진입차수의 indgree가 1이상이기 때문에 큐에 들어갈 수가 없습니다. 혹은 사이클이 이렇게 생겨서 처음부터 vertex가 아예 없는 경우도 큐에 넣을수 없기 때문에 위상정렬을 할수 없습니다.

 

 

- 스택을 써서 위상정렬 구현하기

그 다음으로 스택을 이용한 구현방식을 보도록 하겠습니다.
스택을 이용한 구현은 쉽게 생각하면 DFS탐색 결과를 역순으로 한 결과가 위상정렬이 된다고 보시면 됩니다.

 

 

그래프 예시

 

 

시작은 동일하게 A에서 시작합니다. A에 연결된 B, C노드를 DFS로 방문하게 되면 어떤 순서로 탐색을 하게 될까요? DFS는 깊이 우선탐색으로 가능한한 멀리 탐색을 합니다. 그래서 B든 C든 가능한 멀리 까지 갈 수 있는 방법으로 갈 거에요. ㅇB를 먼저 선택을 해볼게요. 그러면 A - B - D - F - E - G 순서로 DFS 방문을 하게 되겠죠.

 

 

DFS방문 순서

 

이거의 역순인 G - E - F - D - B노드를 스택에 넣어줍니다. 스택은 Last In First Out이기 때문에 스택의 탑에는 B가 위치하게 되고, 스택의 가장 바닥에는 가장 멀리 있던 G가 위치하게 됩니다. 그리고 아직 A노드는 들어가지 않은 상태에요. 왜냐하면 A노드를 탐색 할 수 있는 노드가 아직 남아있기 때문이에요. 그렇기 때문에 A에서 탐색가능한 노드인 C노드 방향으로도 DFS를 하게 되고, 그래서 C노드 이후의 노드는 이미 방문한 노드이기 때문에 추가로 방문을 않고, A, C까지만 방문을 한 후에 DFS를 종료하게 됩니다.

 

그러면 DFS 결과를 역순으로 넣어야하기 때문에 A와 C가 스택에 들어가게 되고, 스택의 탑에는 A가 위치하게 되겠죠. 더이상 DFS를 방문할 노드가 남아있지 않으면, 이제 스택에 남아있는 노드들을 하나씩 출력해주면 그게 위상정렬의 결과가 됩니다. 그러면 A - C - B - D - F - E - G가 됩니다.

 

 

- 위상정렬의 시간복잡도

큐를 이용한 위상정렬과 비교했을 때, C노드의 방문순서가 조금 달라지긴 했지만 그래프 전체에 있어서 노드간의 의존성을 해치지 않고 올바르게 위상정렬된 결과를 볼 수 있습니다. 그래서 위상정렬은 그래프에 존재하는 정점, vertex의 개수와 엣지의 수에 비례하는 시간복잡도를 갖기 때문에 비교적 빠른 시간내에 결과를 구할 수 있다는 특징이 있습니다.

 

오늘은 이렇게 자료구조 - 그래프 위상정렬 그림으로 쉽게 이해하기에 대해서 알아보았습니다.

다음 포스팅도 기대해주세요.

감사합니다.