그래프

• 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조

• 그래프 G

  • 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합

  • G = (V, E)

    • - V는 그래프에 있는 정점들의 집합

    • - E는 정점을 연결하는 간선들의 집합

그래프의 종류

• 무방향 그래프 (undirected graph)

  • 두 정점을 연결하는 간선에 방향이 없는 그래프

  • 정점 A와 정점 B를 연결하는 간선을 (A, B)로 표현

    • - (A, B)와 (B, A)는 같은 간선을 의미

• 무방향 그래프의 예)

  

• 방향 그래프 (directed graph), 다이그래프 (digraph)

  • 간선에 방향이 있는 그래프

  • 정점 A에서 정점 B를 연결하는 간선. 즉, A->B를 <A, B>로 표현

    • - A를 꼬리(tail), B를 머리(head)라고 한다.

    • - <A, B>와 <B, A>는 서로 다른 간선을 의미

• 방향 그래프의 예)

  

• 완전 그래프 (complete graph)

  • 각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프

  • 정점이 n개인 무방향 그래프에서 최대의 간선 수: n(n-1)/2개

  • 정점이 n개인 방향 그래프에서 최대 간선 수: n(n-1)개

  • 완전 그래프의 예)

    • G5는 정점의 개수가 4개인 무방향 그래프이므로 완전 그래프가 되려면 4(4-1)/2 = 6개의 간선 연결

    • G6은 정점의 개수가 4개인 방향 그래프이므로 완전 그래프가 되려면 4(4-1) = 12개의 간선 연결

      

• 부분 그래프 (subgraph)

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

  • 그래프 G와 부분 그래프 G'의 관계

    

  • 그래프 G1에 대한 부분 그래프의 예

    

• 가중 그래프 (weight graph), 네트워크 (network)

  • 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프

  • 가중치 그래프의 예)

    

그래프 관련 용어

• 그래프에서 두 정점 A와 B를 연결하는 간선 (A, B)가 있을 때, 두 정점 A와 B를 인접되어 있다고 하고, 간선 (A, B)는 정점 A와 B에 부속 되어 있다고 함

  • 그래프 G1에서 정점 A와 인접한 정점은 B와 D이고, 정점 A에 부속되어 있는 간선은 (A, B)와 (A, D)

    

• 차수(degree): 정점에 부속되어 있는 간선의 수

  

  • 무방향 그래프 G1에서 정점 A의 차수는 2, 정점 B의 차수는 3

  • 방향 그래프의 정점의 차수 = 진입차수 + 진출차수

    • 방향 그래프의 진입차수: 정점을 머리로 하는 간선의 수

    • 방향 그래프의 진출차수: 정점을 꼬리로 하는 간선의 수

    • 방향 그래프 G3에서 정점 B의 진입차수는 1, 진출차수는 2이므로 정점 B의 전체 차수는 1+2 = 3임

• 경로(path)

  • 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것. 즉, 정점 A에서 B까지 간선으로 연결된 정점을 순서대로 나열한 리스트

    

    • 무방향 그래프 G1에서 정점 A에서 정점 C까지는 A-B-C 경로와 A-B-D-C 경로, A-D-C 경로, 그리고 A-D-B-C경로가 있음

  • 경로 길이(path length) - 경로를 구성하는 간선의 수

• 단순 경로 (simple path)

  • 모두 다른 정점으로 구성된 경로

    

  • 그래프 G1에서 정점 A에서 정점 C까지의 경로 A-B-C는 단순경로이고, 경로 A-B-D-A-B-C는 단순경로가 아님

• 사이클 (cycle)

  • 단순경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로

    
    

  • 그래프 G1에서 단순경로 A-B-C-D-A와 그래프 G4에서 단순경로 A-B-A는 사이클이 됨

• DAG (directed acyclic graph)

  • 방향 그래프이면서 사이클이 없는 그래프

    

• 연결 그래프 (connected graph)

  • 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프. 즉, 떨어져있는 정점이 없는 그래프

  • 그래프에서 두 정점 A에서 B까지의 경로가 있으면 정점 A와 B가 연결되었다고 함. 트리는 사이클이 없는 연결 그래프

  • 단절그래프 - 연결되지 않은 정점이 있는 그래프

    

무방향 그래프 인접 행렬

• 무가중치 그래프

  • (정점1, 정점2) = (정점2, 정점1) -> 1로 표현

    

• 가중치 그래프

  • (정점1, 정점2) = (정점2, 정점1) -> 가중치로 표현

    

방향 그래프 인접 행렬

• 무가중치 그래프

  • (정점1, 정점2) = or != (정점2, 정점1) -> 1로 표현

    

• 가중치 그래프

  • (정점1, 정점2) = or != (정점2, 정점1) -> 가중치로 표현

    

그래프 순회 (graph traversal), 그래프 탐색 (graph search)

• 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하여 처리하는 연산

• 그래프 탐색 방법

  • 깊이 우선 탐색 (depth first search: DFS)

  • 너비 우선 탐색 (breadth first search: BFS)

