Chapter08. 그래프

08-1 그래프란?

그래프(graph): 복잡하게 연결된 객체 사이의 관계를 효율적으로 표현할 수 있는 자료구조

 

그래프의 유래

과거 독일의 도시였던 쾨니히스베르크라는 곳에 강이 흐르고 있고 4개의 지역들을 연결하기 위해 7개의 다리 존재

도시의 사람들 사이에서 '모든 다리를 한 번씩만 건너서 출발했던 장소로 돌아올 수 있을까?' 라는 문제가 돌았음

쾨니히스베르크 도시의 문제

해당 문제를 수학자 레온하르트 오일러(Leonhard Euler)가 처음으로 해결

오일러는 해당 문제를 '위치'라는 객체는 정점(vertex)으로, 위치 간의 관계인 '다리'는 간선(edge)로 표현하여 그래프 문제로 변환하였음

그래프로 변환

오일러는 그래프에 존재하는 모든 간선을 한 번만 통과하면서 처음 정점으로 되돌아오는 경로를 오일러 경로(Eulerian tour)라 정의

그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다 는 오일러의 정리를 증명하였음

 

따라서 위 그래프는 오일러 경로가 존재하지 않음

 

그래는 정점의 집합과 간선의 집합으로 구성되어 수학적으로 G = (V, E)와 같이 표시됨

V, E는 각각 정점과 간선들의 집합

 

정점들 자체로는 큰 의미가 없지만, 이들을 간선으로 연결하면 '관계'가 만들어지고 그래프가 형성됨

정점은 객체, 간선은 객체 간의 관계를 나타냄

정점 A, B를 연결하느 간선은 (A, B)와 같이 정점의 쌍으로 표현

 

그래프의 종류

그래프는 간선의 방향성과 정점 간의 연결 정도에 따라 여러 가지로 나뉨

 

무방향 그래프(undirected graph)

두 정점을 연결하는 간선에 방향성이 없는 그래프, 간선은 양방향으로 갈 수 있는 길을 의미함

(A, B)와 (B, A)는 동일한 간선

위 그림의 경우,

V(G1) = {A, B, C, D}

E(G1) = {(A, B), (A, C), (A, D), (B, C), (C, D)} 

정점의 집합 V(G)와 간선의 집합 E(G)로 표현할 수 있음

 

방향 그래프(directed graph)

간선에 방향이 있는 그래프, 다이그래프(digraph)라고도 함

간선은 한 방향으로만 갈 수 있는 길을 의미함

A → B 는 <A, B>로 표현, <A, B>와 <B, A>는 서로 다른 간선

위 그림의 경우,

V(G3) = {A, B, C, D}

E(G3) = {<A, B>, <A, C>, <B, C>, <C, D>, <D, A>} 로 표현

 

완전(complete) 그래프

그래프의 모든 정점 사이에 간선이 존재하는 그래프

정점이 n개인 무방향 완전 그래프는 n*(n-1)/2 개의 간선을 가지고, 방향 그래프는 n*(n-1)개의 간선을 가짐

 

부분 그래프(subgraph)

원래의 그래프에서 정점이나 간선 일부만을 이용해 만든 그래프

위 그림에서 G1, G2, G3은 그래프 G의 부분 그래프

 

가중치 그래프(weighted graph)

간선에 가중치가 할당된 그래프를 가중치 그래프 또는 네트워크(network)라고 말함

 

그래프의 용어

• 인접(adjacent): 간선으로 연결된 두 정점을 인접해 있다고 말함
• 정점의 차수(degree): 그 정점에 연결된 간선의 수
  방향 그래프에서는 차수가 두 가지로 나뉨
  진입 차수(in-degree): 외부에서 오는 간선의 수 / 진출 차수(out-degree): 외부로 향하는 간선의 수
• 경로(path): 간선을 따라갈 수 있는 길을 순서대로 나열한 것
  경로를 구성하는 간선의 수를 경로 길이(path length)라고 함
