그래프 (Graph)

그래프란?

• 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조
• 그래프는 정점과 간선의 집합으로 구성된다.
• 그래프 G는 G = (V, E)로 정의한다.
  • V는 그래프에 있는 정점의 집합을 의미한다.
  • E는 정점을 연결하는 간선의 집합을 의미한다.

그래프의 구성

• 정점 (Vertex)
  • 연결할 객체
• 간선 (Edge)
  • 객체를 연결하는 선

그래프의 종류

무방향 그래프 (Undirected Graph)

• 두 정점을 연결하는 간선에 방향이 없는 그래프
• 무방향 그래프에서 정점V_i와 정점V_j을 연결하는 간선을 (V_i, V_j)로 표현한다.
• 무방향 그래프에서 (V_i, V_j)와 (V_j, V_i)는 같은 간선을 나타낸다.

방향 그래프 (Directed Graph)

• 간선에 방향이 있는 그래프
• 다이그래프(Digraph)라고도 부른다.
• 방향 그래프에서 정점V_i와 정점V_j을 연결하는 간선은 <V_i, V_j>로 표현한다.
  • 이 떄 V_i를 꼬리(Tail), V_j를 머리(Head)라고 부른다.
• 방향 그래프에서 <V_i, V_j>와 <V_j, V_i>는 서로 다른 간선으로 취급한다.

완전 그래프 (Complete Graph)

• 각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프
• 정점이 n개인 무방향 그래프에서는 최대 간선 수는 n(n-1)/2개가 된다.
• 정점이 n개인 방향 그래프에서는 최대 간선 수는 n(n-1)/2개가 된다.

부분 그래프 (Sub Graph)

• 원래 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프

가중 그래프 (Weight Graph)

• 정점을 연결하는 간선에 가중치(Weight)를 할당한 그래프
• 네트워크(Network)라고도 부른다.

그래프 관련 용어

• 그래프에서 두 정점 V_i와 V_j가 연결되어 간선 (V_i, V_j)가 있을 떄
  • 두 정점 V_i와V_j를 인접 (Adjacent)해 있다고 표현한다.
  • 간선 (V_i, V_j)는 정점 V_i와 V_j에 부속(Incident)되어 있다고 표현한다.
• 차수 (Degree)
  • 정점에 부속되어 있는 간선의 개수
• 진입 차수 (In-degree)
  • 정점을 머리로 하는 간선의 개수
• 진출 차수 (Out-degree)
  • 정점을 꼬리로 하는 간선의 개수
• 경로 (Path)
  • 그래프에서 간선을 따라갈 수 있는 길을 순서대로 나열한 목록
• 경로 길이 (Path Length)
  • 경로를 구성하는 간선 수
• 단순 경로 (Simple Path)
  • 모두 다른 정점으로 구성된 경로
• 사이클 (Cycle)
  • 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로
• DAG (Directed Acyclic Graph)
  • 방향 그래프이면서 사이클이 없는 그래프
• 그래프에서 두 정점 V_i와 V_j까지의 경로가 있으면 V_i와 V_j가 연결(Connected)되었다고 표현한다.
• 연결 그래프 (Connected Graph)
  • 떨어져 있는 정점이 없는 그래프
• 단절 그래프 (Disconnected Graph)
  • 연결되 있지 않은 정점이 있는 그래프

그래프의 순회

그래프 순회(Graph Traversal)란?

• 한 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하는 것
• 그래프 탐색(Graph Search)라고도 부른다.
• 종류
  • 깊이 우선 탐색
  • 너비 우선 탐색

깊이 우선 탐색 (DFC, Depth First Search)

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가
  더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 돌아와
  다른 방향의 간선으로 탐색을 계속하여 결국 모든 정점을 방문하는 순회 방법
• 가장 마지막에 만났던 갈림길 간선의 정점으로 되돌아가서
  다시 깊이 우선 탐색을 반복해야 하므로
  탐색 과정에서 정점 순서를 관리하기 위해 후입선출 구조의 스택을 사용한다.
• 순행 순서
  1. 시작 정점 v를 결점하여 방문한다.
  2. 정점 v에 인접한 정점을 확인한다.
     • 방문하지 않은 정점 w가 있는 경우
       1. 정점 v를 스택에 push하고 w를 방문한다.
       2. w를 v로 하여 다시 2단계를 반복한다.
     • 방문하지 않은 정점 w가 없는 경우
       1. 스택을 pop하여 받은 가장 마지막에 방문한 정점을 v로 설정한다.
       2. 다시 2단계를 반복한다.
  3. 스택이 공백이 될 때까지 2단계를 반복한다.

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

