반응형
10.3 인접 행렬을 이용한 깊이 우선 탐색
깊이 우선 탐색(Depth First Search)은 그래프의 한 정점에서 다른 정점으로 갈 수 있는 경로를 찾는 방법 중에 하나입니다. 하나의 정점에서 갈 수 있는 이웃 정점을 방문하고 다시 방문한 정점에서 이웃 정점을 방문하면서 원하는 목적 지점까지 방문하는 방법이예요. 이 때 방문했었던 정점을 다시 방문하지 말아야 합니다.
깊이 우선 탐색처럼 그래프에서 어떠한 문제를 해결하기 위해서는 그래프를 먼저 표현할 수 있어야 합니다. 정점의 개수가 비교적 적을 때는 인접행렬로 표현할 수 있습니다. 만약 정점의 개수가 많다면 인접 행렬은 이웃하지 않는 간선을 위한 영역도 포함하여 메모리 및 성능이 나빠집니다. 이럴 때는 정점과 간선의 집합으로 그래프를 표현하여 문제를 해결할 수 있습니다.
여기에서는 인접 행렬을 이용하여 그래프를 표현하는 것을 먼저 구현한 후에 정점과 간선의 집합으로 그래프를 표현하는 방법을 살펴보기로 할게요.
다음은 방향성 없는 그래프를 표현한 하나의 예입니다.
그리고 이를 인접행렬로 표현한 예입니다.
반응형
'언어 자료구조 알고리즘 > [C++]디딤돌 자료구조와 알고리즘' 카테고리의 다른 글
| 11. 너비 우선 탐색(Breath First Search) 알고리즘 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.12 |
|---|---|
| 10.4 깊이 우선 탐색(정점과 간선 그래프) (0) | 2016.04.11 |
| 10.3.3 깊이 우선 탐색(인접 행렬) 코드 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.11 |
| 10.3.2 깊이 우선 탐색(인접 행렬) 구현 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.11 |
| 10.3.1 그래프 구현 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.11 |
| 10.2.2 순열 문제 소스 코드 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.11 |
| 10.2.1 순열 문제 구현 (0) | 2016.04.11 |
| 10. 2 순열 문제 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.11 |
| 10.1 피보나치 수열 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.11 |
| 10. 동적 프로그래밍(DYNAMIC PROGRAMMING) [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.11 |