C++로 쉽게 풀어쓴 자료구조/ 그래프

그래프란?

그래프는 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다.

그래프의 역사

그래프는 오일러에 의해 처음 창안되었다. 오일러는 ‘모든 다리를 한번만 건너서 출발했던 장소로 돌아올 수 있는가’라는 문제가 답이 없다는 것을 그래프 이론을 이용하여 증명하였다. 오일러는 이 문제의 핵심은 ‘A, B, C, D의 위치가 어떠한 관계로 연결되었는가?’라고 생각하고 ‘위치’라는 객체는 정점(vertex)로, 위치간의 관계인 ‘다리’는 간선(edge)로 표현하여 그래프 문제로 변환하였다. 오일러는 그래프에 존재하는 모든 간선을 한번만 통과하면서 처음 정점으로 되돌아오는 경로를 오일러 경로(Eulerian tour)라 정의하고, 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다는 오일러의 정리를 증명하였다.

그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다. 수학적으로는 G = (V, E)와 같이 표시한다. 여기서 V(G)는 그래프의 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다. 정점은 여러 특성을 가질 수 있는 객체를 의미하고, 간선은 이러한 객체 정점들 간의 관계를 의미하는데, 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. 정점은 노드(node)라고 불리며, 간선은 링크(link)라고도 불린다.

그래프는 시각적으로 표현하기도 하지만 시각적인 형태가 그래프의 정의는 아니다. 아래 그림의 그래프는 시각적으로 다르게 보이지만, 실제로는 동일한 그래프를 나타낸다.

그래프의 종류

무방향 그래프

간선에 방향이 표시되지 않은 그래프를 무방향 그래프라 한다. 하나의 간선은 양방향으로 갈 수 있는 길을 의미하고 (A, B)와 (B, A)는 동일한 간선이 된다. 아래 그림의 G1, G2 그래프를 정점과 간선의 집합으로 표현하면 다음과 같다.

V(G1) = {0, 1, 2, 3}, E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}
V(G2) = {0, 1, 2, 3}, E(G3) = {(0, 1), (0, 2)}

방향 그래프

간선에 방향성이 존재하는 그래프를 방향 그래프라 한다. 간선은 보통 화살표로 표시되는데, 일방통행 도로와 마찬가지로 한쪽 방향으로만 갈 수 있음을 의미한다. 정점 A에서 정점 B로만 갈 수 있는 간선은 <A, B>로 표시한다. 방향 그래프에서 <A, B>와 <B, A>는 서로 다른 간선이다. 위 그림의 G3은 방향 그래프로 아래와 같이 표현할 수 있다.

V(G3) = {0, 1, 2}, E(G3) = {<0, 1>, <1, 0>, <1, 2>}

가중치 그래프

간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프 또는 네트워크라 한다. 이제 간선은 두 정점간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있어 보다 복잡한 관계를 표현할 수 있다.

부분 그래프

그래프 G를 구성하는 정점의 집합 V(G)와 간선의 집합 E(G)의 부분 집합으로 이루어진 그래프를 부분 그래프라 한다. 아래 그림은 원래의 그래프 G1에 대한 몇 가지 부분 그래프를 보여주고 있다.

그래프 용어

인접 정점(adjacent vertex) 간선에 의해 직접 연결된 정점. 그림 11.7의 그래프 G1에서 정점 1의 인접 정점은 정점 0과 정점 2이다.
 정점의 차수(degree) 그 정점에 연결된 간선의 수. 무방향 그래프에서는 정점에 인접한 정점의 수를 말하는데, G1의 정점 0은 차수가 3이다.
무방향 그래프에서 모든 정점의 차수를 합하면 간선 수의 2배가 된다. 이것은 하나의 간선이 두 개의 정점에 인접하기 때문이다.
방향 그래프에서는 외부에서 오는 간선의 수를 진입 차수(in-degree)라 하고 외부로 향하는 간선의 수를 진출 차수(out-degree)라 한다. 그림 11.5의 방향 그래프 G3에서 정점 1은 진입 차수가 1, 진출 차수가 2이다. 방향 그래프에 있는 정점의 진입 차후 또는 진출 차수의 합은 방향 그래프의 간선의 수가 된다. 방향 그래프 G3의 간선의 수는 진입 차수의 합이나 진출 차수의 합과 같은 3이다.
 경로(path) 간선을 따라 갈 수 있는 길을 말하며 정점의 나열로 표시된다. 무방향 그래프에서 정점 s로부터 정점 e까지의 경로는 정점의 나열 s, v1, v2, … vk, e로서 나열된 정점들 간에는 반드시 간선 (s, v1), (v1, v2), … (vk, e)가 존재해야 한다. 만약 방향 그래프라면 <a, v1>, <v1, v2>, … <vk, e>가 있어야 한다. 그래프 G1에서 0, 1, 2, 3은 경로지만 0, 1, 3, 2는 경로가 아니다. 왜냐면 간선 (1, 3)이 존재하지 않기 때문이다.
 경로의 길이 경로를 구성하는데 사용된 간선의 수를 말한다.
 단순 경로(simple path)와 사이클(cycle) 경로 중에서 반복되는 간선이 없는 경로를 단순 경로라 한다. 그리고 단순 경로의 시작 정점과 종료 정점이 같다면 이러한 경로를 사이클이라 한다. 그림 11.5의 그리패 G1에서 경로 1, 0, 2, 3은 단순 경로이고 경로 1, 0, 2, 0은 단순 경로가 아니다. 그래프 G1에서 경로 0, 1, 2, 0은 사이클이 된다. 또 그래프 G3에서 경로 0, 1, 0도 사이클이 된다.
