알고리즘 - 18 그래프 알고리즘의 원리

일상 생활에서 사용하는 많은 부분을 그래프로 나타낼 수 있음

- 지하철에서 역과 역사이의 관계, 사람간의 관계, 네비게이션 길찾기, 한붓 그리기 등

-> 그래프, 그래프 표현방법

 

 

 

그래프

- 현상이나 사물을 정점 vertex와 간선 edge로 표현한 것

- Graph G = (V, E) - V : 정점 집합, E : 간선 집합

- 두 정점이 간선으로 연결되어 있으면 인접하다고 함

 -> 인접 = adjacent

 -> 간선은 두 정점의 관계를 나타냄

 

 

그래프 예시

- 사람들간 친분 관계를 나타낸 그래프

- 각 사람을 하나씩의 정점으로 표시

- 서로 친밀한 사람 간에는 간선을 연결함

- 다른 예시

 1. 두 도시를 연결하는 도로의 존재 여부

 2. 두 집안간의 혼인 여부

 

친분 관계 그래프

- 친밀도를 가중치로 나타냄

- 간선에 가중치를 주어 친밀감의 정도를 보여줌

 

방향을 고려한 친분관계 그래프

- 간선이 방향을 가짐

- 유향 그래프 : 그래프가 방향을 가진 그래프

 -> 기업들 간 제품 공급 관계

 -> 제품 생산 공정에서 선후 관계 등

- 무향 그래프 : 그래프가 방향이 없는 그래프

 

가중치를 가진 유향 그래프

- 누가 누구를 얼마만큼 좋아하는지를 나타냄

- 다른 예

 -> 서울과 LA간 비행기 노선 처럼 가는데 걸리는 시간과 오는데 걸리는 시간이 다른 경우

 

 

 

그래프 표현 방법

1. 그래프 표현방법 개요

2. 인접 행렬을 이용한 방법

3. 인접 리스트를 이용한 방법

4. 그래프 탐색

 

 

그래프 표현 방법

- 행렬을 이용하는 방법

- 리스트를 이용하는 방법

 

인접 행렬을 이용하여 그래프를 나타내는 표현

- 인접 행렬(Adjacency Matrix)를 사용

- n x n 행렬로 표현

 -> 원소 (i, j) = 1 : 정점 i와 정점 j사이에 간선이 있음

 -> 원소 (i, j) = 0 : 정점 i와 정점 j사이에 간선이 없음

- 유향 그래프의 경우

 -> 원소 (i, j)는 정점 i로부터 정점 j로 연결되는 간선이 있는지를 나타냄

- 가중치가 있는 그래프의 경우

 -> 원소 (i, j)는 1대신 가중치를 가짐

 

 

인접 행렬을 이용한 예

1. 무향 그래프를 인접 행렬로 표현

2. 가중치를 가진 무향 그래프를 인접 행렬로 표현

3. 유향 그래프를 인접 행렬로 표현

4. 가중치를 가진 유향 그래프를 인접 행렬로 표현

 

 

 

1. 무향 그래프와 인접 행렬 표현

2. 가중치를 가진 무향 그래프와 인접 행렬 표현

3. 유향 그래프와 인접 행렬 표현

4. 가중치를 가진 유향 그래프와 인접 행렬 표현

 

 

인접 행렬을 이용한 방법의 효율성 분석

1. 이해가 쉽고 간선의 존재 여부를 즉각 알수 있다는 장점을 가짐

 - 정점 I와 정점 j의 인접 여부는 행렬 (i, j) 원소나 (j, i) 원소의 값만 보면 알 수 있기 때문

2. n x n 행렬이 필요하므로 n^2에 비례하는 공간이 필요함

 - 행렬의 준비 과정에서 행렬의 모든 공간을 채우는 데만 n^2에 비례하는 시간이 소모됨

 - O(n^2) 미만의 시간이 소요되는 알고리즘이 필요한 경우에 행렬 표현법을 사용하면 행렬의 준비과정에만 Theta(n^2)의 시간이 소모되어 적합하지 않음

3. 간선의 밀도가 아주 높은 그래프에서는 인접 행렬의 표현이 적합함

 - 전체 (i, j) 쌍에서 둘 중 하나 꼴로 간선이 있는 경우 행렬을 사용하는 것이 효율 적임

 - 100만 개의 정점을 가진 그래프에서 간선이 200만개 밖에 없는 경우에 행렬 표현을 쓰면 시간과 공간이 많이 낭비됨

   -> 행렬의 총 원소 수는 1조개, 이 중 고작 200만(또는 400만) 개만 1로 채워지고 나머지는 0이 되기 때문

 

 

 

인접 리스트 Adjacency List

- n개의 연결 리스트로 표현

- i번째 리스트는 정점 i에 인접한 정점들을 리스트로 연결해 놓은 것 임

- 가중치 있는 그래프의 경우 -> 리스트는 가중치도 보관함

 

 

인접 리스트를 이용한 예

1. 무향 그래프와 인접리스트

2. 가중치를 가진 그래프의 인접 리스트

 

1. 무향 그래프와 인접 리스트₩

 

2. 가중치를 가진 그래프의 인접 리스트 표현

 

 

 

그래프 탐색

1. 너비 우선 탐색 BFS Breath-First Search

2. 깊이 우선 탐색 DFS Depth-First Search

 

 

너비 우선 탐색

- 깊이가 1인 모든 정점을 방분

 -> 깊이가 2인 모든 정점을 방문

 -> 깊이가 3인 모든 정점을 방문 ... (계속 방문)

- 더이상 방문 할 곳이 없으면 탐색을 마침

 

깊이 우선 탐색

- 깊이 들어가는 특징을 지니고 있음

- 나아갈 길이 존재하지 않으면 이전 위치로 돌아와 다른 길을 선택하여 움직임