• 시작 정점에 인접한 정점을 모두 차례로 방문하고 나서
  방문했던 정점을 시작으로 다시 인접한 정점을 차례대로 방문하는 순회 방법
• 가까운 정점을 먼저 방문하고 멀리 있는 정점을 나중에 방문하는 순회 방법
• 인접한 정접에 대해 차례로 다시 너비 우선 탐색을 반복해야 하므로
  탐색 과정에서 정점 순서를 관리하기 위해 선입선출의 구조를 갖는 큐를 사용한다.
• 순행 순서
  1. 시작 정점 v를 결정하여 방문한다.
  2. 정점 v에 인접한 정점 중에서 방문하지 않은 정점을 차례로 방문하면서 큐에 enQueue한다.
  3. 방문하지 않은 인접한 정점이 없으면,
     방문했던 정점에서 인접한 정점을 다시 차례로 방문하기 위해
     큐에서 deQueue하여 받은 정점을 v로 설정하고 2단계를 반복한다.
  4. 큐가 공백이 될 떄까지 2단계 ~ 3단계를 반복한다.

신장 트리와 최소 비용 신장 트리

신장 트리

• 신장 트리 (Spanning Tree)
  • 모든 정점이 n개인 무방향 그래프 G에서 정점이 n개이고 간선이 n-1개인 트리 형태의 부분 그래프
  • 그래프 관점에서 트리는 사이클이 없는 연결 그래프다.
• 그래프에서 순회를 하면 n-1개의 간선을 이동하면서
  n개의 모든 정점을 방문하게 되므로
  순회 경로는 신장 트리가 된다.
• 종류
  • 깊이 우선 신장 트리 (Depth First Spanning Tree)
    • 깊이 우선 탐색을 이용하여 생성된 신장 트리
  • 너비 우선 신장 트리 (Breadth First Spanning Tree)
    • 너비 우선 탐색을 이용하여 생성된 신장 트리

최소 비용 신장 트리

• 최소 비용 신장 트리 (Minimum Cost Spanning Tree)
  • 가중치 합이 최소인 신장 트리
• 가중치 그래프에서 간선에 주어진 가중치는 비용, 거리, 시간을 의미하는 값이 될 수 있다.
• 무방향 가중치 그래프에서 신장 트리 비용은 신장 트리를 구성하는 간선 n-1개의 가중치를 합한 값이 된다.
• 관련 알고리즘
  • 크루스칼 알고리즘 Ⅰ
  • 크루스칼 알고리즘 Ⅱ
  • 프림 알고리즘

크루스칼 알고리즘 Ⅰ

• 크루스칼 알고리즘 Ⅰ은 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만든다.
• 크루스칼 알고리즘 Ⅰ의 순서
  1. 그래프 G의 모든 간선을 가중치에 따라 내림차순으로 정렬한다.
  2. 그래프 G에서 가장 높은 간선을 제거한다.
     • 이 때 정점을 그래프에서 분리시키는 간선은 제거할 수 없다.
     • 정점을 분리시키는 간선은 그 다음으로 가중치가 높은 간선을 대신 제거한다.
  3. 그래프 G에 간선이 n-1개만 남을 때까지 2단계를 반복한다.
  4. 그래프에 간선이 n-1개만 남으면 최소 비용 신장 트리가 된다.

크루스칼 알고리즘 Ⅱ

• 크루스칼 알고리즘 Ⅱ은 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만든다.
• 크루스칼 알고리즘 Ⅱ의 순서
  1. 그래프 G의 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
  2. 그래프 G에서 가장 낮은 간선을 삽입한다.
     • 이 때 사이클을 형성하는 간선은 삽입할 수 없다.
     • 사이클을 형성하는 간선은 그 다음으로 가중치가 낮은 간선을 대신 삽입한다.
  3. 그래프 G에 간선이 n-1개 삽입될 때까지 2단계를 반복한다.
  4. 그래프에 간선이 n-1개가 되면 최소 비용 신장 트리가 된다.

프림 알고리즘