연결 그래프(connected graph) 그래프 G의 모든 정점들 사이에 경로가 존재하면 G를 연결 그래프라 부른다. 이 그래프에는 떨어진 정점이 없다. 그렇지 않은 그래프는 비연결 그래프라고 한다. 그림 11.5에서 G2가 비연결 그래프이다.
트리(tree) 그래프의 특수한 형태로서 사이클을 가지지 않는 연결 그래프를 트리라 한다. 그림 11.7의 부분 그래프 (b), (c), (d)는 모두 연결되어 있을 뿐만 아니라 사이클이 없으므로 트리이다.
완전 그래프(complete graph) 모든 정점 간에 간선이 존재하는 그래프를 완전 그래프라고 한다. 무방향 완전 그래프의 정점 수를 n이라 하면, 하나의 정점은 n-1개의 다른 정점과 연결되므로 간선의 수는 n x (n-1) / 2 가 된다.

그래프의 추상 자료형

  • 객체
    • 정점의 집합과 간선의 집합
  • 연산
    • create(): 그래프를 생성한다.
    • isEmpty(): 그래프가 공백 상태인지 확인한다.
    • insertVertex(v): 그래프에 정점 v를 삽입한다.
    • insertEdge(u, v): 그래프에 간선 (u, v)를 삽입한다.
    • deleteVertex(v): 그래프의 정점 v를 삭제한다.
    • deleteEdge(u, v): 그래프의 간선 (u, v)를 삭제한다.
    • adjacent(v): 정점 v에 인접한 모든 정점의 집합을 반환한다.

그래프의 표현

인접 행렬을 이용한 그래프의 표현

정점의 개수가 n인 그래프 G를 인접 행렬로 표현하면 n x n의 2차원 배열 형태인 인접 행렬(adjacency matrix)이 사용된다. 이 행렬을 M이라 하면 M의 각 원소들은 다음과 같은 값을 갖는다.

if(간선 (i, j)가 그래프에 존재) M[i][j] = 1,
그렇지 않으면 M[i][j] = 0

우리가 다루는 그래프에서 자체 간선은 허용하지 않으므로 인접 행렬의 대각선 성분은 모두 0으로 표시한다.

무방향 그래프 그림 11.10의 (a), (b)와 같이 무방향 그래프의 인접 행렬은 대칭 행렬이 된다. 이것은 간선 (i, j)가 정점 i에서 정점 j로의 연결 뿐만 아니라 정점 j에서 정점 i로의 연결을 동시에 의미하기 때문이다. 따라서 무방향 그래프의 경우, 배열의 상위 삼각이나 하위 삼각만 저장하면 메모리를 절약할 수 있다.
방향 그래프 그림 11.10의 (c)는 방향 그래프를 나타낸다. 방향 그래프의 인접 행렬은 일반적으로 대칭이 아니다.
가중치 그래프 만약 그래프의 간선들이 가중치를 갖고 있다면 행렬의 각 항목의 의미가 달라진다. 즉, 0과 1이 아니라 해당 간선의 가중치 값이 저장되어야 한다. 이 경우 정점 간의 간선이 없는 경우에 대한 처리에 조심해야 하는데, 단순히 0으로 처리하면 문제가 발생할 수 있기 때문이다.

 

n개의 정점을 갖는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수에 무관하게 항상 n2개의 메모리 공간이 필요하다. 인접 행렬을 이용하면 두 정점을 연결하는 간선의 존재 여부를 O(1) 시간 안에 즉시 알 수 있는 장점이 있다. 즉, 정점 u와 정점 v를 연결하는 정점이 있는지를 알려면 M[u][v]의 값을 조사하면 바로 알 수 있다. 또한 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로 O(n)의 연산에 의해 알 수 있다. 정점 i에 대한 차수는 다음과 같이 인접 배열의 i번째 행에 있는 값을 모두 더하면 된다.

