[자구] 그래프(2)

이번 장에서는 그래프를 이용한 알고리즘에 대해 배워보도록 하겠다.

1. 그래프 순회 알고리즘- 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)
2. 최단 경로 알고리즘 - 다익스트라 알고리즘

 

 

---

그래프 순회 알고리즘

앞서 트리에서는 모든 노드를 한 번씩 방문하는 순회에 대해 정리했었다. ( 전위, 중위, 후위)

이번에는 그래프의 모든 정점을 순회하는 탐색 방법에 대해 알아볼 것이다. 그래프 순회 방법에는 길이 우선 탐색과 너비 우선 탐색이 있다.

 

 

 

1️⃣ 깊이 우선 탐색 (DFS)

더 이상 방문 가능한 정점이 없을때까지 최대한 깊이 탐색하는 방법

a→b→e→c→f→d

• 루트부터 시작
• 배열, 스택 사용
  • 배열: 방문 여부 확인 (미방문 정점 파악)
  • 스택: 방문 중 뒤로가기가 필요할때 사용

1. 배열에 a추가, 스택에 a 추가 
a.           |. a. |

2. 정점 b 방문
           |. b. |
a, b       |. a. |

3. 정점 e 방문 
           |. b. |
           |. a. |
a, b, e.   |. e. |

4. 정점 e에서 b로 돌아감 ( 현재: 방문 a,b,e|    위치: 전으로 돌아가기 때문에 e pop)
              |. b. |
a, b, e       |. a. |

-> 미방문 정점이 없을때까지 반복 

 

2️⃣ 너비 우선 탐색

깊이 우선 탐색은 최대한 깊이 탐색하기 위해 반복하는 방법이라면

너비 우선 탐색은 최대한 넓게 탐색하기 위해 반복하는 방법이다.

너비 우선 탐색(BFS)는 인접한 모든 정점들을 방문하고 방문한 정점들과 연결된 모든 정점들을 반복하는 방법이다.

a→b→c→d→e→f

• 루트부터 시작
• 배열과 큐를 사용
  • 배열: 방문 여부 확인 (미방문 정점 파악)
  • 큐: 연결된 정점 저장

1. 정점 a 방문
a

2. a 방문시 인접한 노드 b,c,d
a                b,c,d

3. 정점 b 방문 (b를 접근했을때 e 인큐)
a,b              c,d,e 

4. 정점 c 방문 (c를 접근했을때 f 인큐)
a,b,c            d,e,f

4. 정점 d 방문 (d를 접근했을때 없음)
a,b,c,d          e,f

4. 정점 e 방문 (e를 접근했을때 없음)
a,b,c,d,e        e,f

4. 정점 f 방문 (f를 접근했을때 없음)
a,b,c,d,e,f          

 

---

최단 경로 알고리즘

최단 경로 알고리즘은 한 정점에서 목적지 정점까지 이르는 가중치의 합이 최소가 되는 경로를 결정하는 알고르짐이다.

최단 경로 알고리즘의 종류는 다양하지만 그 중 대표적인 알고리즘은 다익스트라 알고리즘이다.

 

1️⃣ 다익스트라 알고리즘

특정 정점에서 다른 모든 정점까지의 최단 거리를 구해주는 알고리즘

• 간선의 가중치가 음이 아니어야 사용 가능

 

1. 시작 정점은 0, 나머지 정점들은 충분히 큰 수로 초기화

정점1 0

정점2	∞
정점3	∞
정점4	∞
정점5	∞
정점6	∞

1. 시작 정점 방문 → 인접한 정점들 탐색 (2 탐색)

• 2에 이르는 가중치 합 = 2

정점1 0

정점2	2
정점3	∞
정점4	∞
정점5	∞
정점6	∞

1. 2에 인접한 정점 방문 ( 3,4,5)

• 정점 3에 이르는 가중치 합: 정점2 + 10 = 12
• 정점 4에 이르는 가중치 합: 정점2+ 2 = 4
• 정점 5에 이르는 가중치 합: 정점2+ 5 = 7

정점1 0

정점2	2
정점3	12
정점4	4
정점5	7
정점6	∞

1. 2에 인접한 4에 방문 → 4에 인접한 5에 방문

• 정점 5에 이르는 가중치 합: 정점4+1 = 5
• 정점 5에 적혀있는 수: 7, 지금 구한 값: 5
• 제일 작은 값으로 변경

정점1 0

정점2	2
정점3	12
정점4	4
정점5	5
정점6	∞

1. 반복

이처럼 다익스트라 알고리즘은 한 정점에서 나머지 정점까지의 최단 거리를 구할 수 있는 그래프 기반 알고리즘이다.