• 깊이 우선 탐색 (DFS)

  

  • 탐색 순서: A-B-C-D-E

  • 순회 방법

    • 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법

    • 가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용

• 너비 우선 탐색 (BFS)

  

  • 탐색 순서: A-B-E-C-D

  • 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

  • 선입선출 큐 사용

신장 트리 (spanning tree)

• n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리

  

• 깊이 우선 신장 트리 (depth first spanning tree)

  • 깊이 우선 탐색을 이용하여 생성된 신장 트리

• 너비 우선 신장 트리 (breadth first spanning tree)

  • 너비 우선 탐색을 이용하여 생성된 신장 트리

    

• 최소 비용 신장 트리 (minimun cost spanning tree)

  • 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리

    • 가중치 그래프의 간선에 주어진 가중치

      • 비용이나 거리, 시간을 의미하는 값

  • 최소 비용 신장 트리를 만드는 알고리즘

    • 크루스칼 (kruskal)의 알고리즘

    • 프림 (Prime)의 알고리즘

크루스칼 알고리즘 I

• 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 방법

• 순서

  • 1. 그래프 G의 모든 간선을 가중치에 따라 내림차순으로 정렬한다.

  • 2. 그래프 G에서 가중치가 가장 높은 간선을 제거한다. 단, 이때 정점을 그래프에서 분리시키는 간선은 제거할 수 없으므로 이런 경우에는 그 다음으로 가중치가 높은 간선을 제거한다.

  • 3. 그래프 G에 간선이 n-1개만 남을때까지 2를 반복한다.

  • 4. 그래프에 간선이 n-1개만 남으면 최소 비용 신장 트리가 완성된다.

• 최종 결과

  

크루스칼 알고리즘Ⅱ

• 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만드는 방법

• 순서

  • 1. 그래프 G의 모든 간선을 가중치에 따라 오름차순으로 정리한다.

  • 2. 그래프 G에 가중치가 가장 낮은 간선을 삽입한다. 단, 이때 사이클을 형성하는 간선은 삽입할 수 없으므로 그 다음으로 가중치가 낮은 간선을 삽입한다.

  • 3. 그래프 G에 간선이 n-1개 삽입될 때까지 2를 반복한다.

  • 4. 그래프 G의 간선이 n-1개가 되면 최소 비용 신장 트리가 완성된다.

• 최종 결과

  

프림 알고리즘

• 간선을 정렬하지 않고 하나의 정점에서 시작하여 트리를 확장해 나가는 방법

• 순서

  • 1. 그래프 G에서 시작 정점을 선택한다.

  • 2. 선택한 정점에 부속된 모든 간선 중에 가중치가 가장 낮은 간선을 연결하여 트리를 확장한다.

  • 3. 이전에 선택한 정점과 새로 확장된 정점에 부속된 모든 간선 중에서 가중치가 가장 낮은 간선을 삽입한다. 단, 사이클을 형성하는 간선은 삽입할 수 없으므로 이런 경우에는 그 다음으로 가중치가 낮은 간선을 선택한다.

  • 4. 그래프 G에 간선이 n-1개 삽입될 때까지 3을 반복한다.

  • 5. 그래프 G의 간선이 n-1개가 되면 최소 비용 신장 트리가 완성된다.

• 최종 결과

  

최단 경로 (Shortest Path)

신장 트리가 아닌 가중치 그래프, 즉 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 가중치의 합이 최소인 경로

• 가중치 인접 행렬 (Weight Adjacent Matrix)

  • 최단 경로를 구하려는 가중치 그래프의 가중치를 저장

  • 그래프에서 사용한 인접 행렬과 같은 형태의 2차원 배열, 두 정점 사이에 간선이 없으면 0이 아니라 ∞(무한대)값이 저장되어 있다고 가정.

  • 각 정점은 자기 자신과 이어진 간선을 허용하지 않으므로 가중치 인접 행렬에서 대각선 값은 0

  • 예)

    

• 다익스트라(Dijkstra) 최단 경로 알고리즘

  • 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구함

  • 단일점에서의 최단 경로 알고리즘 중 가장 많이 사용.

  • 무방향 그래프나 방향 그래프에 모두 적용 가능

  • 순서

    • 1. 경로 길이를 저장할 배열 distance 준비: 시작 정점으로부터 각 정점에 이르는 경로의 길이를 저장하기 위한 배열 distance를 ∞(무한대)로 초기화 한다.

    • 2. 시작 정점 초기화: 시작 정점의 distance를 0으로 초기화하고 집합 S에 추가한다.

    • 3. 최단 거리 수정: 집합 S에 속하지 않은 정점 중에서 distance가 최소인 정점 u를 찾아 집합 S에 추가한다. 새로운 정점 u가 추가되면 u에 인접하고 집합 S에 포함되지 않은 정점 w의 distance값을 다음 식에 따라 수정한다. 집합 S에 모든 정점이 추가될 때까지 3을 반복한다.

• 플로이드(Floyd) 최단 경로 알고리즘

  • 모든 정점 사이의 최단 경로를 구한 것

  • k-최단 경로 - 플로이드 최단 경로 알고리즘으로 만든 최단 경로