반면 그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야 하므로 n2번의 조사가 필요하게 되어 O(n2)의 시간이 요구된다.

인접 리스트를 이용한 그래프의 표현

인접 리스트(adjacency list)는 그래프의 각 정점에 인접한 정점들을 연결 리스트로 표현하는 방법이다. 연결 리스트의 노드들은 인접 정점 정보를 저장하는데, 그래프에는 이러한 각 인접 리스트에 대한 헤더 포인터를 배열로 갖는다. 따라서 정점의 번호만 알면 각 정점의 연결 리스트에 쉽게 접근할 수 있다.

무방향 그래프의 경우 간선 (i, j)가 추가되면 정점 i의 연결 리스트에 j 노드를 추가해야 하고, 정점 j의 연결 리스트에도 i 노드를 추가해야 한다. 물론 인접 리스트에 노드를 추가하는 방법에 따라 연결 리스트 내에서 정점들의 순서가 달라질 수 있지만 이러한 순서는 중요하지 않다.

정점의 수가 n개이고 간선의 수가 e개인 무방향 그래프를 표시하기 위해서는 n개의 연결 리스트가 필요하고, n개의 헤더 포인터와 2e개의 노드가 필요하다. 따라서 인접 행렬 표현은 정점의 개수에 비해 간선의 개수가 매우 적은 희소 그래프(sparse graph)의 표현에 적합하다.

그래프에 간선 (i, j)의 존재 여부나 정점 i의 차수를 알기 위해서는 인접 리스트에서의 정점 i의 연결 리스트를 탐색해야 하므로 연결 리스트에 있는 노드의 수만큼, 즉 정점 차수만큼의 시간이 필요하다. 즉, n개 정점과 e개의 간선을 가진 그래프에서 전체 간선의 수를 알아내려면 헤더 노드를 포함하여 모든 인접 리스트를 조사해야 하므로 O(n+e)의 연산이 요구된다.

그래프의 탐색

그래프 탐색은 가장 기본적인 연산으로 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업이다. 그래프의 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색의 두 가지가 있다.

깊이 우선 탐색

깊이 우선 탐색(depth first search, DFS)은 스택을 이용한 미로 탐색과 유사하다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향을 다시 탐색하는 방법으로 출구를 찾을 수 있었다.

그래프에서 깊이 우선 탐색은 먼저 시작 정점에서부터의 임의의 인접한 정점으로 깊이 탐색을 진행한다. 이때 방문한 정점은 반드시 방문되었다는 표시를 해야 하고, 탐색은 아직 방문하지 않은 인접 정점으로만 가능하다. 만약 현재 정점에서 더는 방문하지 않은 인접 정점이 없으면 가장 마지막에 만났던 정점으로 되돌아간다. 거기서 다시 아직 방문하지 않은 인접 정점을 찾아 다시 동일한 방법의 탐색을 진행한다.

이 방법은 가장 최근에 만났던 갈림길로 되돌아가야 하므로 스택을 사용하여 구현할 수도 있지만, 스택 없이 순환 알고리즘의 형태로 다음과 같이 간단하게 나타낼 수 있다.

depthFirstSearch(v)
    v를 방문 했다고 표시;
    for all u ∈ (v에 인접한 정점) do
        if (u가 아직 방문 되지 않았다면)
            then depthFirstSearch(u)

너비 우선 탐색

너비 우선 탐색(breath first search, BFS)은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 너비 우선 탐색을 위해서는 가까운 거리에 있는 정점들을 차례로 저장하고, 들어간 순서대로 꺼낼 수 있는 자료구조가 필요하다. 물론 큐(queue)가 사용된다. 즉, 정점들이 방문될 때마다 큐에 인접 정점을 삽입하고, 더 이상 방문할 인접 정점이 없는 경우 큐의 맨 앞에서 정점을 꺼내 그 정점과 인접한 정점들을 차례대로 방문한다. 초기 상태의 큐에는 시작 정점만이 저장되고, 너비 우선 탐색 과정은 큐가 공백 상태가 될 때까지 계속한다.

breathFirstSearch(v)
    v를 방문되었다고 표시;
    큐 Q에 정점 v를 삽입;
    while(not is_empty(Q)) do
        Q에서 정점 w를 삭제;
        for all u ∈ (w에 인접한 정점) do
            if (u가 아직 방문되지 않았으면)
                then u를 큐에 삽입;
                         u를 방문되었다고 표시;

연결 성분

연결 성분(connected component)이란 최대로 연결된 부분 그래프를 말한다. 예컨대 11.19의 그래프에는 2개의 연결된 부분 그래프, 즉 2개의 연결 성분이 있다.

