알고리즘 8강 (그래프)

학습개요

1. 이번 강의에서는 그래프와 관련된 기본 개념(정의, 종류, 용어, 구현 방법)을 우선 살펴본 후, 그래프에 대한 기본 연산으로 사용되는 그래프 순회 방법을 학습한다. 또한 그래프 순회를 활용해서 위상 정렬, 연결 성분, 강연결 성분을 구하는 방법에 대해서도 함께 살펴본다.

 학습목표

1. 그래프의 개념, 주요 용어 그리고 구현 방법을 이해할 수 있다.
2. 그래프의 순회 방법으로 깊이 우선 탐색과 너비 우선 탐색을 이해하고 적용할 수 있다.
3. 그래프 순회 방법을 적용하여 위상 정렬, 연결 성분, 강연결 성분을 구할 수 있다.

 주요용어

1. 그래프(graph)
   - 연결할 객체를 나타내는 정점(vertex)의 집합과 정점을 연결하는 간선(edge)의 집합으로 구성된 비선형 자료구조
2. 인접 행렬(adjacency matrix)
   - 정점의 집합 V={1,2,…,n}인 그래프 G에 대해서 2차원 배열 A=(n×n)으로 표현하는 방법
3. 인접 리스트(adjacency list)
   - 정점의 집합 V={1,2,…,n}인 그래프 G에 대해서 n개의 연결 리스트로 표현하는 방법으로, 각 연결 리스트는 임의의 정점 u에 대해서 인접한 모든 정점을 표현함
4. 그래프 순회(graph traversal)
   - 그래프의 모든 정점을 체계적으로 한 번씩 방문하는 방법으로, 깊이 우선 탐색과 너비 우선 탐색이 있음
5. 깊이 우선 탐색(depth first search)
   - 한 정점을 시작으로 매번 인접한 정점 중 한 곳으로 이동하며 탐색하는 방법
   - 최근의 주변 정점을 우선으로 탐색하는 방법
6. 너비 우선 탐색(breadth first search)
   - 시작 정점을 기준으로 거리가 가장 가깝게 인접한 정점을 우선으로 모두 방문한 후 시작 정점과의 거리가 점점 멀어지는 순서로 인접 정점들을 탐색하는 방법
   - 주변 정점 중에서 가장 오래된 것부터 우선 방문하는 방법
7. 위상 정렬(topological sort)
   - 무사이클 방향 그래프에서 모든 간선이 한 방향으로만 향하도록 정점을 한 줄로 나열하는 것
8. 연결 성분(connected component)
   - 주어진 무방향 그래프에서 임의의 두 정점 간의 경로가 존재하는 최대 부분 그래프
9. 강연결 성분(strongly connected component)
   - 주어진 방향 그래프에서 임의의 두 정점 사이에 양방향의 경로가 존재하는 최대 부분 그래프

정리하기

1. 기본 개념
    ⦁ 그래프 G=(V, E) → 연결할 객체는 나타내는 정점의 집합 V와 정점을 연결하는 간선의 집합 E의 집합
    - 종류 → 무방향 그래프 vs 방향 그래프, 가중 그래프
    - 주요 용어 → 인접, 부수, 부분 그래프, 경로, 경로의 길이, 차수(진입차수, 진출차수), 단순 경로, 사이클, 루프, 연결, 강하게 연결, 약하게 연결
    ⦁ 그래프의 구현 방법
    - 정점들의 관계를 나타내는 간선의 집합 E를 표현하는 것
    - 인접 행렬에 의한 구현 → |V|*|V| 행렬 사용, 조밀한(dense) 그래프에 적합
    - 인접 리스트에 의한 구현 → |V|개의 연결 리스트로 구성되며 각 연결 리스트는 임의의 정점 u에 대해서 인접한 모든 정점을 표현, 성긴(sparse) 그래프 표현에 적합
2. 그래프 순회
    ⦁ 그래프의 모든 정점을 체계적으로 한 번씩 방문하는 것 → 깊이 우선 탐색, 너비 우선 탐색
    ⦁ 깊이 우선 탐색
    - 한 정점을 시작으로 매번 인접한 정점 중 한 곳으로 이동하며 탐색하는 방법 → 최근의 주변 정점을 우선으로 방문하는 방법
    - 스택 구조를 통해 구현
    - 인접 리스트 O(|V|+|E|), 인접 행렬 O(|V|2)
    ⦁ 너비 우선 탐색
    - 시작 정점을 기준으로 거리가 가장 가깝게 인접한 정점을 우선으로 모두 방문한 후 시작 정점과의 거리가 점점 멀어지는 순서로 인접 정점들을 탐색하는 방법 → 주변 정점 중에서 가장 오래된 것부터 우선으로 방문하는 방법
    - 큐를 통해 구현
    - 인접 리스트 O(|V|+|E|), 인접 행렬 O(|V|2)
3. 그래프 순회의 응용
    ⦁ 위상 정렬
    - 무사이클 방향 그래프에서 모든 간선의 방향이 한 방향으로만 향하도록 정점을 한 줄로 나열하는 것
    - 깊이 우선 탐색 활용 → 탐색을 수행하다가 더 이상 주변 정점이 없어서 되돌아갈 때, 즉 스택에서 탑이 삭제될 때 그 제거한 정점을 역순으로 나열하면 됨
    ⦁ 연결 성분
    - 주어진 무방향 그래프에서 임의의 두 정점 간의 경로가 존재하는 최대 부분 그래프
    - 탐색을 수행하다가 큐/스택이 비게 되면 그때까지 탐색한 정점들을 하나의 연결 성분으로 구성하며, 이 과정을 탐색하지 않은 정점이 남아 있지 않을 때까지 반복
    ⦁ 강연결 성분
    - 주어진 방향 그래프에서 임의의 두 정점 사이에 양방향의 경로가 존재하는 최대 부분 그래프
    - 깊이 우선 탐색을 적용하여 정점의 방문 완료 순서(방문 순서의 역순)를 구하고, G=(V, E)에 대해 ER={< v,u >|<u,v>∈E}를 사용한 GR=(V, ER)을 구하고, GR에 대해서 방문 완료 번호가 큰 것부터 DFS를 수행하여 갈 수 있는 정점들의 각 리스트가 강연결 성분이 됨