• 단순(simple) 경로: 반복되는 간선이 없는 경로
• 사이클(cycle): 시작 정점과 종료 정점이 같은 단순 경로
• 연결(connected) 그래프: 모든 정점 사이에 경로가 존재하는 그래프
• 트리(tree): 사이클을 가지지 않는 연결 그래프

 

---

08-2 그래프의 표현

인접 행렬을 이용한 표현

인접 행렬(adjacency matrix): 간선들의 집합을 표현하는 2차원 배열

그래프의 정점 개수가 n이라면 인접 행렬의 크기는 n ⨉ n, 행렬의 각 성분이 두 정점의 연결 관계를 나타냄

간선이 존재하는 경우 1, 존재하지 않는 경우 0으로 표시

 

무방향 그래프에서는 인접 행렬이 항상 대칭행렬

→ 상위 삼각이나 하위 삼각만 저장하여 메모리 절약 가능

자신에서 출발해서 자신으로 들어오는 간선은 없기 때문에 행렬의 대각선 성분은 모두 0으로 표시

 

인접 리스트를 이용한 표현

인접 리스트(adjacency list): 각 정점과 인접한 정점들을 나타내는 리스트

 

인접 행렬 vs 인접 리스트

• 인접 행렬의 정점이 n개인 그래프를 표현하기 위한 메모리 양은 n^2이므로 인접 리스트보다 약간 불리
• 그래프에 간선 (u, v)가 있는 지 검사할 때, 행렬은 해당 성분을 바로 검사하지만, 인접 리스트는 정점 u의 인접 리스트에서 v가 있는지 하나씩 검사 → 인접 리스트가 불리

메모리 사용량이 중요하거나 정점에 비해 간선이 별로 없는 희소 그래프(sparse graph) → 인접 리스트

정점끼리의 인접 여부를 빨리 알아내야 하거나, 완전 그래프, 조밀 그래프(dense graph) → 인접 행렬

 

---

08-3 그래프 순회

그래프 순회: 하나의 정점에서 시작하여 그래프의 모든 정점을 한 번씩 방문하는 작업

순회 방법

• 깊이 우선 탐색(DFS: Depth First Search): 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없으면 가장 가까운 갈림길로 다시 돌아와 다른 방향 탐색 시작
• 너비 우선 탐색(BFS: Breadth First Search): 시작 정점에서 가까운 정점을 먼저 방문하고 먼 정점을 나중에 방문

깊이 우선 탐색

시작 정점에서 한 방향으로 갈 수 있는 곳까지 깊이 탐색을 진행하다가 더 이상 갈 곳이 없으면 가장 최근에 만났던 갈림길 정점으로 되돌아 옴

후입선출 구조의 스택에 저장

 

깊이 우선 탐색(인접행렬 방식)

def DFS(vtx, adj, s, visited):
    print(vtx[s], end=' ')
    visited[s] = True

    for v in range(len(vtx)):
        if adj[s][v] != 0:
            if visited[v] == False:
                DFS(vtx, adj, v, visited)

 

너비 우선 탐색

가까운 정점부터 살피고 먼 정점을 찾아감

큐 사용

 

너비 우선 탐색(인접 리스트 방식)

from queue import Queue
def BFS_AL(vtx, aList, s):
    n = len(vtx)
    visited = [False]*n
    Q = Queue()
    Q.put(s)
    visited[s] = True
    while not Q.empty():
        s = Q.get()
        print(vtx[s], end=' ')
        for v in aList[s]:
            if visited[v]==False:
                Q.put(v)
                visited[v] = True

 

---

08-4 신장 트리

신장 트리(spanning tree): 그래프 내 모든 정점을 포함하는 트리

그래프의 정점은 모두 포함, 간선은 일부만을 포함하여 트리의 형태(사이클이 없어야 함)를 이루어야 함

하나의 그래프에는 여러 개의 신장 트리 가능

 

