쉽게 배우는 알고리즘 9장 요약

Chapter 9. 그래프 알고리즘

1. 그래프

그래프: 현상이나 사물을 정점과 간선으로 표현하는 것
    정점(Vertex): 대상이나 개체
    간선(Edge): 이들간의 관계

사람들간의 친밀도를 나타내는 경우를 그래프로 표시한다면, 정점은 각각의 사람이 되고, 간선은 친밀한 사람들 사이를 선으로 연결한 것이 될 것이다.
간선에 숫자를 표시하여 친밀도의 크기를 표시할 수도 있고, 화살표로 방향을 줄 수도 있다. 방향을 가진 그래프를 유향 그래프(Directed Graph)라고 하고 방향이 없는 그래프를 무향 그래프(Undirected Graph)라고 한다.

n개의 정점의 집합 V와 이들간에 존재하는 간선의 집합 E로 구성된 그래프 G를 보통
    G = (V, E)
로 표시한다.

2. 그래프의 표현

2.1 인접행렬을 이용한 방법

그래프 G=(V,E)에서 정점의 총수가 n이라 하자 nXn 행렬을 준비한다. 정점 i와 정점 j간에 간선이 있으면 행렬의 (i,j)원소와 (j,i)원소의 값을 1로 할당한다. 가중치가 있는 경우는 1 대신 가중치를 할당하고 방향이 있는 경우는 방향에 맞게 값을 할당한다.

행렬 표현법은 n^2의 공간이 필요하고 행렬의 공간을 채우는데 n^2에 비례하는 시간이 걸린다. 따라서, 간선의 밀도가 높은 그래프에서는 좋지만 그렇지 않는 경우는 좋지 않다.

2.2 인접리스트를 이용한 방법

각 정점마다 리스트를 만든다. 각 정점에 인접한 정점들을 연결 리스트(linked list)로 매단다.

단순관계 그래프에서 리스트는 <정점번호, 다음 정점의 포인터>로 표시될 수 있고 가중치를 가진 그래프에서 리스트는 <정점번호, 가중치, 다음 정점의 포인터>로 표시될 수 있다.

3. 너비우선탐색(BFS)과 깊이우선탐색(DFS)

3.1 BFS

루트의 자식을 차례로 방문한다. 다음으로 루트 자식의 자식의 정점을 방문한다. 이런식으로 루트에서의 거리 순으로 방문한다.
BFS의 수행시간은 Theta(V+E)이다.

// G: 그래프
// s: 시작정점
BFS(G, s)
{
    // s를 제외한 모든 정점을 NO로 표시한다.
    for each v in V -{s} {
        visited[v] = NO;
    }
    visited[s] = Yes;
    enqueue(Q,s);
    while (Q가 비어 있지 않으면) {
        u = dequeue(Q);
        for each v in L(u) // 정점 u의 인접 리스트
            if (visited[v] == NO) {
                visited[v] = YES;
                enqueue(Q,v);
            }
        }
    }
}

3.2 DFS

루트의 자식 정점을 하나 방문한 다음, 아래로 내려갈 수 있는 곳까지 내려간다. 더이상 내려갈 수가 없으면 위로 되돌아오다가 내려갈 속이 있으면 즉각 내려간다.
DFS의 수행시간은 Theta(V+E)이다.

DFS(G)
{
    for each v in V {
        visited[v] = NO;
    }
    for each v in V {
        if (visited[v] == NO) {
            aDFS(v)
        }
    }
}

aDFS(v)
{
    visited[v] = YES;
    for each x in L(v) { // L(v): 정점 v의 인접리스트
        if (visited[x] == NO) {
            aDFS(x);
        }
    }
}

4. 최소신장트리(Minimum Spanning Tree)

간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소신장트리라 한다.

4.1 프림 알고리즘

집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 키워 나간다.
d에 대한 자료구조는 최소힙을 사용하면 시간을 개선할 수 있다.
수행시간은 O(E*logV)가 된다.

// G(V,E): 주어진 그래프
// r: 시작 정점
Prim(G, r)
{
    S는 공집합
    // 시작정점 r의 연결비용은 0으로하고 나머지 정점들의 연결비용은 무한대로 초기화한다.
    for each u in V {
        d[u] = 무한대
    }
    d[r] = 0;
    while (S != V) {
        u = extractMin(V-S, d);
        S = S + [u]; // 집합 S에 u를 포함시킨다.
        for each v in L(u) { // L(u): u의 인접 정점 집합
            if (v in V-S && w(u,v) < d[v]) {
                d[v] = w(u,v);
                tree[v] = u;
            }
        }
    }
}

extractMin(Q, d[])
{
    집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}

4.2 크루스칼 알고리즘

