11. 자료구조론 - Graph(1) Intro, Topological Sort

Graph

그래프는 여러 개의 정점(Vertex, node)들이 간선(Edge)으로 연결된 자료구조입니다.

• Directed graph : 방향이 있는 간선들로 이루어진 그래프
• Undirected graph: 방향이 없는 간선들로 이루어진 그래프

방향이 있는 그래프 G = (V, E)가 다음과 같을 때,

V = {1, 2, 3}, E = {(1, 2}, {2, 1}, {2, 3}, {3, 1}, {3, 3}} 이 됩니다.

 

Directed graph G = (V, E)에서 edge(u, v)가 의미하는 바는 

1. u가 v와 연결되어있고, 2. u가 initial vertex이고, 3. v는 terminal vertex

입니다.

vertex에는 두 종류의 degree가 있습니다.

vertex v의 in-degree : 정점 v로 들어오는 간선의 개수 (v를 terminal vertex로 하는 간선의 개수)
vertex v의 out-degree : 정점 v에서 나가는 간선의 개수 (v를 initial vertex로 하는 간선의 개수)

이때, 간선 하나는 무조건 in-degree 하나, out-degree 하나가 생기도록 하므로, 모든 in-degree의 합과 모든 out-degree의 합은 간선의 개수와 같습니다.
$$ \sum_{v \in V} indegree(v) = \sum_{v \in V} outdegree(v) = \left| E \right|$$

• Path : 그래프에서 path는 정점들의 sequence
• Length of path : path에 있는 간선의 개수
• Cycle : 시작과 끝이 같은 정점인 그래프
• Path나 cycle이 같은 정점을 두 번 이상 포함하고있지 않으면 (처음과 마지막 제외) simple하다고 합니다.
• DAG (Directed Acyclic Graph) : cycle이 없는 directed graph

그래프를 표현하기 위해 이차원배열 Matrix를 사용할 수도 있고, 배열을 사용할 수도 있습니다.

Adjacency Matrices (인접행렬) 를 이용한 그래프 표현

정사각형의 이차원 배열을 이용하여 그래프에서 어떤 정점들이 연결되어있는지 나타내는 방법입니다. 

인접행렬 A에 대해 A[u][v] = w이면 정점 u에서 v 로 간선이 연결되어 있는 것이고, 0이면 연결되어있지 않은 것입니다.

w는 간선에 주어지는 가중치를 의미하는 것으로 딱히 가중치가 없으면 w=1이 됩니다.

• 장점 : 그래프를 간단하게 나타낼 수 있음
• 단점 : 열과 행 개수가 모두 $\left| V \right|$ 이어야하므로 무조건 $\Theta (\left| V \right|^2)$ 만큼의 공간이 필요하다. 
• 따라서 간선의 개수가 최댓값 $\left| V \right|^2$ 에 가까운 빽빽한 그래프일 때 적합한 방식이고, 간선의 개수가 별로 없다면 아래의 인접배열 방식이 더 적합하다. 

Adjacency lists 를 이용한 그래프 표현

각 정점마다 인접한 정점들의 리스트를 관리하는 방법입니다. 

배열의 인덱스를 통해 정점을 표현하고, 각 배열요소는 링크드리스트의 헤더가 되어 해당 정점에 인접한 정점들이 링크드리스트에 연결됩니다 .

우선 배열이 정점의 개수 $\left| V \right|$ 크기만큼 필요하고, 각 배열마다 연결된 링크드리스트에 아이템이 간선의 개수만큼 달려있으므로 $O(\left| E \right|)$만큼의 공간이 필요합니다.

따라서 필요한 공간복잡도는 $O( \left| V \right| + \left| V \right| )$가 됩니다. 

존재하는 간선에 대한 공간만 필요하므로 sparse한 그래프에 적합한 방식입니다. 

하지만 간선을 표현하는데 사용하는 링크드리스트는 다음노드를 가리키는 포인터를 담고있어서 일반 배열보다 공간을 많이 사용하므로, dense한 그래프에는 위의 방식이 더 적합할 수 있습니다.

 

Topological Sorting (위상 정렬)

우선 다음의 두 용어를 이해해야합니다. 

Partial Ordering : 집합S에서 관계 R이 reflexive, antisymmetrix, transitive하면 그것은 partial ordering이다.
예를들어 R이 $\geq$ 일 때,
- reflexive : 모든 정수 a에 대해 a $\geq$ a이다.
- antisymmetric : a $\geq$ b이고 b $\geq$ a 이면 a = b 이다.
- transitive : a $\geq$ b이고 b $\geq$ c 이면 a $\geq$ c 이다.
따라서 $\geq$는 정수의 집합에서 partial ordering이다.
ex) 나눗셈 기호 |는 모든 양수 집합에서 partial ordering이다. 

