26. 그래프(Graph) - 위상정렬(Topological Sorting)

위상 정렬(topological sorting)이란 방향성(유향) 그래프의 모든 방향성 간선이 한쪽을 가리키도록 모든 정점을 배치하는 방법입니다. 

 

위키에는 다음과 같이 설명합니다. ㅇㅇ 같은 말입니다. 

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.

쉽게 말해서 위 그래프를 빠지지 않고 모두 이수할 수 있도록 순서를 정하는 것이 위상 정렬입니다. 

 

입학 -> 개론 -> (어셈블리) -> 자료구조 -> 운영체제 -> 알고리듬
입학 -> 개론 -> 자료구조 -> (어셈블리) -> 운영체제 -> 알고리듬
입학 -> 개론 -> 자료구조 -> 운영체제 -> (어셈블리) -> 알고리듬
입학 -> 개론 -> 자료구조 -> 운영체제 -> 알고리듬 -> (어셈블리)

 

이렇게 어셈블리 노드만 변형을 해봐도 다양한 순서가 나옵니다. 
모두 다 정답이라고 할 수 있죠. 하나의 답만 나오는 것이 아닙니다. 

 

이렇게 되는 기본 조건은 Directed Acyclic Graph = DAG입니다. 
Acyclic는 비 순환적인 이라는 뜻입니다. 

 

위상 정렬 알고리듬은 보통 2가지 구현이 있습니다. 
하나는 깊이 우선 검색이고 하나는 indegree(자신에게 들어오는 간선)의 수를 이용하는 방법입니다. 
개인적으론 indegree를 이용하는 방법이 더 쉬운 것 같습니다만
앞서 코딩한 깊이 우선 검색의 연장선 상에서 깊이 우선 검색을 선택하도록 하겠습니다. 

위상 정렬 알고리듬은 깊이 우선 검색과 비슷합니다. 

깊이 우선 검색은 방문한 정점을 즉시 출력했던 반면에
위상 정렬은 현재 정점과 인접한 정점을 따라 깊이 우선 검색을 시행하고, 
더 이상의 정점이 없을 때의 (마지막?) 정점을 스택에 저장합니다. 

 

간략히 감만 잡아보겠습니다. 

          / [3]
[0] - [1] - [2] - [4]
                \ [5]

class Graph:
    def __init__(self):
        self.graph = {}
        self.marked = set()

    def add(self, v, w):
        self.graph.setdefault(v, {w})
        self.graph[v].add(w)
        self.graph.setdefault(w, {v})
        self.graph[w].add(v)

    def show(self):
        print(self.graph)

    def init_marked(self):
        self.marked.clear()

    def top_sort_helper(self, v, stack):
        self.marked.add(v)
        print('Visited vertex:', v)
        for w in self.graph[v]:
            if w not in self.marked:
                self.top_sort_helper(w, stack)
        stack.append(v)
        print('Stacked vertex:', v)

    def top_sort(self):
        stack = []
        for v in self.graph:
            if v not in self.marked:
                self.top_sort_helper(v, stack)
        for _ in range(len(stack)):
            v = stack.pop()
            if v in self.marked:
                print(v, end=' ')


g = Graph()
g.add(0, 1)
g.add(1, 2)
g.add(2, 5)
g.add(1, 3)
g.add(2, 4)

g.show()
g.top_sort()

{0: {1}, 1: {0, 2, 3}, 2: {1, 4, 5}, 5: {2}, 3: {1}, 4: {2}}
Visited vertex: 0
Visited vertex: 1
Visited vertex: 2
Visited vertex: 4
Stacked vertex: 4
Visited vertex: 5
Stacked vertex: 5
Stacked vertex: 2
Visited vertex: 3
Stacked vertex: 3
Stacked vertex: 1
Stacked vertex: 0
0 1 3 2 5 4 

          / [3]
[0] - [1] - [2] - [4]
                \ [5]

방문 순서와 저장 순서의 차이를 알 수 있습니다. 

 

사실 이 코드에는 문제가 있습니다.
0부터 입력하지 않으면 결과가 엉망이 됩니다. 

 

마지막에 0 노드를 입력해보겠습니다. 

g = Graph()
g.add(1, 2)
g.add(2, 5)
g.add(1, 3)
g.add(2, 4)
g.add(0, 1)

g.show()
g.top_sort()

{1: {0, 2, 3}, 2: {1, 4, 5}, 5: {2}, 3: {1}, 4: {2}, 0: {1}}
Visited vertex: 1
Visited vertex: 0
Visited vertex: 2
Visited vertex: 4
Visited vertex: 5
Visited vertex: 3
1
3
2
5
4
0

이수할 수 없는 순서가 나옵니다. 

 

이건 많이 찜찜하니까...
해결해 보겠습니다.

 

코드를 조금만 수정해도 작동하도록

조건을 만들어야겠습니다. 

0부터 입력하라고 하면 되지않...

선수과목은 후수과목(?)보다 작은 숫자가 되도록 과목코드(번호)를 할당합니다. 
0 이상 연속된 양의 정수만 과목코드가 될 수 있습니다. 
과목의 총 수를 미리 입력합니다.

이런 조건들이 있으면 리스트를 사용해서 풀 수 있을 것 같습니다. 

class Graph:
    def __init__(self, length):
        self.graph = [set() for _ in range(length)]
        self.marked = set()

    def add(self, v, w):
        self.graph[v].add(w)
        self.graph[w].add(v)

    def show(self):
        print(self.graph)

    def init_marked(self):
        self.marked.clear()

    def top_sort_helper(self, v, stack):
        self.marked.add(v)
        print('Visited vertex:', v)
        for w in self.graph[v]:
            if w not in self.marked:
                self.top_sort_helper(w, stack)
        stack.append(v)
        print('Stacked vertex:', v)

    def top_sort(self):
        stack = []
        for v in range(len(self.graph)):
            if v not in self.marked:
                self.top_sort_helper(v, stack)
        for _ in range(len(stack)):
            v = stack.pop()
            if v in self.marked:
                print(v, end=' ')


g = Graph(6)  # 요소의 총 갯수를 미리 입력합니다.
g.show()
g.add(1, 2)
g.add(2, 5)
g.add(1, 3)
g.add(2, 4)
g.add(0, 1)

g.show()
g.top_sort()

[None, None, None, None, None, None]
[{1}, {0, 2, 3}, {1, 4, 5}, {1}, {2}, {2}]
Visited vertex: 0
Visited vertex: 1
Visited vertex: 2
Visited vertex: 4
Stacked vertex: 4
Visited vertex: 5
Stacked vertex: 5
Stacked vertex: 2
Visited vertex: 3
Stacked vertex: 3
Stacked vertex: 1
Stacked vertex: 0
0 1 3 2 5 4 

          / [3]
[0] - [1] - [2] - [4]
                \ [5]