• 프림 알고리즘은 크루스칼 알고리즘처럼 미리 간선을 정렬하지 않고,
  하나의 정점에서 시작하여 트리를 확장해 나가는 방법이다.
• 프림 알고리즘의 순서
  1. 그래프 G에서 시작 정점을 서낵한다.
  2. 선택한 정점에 부속된 모든 간선 중에서 가중치가 가장 낮은 간선을 연결하여 트리를 확장한다.
  3. 이전에 선택한 정점과 새로 확장된 정점에 부속된 모든 간선 중에서 가중치가 가장 낮은 간선을 삽입한다.
     • 이 때 사이클을 형성하는 간선은 삽입할 수 없다.
     • 사이클을 형성하는 간선은 그 다음으로 가중치가 낮은 간선을 대신 삽입한다.
  4. 그래프 G에 간선이 n-1개 삽입될 때까지 3단계를 반복한다.
  5. 그래프에 간선이 n-1개가 되면 최소 비용 신장 트리가 된다.

최단 경로

• 최단 경로 (Shortest Path)
  • 신장 트리가 아닌 가중치 그래프에서 정점 u와 정점 v를 연결하는 경로 중에서 가중치의 합이 최소인 경로
• 최단 경로를 구하려는 가중치 그래프의 가중치는 가중치 인접 행렬(Weight Adjacent Matrix)에 저장한다.
• 가중치 인접 행렬은 그래프에서 사용한 인접 행렬과 같은 형태의 2차원 배열이다.
• 두 정점 사이에 간선이 0이 아니라 무한대 값이 저장되어 있다고 가정한다.
• 각 정점은 자기 자신과 이어진 간선을 허용하지 않으므로 가중치 인접 행렬에서 대각선의 값은 0이다.
• 관련 알고리즘
  • 다익스트라 최단 경로 알고리즘
  • 플로이드 최단 경로 알고리즘

다익스트라 최단 경로 알고리즘

• 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘
• 자주 쓰인다.
• 정점 하나를 출발점으로 두고 다른 모든 정점을 도착점으로 하는
  단일점에서의 최단 경로 알고리즘 중 가장 많이 상요된다.
• 무방향 그래프나 방향 그래프에 모두 적용할 수 있다.
• 다익스트라 최단 경로 알고리즘의 순서
  1. 경로 길이를 저장할 배열 distance를 준비한다.
     • 시작 정점으로부터 각 정점에 이르는 경로의 길이를 저장하기 위한 배열 distance를 무한대로 초기화한다.
  2. 시작 정점 초기화
     • 시작 정점의 distance를 0으로 초기화하고 집합 S에 추가한다.
  3. 최단 거리 수정
     • 집합 S에 속하지 않은 정점 중에서 distance가 최소인 정점 u를 찾아 집합 S에 추가한다.
     • 새로운 정점 u가 추가되면 u에 인접하고 집합 S에 포함되지 않은 정점 w의 distance 값을 다음 식에 따라 수정한다.
       • distance[w] ← min(distance[w], distance[u] + weight[u][w])
     • 집합 S에 모든 정점이 추가될 때까지 3단계를 반복한다.

플로이드 최단 경로 알고리즘

• 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘
• 잘 쓰이지 않는다.
• k-최단 경로
  • 플로이드 최단 경로 알고리즘으로 만드는 최단 경로
• 플로이드 최단 경로 알고리즘에 대한 정보
  • A^k[v][w]는 0부터 k까지의 정점만을 이용한 정점 v에서 정점 w까지의 최단 경로를 의미한다.
  • 정점 0부터 정점 (k-1)까지의 정점을 고려한 최단 거리 A^k-1을 구한 상태에서 다음 정점 k를 고려할 때
    A^k-1[v][w]와 A^k-1[v][k] + A^k-1[k][w] 중에서
    작은 값에 따라 최단 경로가 수정된다.
    • A^k[v][w] ← min(A^k-1[v][w], A^k-1[v][k] + A^k-1[k][w])
  • A^-1 → A⁰ → A¹ → A² → … 순서로 정점을 늘려 최단 경로를 구하다가
    최종적으로 A^n-1을 구하면 n개의 모든 정점 사이의 최단 경로를 구하게 된다.
  • A^-1은 초기 상태로서 가중치 인접 행렬인 배열 weight 값이 되고,
    A^n-1[v][w]는 정점 0부터 정점 n-1까지의 모든 정점을 이용한 최단 경로가 된다.