연결 성분을 찾기 위해서 깊이 우선 탐색이나 너비 우선 탐색을 이용한다. 먼저 그래프 상의 임의의 정점을 선택해 깊이 우선 탐색이나 너비 우선 탐색을 시작하면 시작 정점과 연결되어 있는 모든 정점들이 출력된다. 다음에 아직 방문되지 않은 정점을 선택해서 다시 탐색을 실행하면 그 정점을 포함하는 연결 성분이 또 찾아진다. 이 과정을 그래프의 모든 정점이 방문될 때까지 되풀이 하면 모든 연결 성분들을 찾을 수 있다.

신장 트리

신장 트리(spanning tree)란 그래프 내의 모든 정점을 포함하는 트리다. 신장 트리도 트리의 일종이므로 모든 정점들이 연결되어 있고 사이클이 없어야 한다. 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다.

신장 트리를 찾기 위해 깊이 우선 탐색이나 너비 우선 탐색을 이용할 수 있는데, 하나의 그래프에는 많은 신장 트리가 가능한 것에 유의하라

신장 트리는 깊이 우선이나 너비 우선 탐색 도중에 사용된 간선들만 모으면 만들 수 있다. 그림 11.20 (b)는 깊이 우선 탐색 때 사용된 간선으로만 만들어진 신장 트리이고 (c)는 너비 우선 탐색 때 사용된 간선으로만 만들어진 신장 트리이다. 깊이 우선 탐색 알고리즘을 변경하여 신장 트리 알고리즘을 나타내면 다음과 같다.

spanningTreeByDFS(v)
    v를 방문되었다고 표시;
    for all u ∈ (v에 인접한 정점) do
        if (u가 아직 방문되지 않았으면)
            then (v, u)를 신장 트리 간선이라고 표시;
                spanningTreeByDFS(u);

위상 정렬

그림 11.21의 (a)는 컴퓨터 관련 여러 과목들에 대해 선후수 관계를 보여주는 표이고 (b)는 그것을 방향 그래프로 그린 것이다. 자료구조를 수강하려면 먼저 컴퓨터개론을 수강해야 하고, 인공지능을 수강하려면 자료구조, 알고리즘, 운영체제를 모두 먼저 수강해야 한다.

이러한 방향 그래프에서 간선 <u, v>가 있다면 ‘정점 u는 정점 v에 선행한다’고 말한다. 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것을 방향 그래프의 위상 정렬(topological sort)이라고 한다.

그림 11.21의 그래프에는 많은 위상 정렬이 가능한데, 그 중 몇 개를 뽑으면 <A, B, C, D, E, F>, <B, A, C, D, E, F> 등이 있다. 이것은 순서대로 교과목을 수강하면 졸업할 수 있다는 것이다.

방향 그래프의 위상 정렬 알고리즘을 생각해 보자. 먼저 진입 차수가 0인 정점을 선택하고, 선택된 정점과 여기에 연결된 모든 간선을 삭제한다. 이때 삭제되는 간선과 연결된 남아 있는 정점들의 진입 차수를 변경한다. 이 과정을 반복하여 모든 정점이 삭제되면 알고리즘이 종료된다. 전체 과정에서 정점이 삭제되는 순서가 위상 순서(topological order)가 된다.

진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택하여도 무방하다. 따라서 하나의 그래프에는 여러 개의 위상 순서가 존재한다. 만약 그래프에 남아 있는 정점 중에 진입 차수 0인 정점이 없다면 위상 정렬은 불가능하다. 이것은 그래프에 사이클이 존재하는 것이고 모든 과목이 선수 과목을 갖는 것을 말한다.

그림 11.22는 위상 정렬 과정의 예를 보여주고 있다. 진입 차수가 0인 정점 B를 시작으로 정점 B와 간선을 제거하면 다음 단계에서 정점 E의 진입 차수가 0이 되므로 후보 정점은 A, E가 된다. 만약 정점 E를 선택하면 다음 단계에서는 오직 정점 A만이 후보가 된다. 다음에 정점 A가 선택되고 정점 C가 진입 차수가 0이 되어 선택 가능하게 된다. 다음에 정점 C, 정점 D, 정점 F를 선택하면 결과적으로 B, E, A, C, D, F가 된다.

topoSort()
    for i <- 0 to n-1 do
        if 모든 정점이 선행 정점을 가지면
            then 사이클이 존재하고 위상 정렬 불가;
        선행 정점을 가지지 않는 정점 v 선택;
        v를 출력;
        v와 v에서 나온 모든 간선들을 그래프에서 삭제;

 

It's only fair to share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기