싸이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 최소신장트리를 만든다.
집합의 처리 방법으로 랭크를 이용한 Union과 경로압축을 이용한 Find-Set을 사용하면 시간을 아낄 수 있다.
수행시간은 O(E*logV)가 된다.

Kruskal(G)
{
    T는 공집합
    단 하나의 정점만으로 이루어진 n개의 집합을  초기화한다.
    모든 간선을 가중치의 크기순으로 정렬하여 배열 A[1...E]에 저장한다.
    while (T의 간선수 < n - 1) {
        A에서 최소비용의 간선(u,v)를 제거한다.
        if (정점 u와 v가 다른 집합에 속함) {
            T = T + (u,v);
            정점 u와 v가 속한 두 집합을 하나로 합친다.;
        }
    }
}

5. 위상 정렬

싸이클이 없는 유향 그래프 G=(V,E)에서 V의 모든 정점을 정렬하되 다음 성질을 만족해야 한다.
- 간선 (i,j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 나열되어야 한다.

topologicalSort(G)
{
    for each v in V {
        visited[v] = NO;
    }
    for each v in V {
        if (visited[v] == NO) {
            DFS-TS(v);
        }
    }
}

DFS-TS(v)
{
    visited[v] = YES;
    for each x in L(v) {
        if (visited[x] == NO) {
            DFS-TS(x);
        }
    }
    연결 리스트 R의 맨 앞에 정점 v를 삽입한다.
}

6. 최단경로

6.1 다익스트라 알고리즘(음의 가중치를 허용하지 않는 경우)

// G=(V,E): 주어진 그래프
// r: 시작으로 삼을 정점
Dijkstra(G, r)
{
    S는 공집합
    for each u in V {
        d[u] = 무한대
    }
    d[r] = 0;
    while (S != V) {
        u = extractMin(V-S, d);
        S = S + {u};
        for each v in L(u) {
            if (v in V-S && d[u] + w(u,v) < d[v]) {
                d[v] = d[u] + w(u,v);
                prev[v] = u;
            }
        }
    }
}

extractMin(Q, d[])
{
    집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}

6.2 벨만-포드 알고리즘(음의 가중치를 허용하는 경우)

BellmanFord(G, r)
{
    for each u in V {
        d[u] = 무한대;
    }
    d[r] = 0;
    for (int i=0; i<V; i++) {
        for each (u,v) in E {
            if (d[u] + w(u,v) < d[v]) {
                d[v] = d[u] + w(u,v);
                prev[v] = u;
            }
        }
    }
    // 음의 싸이클 존재여부 확인
    for each (u,v) in E {
        if (d[u] + w(u,v) < d[v]) {
            output "해없음"
        }
    }
}

6.3 모든쌍 최단경로 알고리즘

d.k(ij) : 정점 집합 {1,2, ..., k}에 속하는 정점들만을 중간 정점으로 거쳐서 i에서 j에 이르는 최단거리

d.k(ij) = w(ij) if k=0
            min(d.k-1(ij), d.k-1(ik) + d.k-1(kj)) if k>=1

FloydWarshall(G)
{
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            d(ij) = w(ij);
        }
    }
    for (int k=1; k<=n; k++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                d.k(ij) = min(d.k-1(ij), d.k-1(ik) + d.k-1(kj));
            }
        }
    }
}

6.4 싸이클이 없는 그래프의 최단경로

DAG-ShortestPath(G, r)
{
    for each u in V {
        d[u] = 무한대;
    }
    d[r] = 0;
    G의 정점들을 위상정렬한다.
    for each u in V { // 위상정렬 순서대로
        for each v in L(u) {
            if (d[u] + w(u,v) < d[v]) {
                d[v] = d[u] + w(u,v);
                prev[v] = u;
            }
        }
    }
}

7. 강연결요소

유향 그래프 G=(V,E)에서 V의 모든 정점쌍 (u,v)에 대해서 경로 u ~> v와 경로 v ~> u가 존재하면 그래프 G는 강하게 연결되었다고 말한다.
그래프에서 강하게 연결된 부분 그래프들을 각각 강연결요소라고 한다.

// f[v]: DFS를 수행하면서 v에 관한 한 더이상 할 일이 없는 상태가 된 시점
stronglyConnectedComponent(G)
{
    그래프 G에 대해 DFS(G)를 수행하여 각 정점 v의 완료시간 f[v]를 계산한다.
    G의 모든 간선들의 방향을 뒤집어 G(R)을 만든다.
    DFS(G(R))을 수행하되 앞에서 구한 f[v]가 가장 큰 정점을 시작점으로 잡는다.
    앞에서 만들어진 분리된 트리들 각각을 강연결요소로 리턴한다.
}