그래프 순회(Graph Traversal) - 1

그래프(Graph)는 G = (V, E)로 표현 가능하다

그래프는 V는 정점(Vertex)이고 E는 간선(Edge)로 구성되어 있다.

 

많은 알고리즘 문제들을 푸는 핵심은 그래프의 측면에서 생각하는 것

 

그래프의 특징

- 무방향(undirected) 그래프 vs 방향(directed) 그래프

G = (V, E)에서 (x, y) 간선이 (y, x)을 의미하면 무방향 그래프, 아니면 방향 그래프

 

- 가중(weighted) 그래프 vs 비가중(unweighted) 그래프

각 에지에 가중치라고 부르는 수치가 할당

두 정점 사이의 최단 경로를 구할 때 분명해진다

비가중 그래프에서 최단 경로는 최소 에지의 개수이며 BFS로 구할 수 있다.

 

- 단순(simple) 그래프 vs 비단순(non-simple) 그래프

자기-루프(self-loop) 에지, 에지 (x, y)가 두 번 이상 나타나면 다중 에지(multiedge)

 

- 희박(sparse) 그래프 vs 조밀(dense) 그래프

희박 그래프 : 가능한 모든 정점 쌍들의 적은 부분만이 에지가 되는 그래프

조밀 그래프 : 정점 쌍들의 많은 부분이 에지가 되는 그래프

조밀 그래프에서는 에지 개수가 n에 대한 이차함수로 나타나지만 희박 그래프는 선형 함수

 

- 사이클 있는(cyclic) 그래프 vs 사이클 없는(acyclic) 그래프

트리(tree)는 사이클 없는 무방향 그래프

사이클 없는 방향 그래프(DAG)는 스케줄링 문제에서 나타나는 데, 방향 에지 (x, y)는 활동 x가 y보다 먼저 일어나야 한다는 것

위상 정렬은 DAG의 정점들에 순서를 매긴다

 

- 임베딩한(embedded) 그래프 vs 위상(topological) 그래프

 

- 묵시적(implict) 그래프 vs 명시적(explict) 그래프

그래프를 명시적으로 구성하지 않고 순회하는 경우이며, 그래프를 사용하면서 완성, 백트래킹(Backtracking)

 

- 라벨(labeled) 그래프 vs 라벨 없는(unlabeled) 그래프

 

그래프에 대한 자료구조

그래프 자료구조는 인접 행렬(adjancey matrix)과 인접 리스트(adjancey list)로 표현이 가능하다

- 인접 행렬 : G를 n * n 행렬 M을 이용해서 표현 할 수 있다. (i, j)가 G의 에지면 M[i, j] = 1이고 그렇지 않으면 0이다.

정점은 많고 에지가 적은 그래프에 대해서는 지나치게 많은 공간 할당할 수 있다

희박 그래프에서는 비효율적인 표현 방식

 

- 인접 리스트 : 희박 그래프에서 각 정점에 인접한 정점을 저장하는 연결 리스트를 이용하면 효율적으로 표현할 수 있다.

 

대부분의 그래프 응용에 대한 적절한 자료구조는 인접 리스트이다.

 

그래프 순회하기

그래프 순회의 핵심 아이디어는 각 정점을 처음 방문했을 때 표시하고 아직 완전히 탐색되지 않은 것들을 파악

부울(Boolean) 변수나 열거형(Enumerated Type)을 사용하여 방문한 정점 표시

 

각 정점의 상태

- 미발견(undiscovered) : 정점의 초기 상태

- 발견(discovered) : 정점이 발견되었으나 아직 인접한 모든 에지를 검사하지는 못함

- 처리 완료(processed) : 모든 인접한 에지를 방문한 후의 정점

 

미발견 -> 발견 -> 처리완료

 

너비 우선 탐색(Breadth-First Search: BFS)

순회하는 동안 원래 미발견 상태였던 그래프의 정점은 발견으로 바뀜

무방향 그래프에서 BFS는 발견한 정점 u에 대해 발견된 정점 v로 에지에 방향을 할당할 수 있으며 u을 v의 부모 노드라고 한다.

루트를 제외한 각 정점은 부모 노드를 정확히 하나 가지므로 그래프에 대한 트리(tree)가 정의된다

 

위 그림에서 BFS 트리는 루트로부터 트리의 다른 모든 노드까지 최단 경로를 정의한다

BFS 트리에서 나타나지 않은 그래프 에지들은 특별한 성질을 갖는다. /**/

트리 에지가 아닌 에지들은 부모 노드와 같은 레벨에 있는 노드를 가리키거나 부모 노드 바로 아래 레벨에 있는 노드를 가리킨다

이 성질은 트리에서 경로는 반드시 그래프에서 최단 경로이어야 한다는 사실로부터 쉽게 도출한다.

방향 그래프에서 v가 u보다 루트 노트에 더 가까이 있는 경우에 (u, v)가 존재할 수 있다.

 

구현

bfs(graph *g, int start) {
    queue q;
    int v;
    int y;
    edgenode *p;
    
    init_queue(&q);
    enqueue(&q, start);
    discovered(start) = true;
    
    while (empty_queue(&q) == false) {
        v = dequeue(&q);
        printf("processed vertex %d\n", v);
        processed[v] = true;
        p = g->edges[v];
        
        while (p != NULL) {
             y = p->y;
             if ((processed[y] == false) || g->directed)
                 printf("processed edge %d\n", v, y);
             if (discovered[y] == false) {
                 enqueue(&q, y);
                 discovered[y] = true;
                 parent[y] = v;
             }
             p = p->next;
        }
    }
}

연결 성분(Connected Component)

무방향 그래프에서 임의의 점정 쌍 사이에 경로가 존재하는 정점들의 극대(maximal) 집합

연결 성분은 정점의 순서와 무관하기 때문에 BFS를 이용하여 찾을 수 있다.

 

방향 그래프에서는 연결되어 있다는 것을 약연결성분과 강연결성분(Strongly Connected Component)가 있다.

 

그래프를 두 가지 색깔로 색칠하기

정점 색칠하기(vertex-coloring)은 어떤 에지도 같은 색을 가진 두 정점을 잇지 않도록 그래프의 각 정점에 색을 할당하는 문제

각 정점에 유일한 색을 할당하면 쉽게 충돌을 피할 수 있다. 목표는 가능한 적은 수의 색을 사용하는 것이다.

 

두 가지 색을 가지고 충돌 없이 색칠할 수 있는 그래프를 이분 그래프(bipartitle graph)라고 한다.

BFS를 확장하여 새로운 정점을 발견할 때마다 부모의 색과 다른 색을 칠할 수 있다.