그래프의 정점 수가 n이면 신장 트리는 정확히 n-1 개의 간선으로 모든 정점을 연결해야 함

깊이 우선이나 너비 우선 탐색 도중에 사용된 가선들만 모으면 신장 트리가 만들어짐

 

DFS를 이용한 신장트리(인접행렬 방식)

def ST_DFS(vtx, adj, s, visited):
    visited[s] = True
    for v in range(len(vtx)):
        if adj[s][v] != 0:
            if visited[v] == False:
                print("(", vtx[s], vtx[v], ")", end=' ')
                ST_DFS(vtx, adj, v, visited)

DFS 탐색 도중에 추가되는 간선을 출력

 

---

08-5 최소 비용 신장 트리

최소 신장 트리(MST: Minimum Spanning Tree) or 최소 비용 신장 트리: 가중치 그래프의 여러 신장 트리 중에서 간선의 가중치 합이 최소인 것

• 그래프의 모든 정점은 연결되어야 함
• 연결에 필요한 간선의 가중치 합이 최소가 되어야 함

 

최소 신장 트리를 구하는 방법에는 Kruskal과 Prim의 알고리즘 존재

 

프림 알고리즘

하나의 정점에서부터 시작하여 최소 신장 트리(MST)를 단계적으로 확장해나가는 방법 사용

1. 처음에는 MST에 시작정점만 포함
2. 현재까지 만들어진 MST에 인접한 정점 중에서 간선의 가중치가 가장 작은(최소 간선) 정점을 선택하여 MST 확장
3. MST에 모든 정점이 삽입될 때까지 과정을 반복

프림의 최소 신장 트리 알고리즘(자연어)

Prim()
그래프에서 시작정점을 선택하여 초기 트리(MST)를 만듭니다.
MST와 인접한 정점 중 간선의 가중치가 가장 작은 정점 v를 선택합니다.
v와 이때의 간선을 MST에 추가합니다.
아직 모든 정점이 삽입되지 않았으면 2행으로 이동합니다.

 

정점들의 상태를 저장할 배열 두개 사용, 배열의 크기는 정점 수와 같음

• selected[ ]: 정점이 MST에 포함되었는지를 기록
  selected[v]가 True면 v가 MST에 포함되었음을 의미
  맨 처음에는 MST가 공백 트리이므로 배열의 모든 요소가 False가 되고, 단계마다 선택되는 정점이 True로 변경됨
• dist[ ]: 현재까지 구성된 MST와 정점 사이의 최단 거리를 저장
  처음에는 시작정점의 값만 0이고 나머지는 모두 무한대
  새로운 정점이 추가되면 그 정점과 인접한 정점의 최단 거리가 짧아질 수 있음

아직 선택되지 않은(selected가 False인) 정점 중에서 dist가 최소인 것을 찾으면 됨

프림 알고리즘의 구현

MST에 포함되지 않은 최소 dist의 정점 찾기

INF = 999
def getMinVertex(dist, selected):
    minv = 0
    mindist = INF
    for v in range(len(dist)):
        if selected[v]==False and dist[v]<mindist:
            mindist = dist[v]
            minv = v
        return minv

 

프림의 최소 신장 트리 알고리즘

def MSTPrim(vertex, adj):
    n = len(vertex)
    dist = [INF] * n
    dist[0] = 0
    selected = [False] * n

    for _ in range(n):
        u = getMinVertex(dist, selected)
        selected[u] = True
        print(vertex[u], end=' ')
        for v in range(n):
            if adj[u][v] != INF and not selected[v]:
                if adj[u][v]<dist[v]:
                    dist[v]=adj[u][v]

        print(': ', dist)

 

프림 알고리즘의 빠르기

외부 루프: 정점의 수 n만큼 반복

내부 루프: getMinVertex() 함수 반복문 n번 반복, 21행 내부 루프 n번 반복

⇒ 외부와 내부 루프의 반복 횟수의 곱에 비례 → O(n^2)