Total ordering : 만약 (S, R)이 partial ordering set이고 S의 모든 두 요소가 비교가능하다면, S는 totally ordered (linearly ordered set, chain)이다.
ex) (Z, $\geq$) 는 어떤 두 요소에서든 a $\geq$ b 또는 b $\geq$ a를 만족하기 때문에 totally ordered이다.
ex) (Z+, |)는 5|7도 성립하지 않고 7|5도 성립하지 않으므로 totally ordered가 아니다. 

Topological sorting은 partial ordering을 total ordering로 변환하는 방법입니다. 

예를 들어, partical ordered set ({1, 2, 4, 5, 12, 20}, |)을 total ordering으로 변환해보겠습니다. 

위와 같이 | 연산이 성립하는 수들을 화살표로 연결해두고, 더 이상 자신을 나눌 수 있는 수가 없는 수들을 순서대로 빼내면 total ordering이 됩니다.

이때, 동시에 꺼낼 수 있는 수가 두 개 이상이라면, 어떤 수를 먼저 꺼내든 상관 없습니다. 따라서 total ordering은 여러가지가 될 수 있습니다. 

 

위에서는 어렵게 말했지만, 쉽게 말하면 Topological Sorting은 DAG (Directed Acyclic Graph)에서 정점들을 정렬하는 방식입니다. DAG가 아니라면 Topological sorting은 사용할 수 없습니다. 

정렬 방식은, 정점x에서 정점y로 가는 경로가 존재한다면 y는 x 뒤로 정렬합니다. 

즉, 순서가 있는 여러가지 일들이 있을 때 순서의 방향성을 거스르지 않고 일들을 정렬하는 것입니다 .

 

예를 들어 여러가지 과목들이 있고, 어떤 과목을 듣기 위해서는 반드시 들어야하는 선행과목들이 있다고 하겠습니다.

다음과 같이 선행요건을 DAG로 나타낼 수 있습니다. 선행요건을 위반하지 않고 과목을 들을 수 있는 순서를 topological sorting을 이용해 구할 수 있습니다. 

이를테면, 자료구조 ->데이터베이스->운영체제->선형대수->네트워크->이산수학->컴퓨터구조 순으로 과목을 수강할 수 있습니다. 

 

알고리즘

Topological sorting을 구현하기 위한 알고리즘은 다음과 같습니다. 

간단하게 말하면, 그래프에서 특정 정점으로 들어오는 간선이 하나도 없으면 해당 정점은 선행하는 정점이 하나도 없는 것이므로 자유로운 정점이 됩니다. 따라서 그런 정점을 차례차례 찾아 그래프에서 꺼내주면됩니다. 

 

1. in-degree = 0 인 정점 v을 찾는다.

2. v를 정렬된 리스트에 넣는다.

3. v를 그래프에서 삭제하고 v에서 시작하는 간선들도 모두 지운다. 

4. v에 인접했던 노드들의 in-degree를 갱신해주고 1번으로 돌아가 반복한다. 

 

여기서 스택이나 큐와 같은 자료구조에 in-degree = 0인 정점들을 저장해두는 방법을 사용할 수 있습니다.

또한 그래프를 표현하기 위해서는 위의 adjacency list나 adjacency matrix를 사용합니다.

---

Topological Sorting 과정

코드

Topological sort의 구현은 아래 링크에서 볼 수 있습니다.

GitHub - dycha0430/HYU-CSE2010: Hanyang Univ. 자료구조론

간단하게 알고리즘의 흐름만을 코드로 나타내면 다음과 같습니다. 

void TopologicalSort(Graph g) {
    Stack s = CreateStack();
    Vertex v, w;
    int in_degree[];

    // 그래프 정점들의 in-degree를 확인하여 in_degree배열에 저장
    CheckIndegree(G, in_degree);

    for each vertex v in g {
        // in-degree가 0인 정점들을 스택에 넣음
        if (in_degree[v] == 0) Push(v, s);
    }

    while (!IsEmpty(s)) {
        v = Pop(s);
        print(v);
        // v에 인접한 모든 정점에 대해 in-degree를 하나 줄여주고, 줄인 값이 0이면 스택에 넣음
        for each vertex w adjacent to v {
            if (--in_degree[w] == 0) Push(w, s);
        }
    }
}

Analysis of Topological sort

그래프에서 정점의 개수 $n = \left| V \right|$, 간선의 개수 $e = \left| E \right|$ 라고 하면,

1. 위 수도코드에서 while문이 총 정점의 개수인 n번만큼 돌고, (모든 정점이 결국 한번씩은 스택에 들어갔다 나오므로)

2. 한 정점이 스택에서 pop되어 나올 때마다 해당 정점에 인접한 정점들의 in-degree를 하나씩 줄여주는 과정 (while문 내의 for문의 과정)이 전체적으로 보면 $\sum_{v \in V} outdegree(v)$ 만큼 발생합니다.

따라서 전체적인 시간복잡도는 다음과 같습니다. 

$$T(n) = n + \sum_{v \in V} outdegree(v) = \theta (n+e)$$