#그래프 탐색
- 그래프 탐색이란?
▪ 그래프 탐색은 자료의 하나의 정점에서 시작해서 이어진 모든 정점들을 한 번식 방문하는 것이 목적이다.
▪ 그래프의 데이터가 배열과 같이 일정한 열과 행을 가지며 정렬되어 있지 않기 때문에 찾고자 하는 자료를 찾을 때까지 모든 지점을 방문하여야 한다.
▪ 그래프 탐색의 대표적인 방법에는 DFS, BFS가 있다
- BFS(Breadth-First Search)
▪ 너비 우선 탐색(BFS)는 가까운 정점부터 탐색한다.
▪ 더 탐색할 정점이 없는 경우 그 다음 떨어져 있는 정점을 순서대로 탐색한다.
▪ 주로 두 정점 사이 최단 경로를 찾을 때 사용한다.

▪ 위와 같은 그래프에서 BFS의 탐색 순서는 다음과 같다.
- Start지점에서 가장 가까운 노드인 A~F를 탐색한다.
- 탐색 후 그 다음 가까운 노드인 G와 같은 레벨의 노드들을 탐색한다. (S - A - G / S - B - H / S - C - I / S - D -T)
- 탐색 중 Target 노드를 발견하고 탐색을 종료한다.
- DFS(Depth-First Search)
▪ 깊이 우선 탐색(DFS)는 하나의 경로를 끝까지 탐색하여, 목적에 맞는 자료가 찾으면 종료된다.
▪ 목적에 맞는 정점에 도달하지 못하면 다음 경로를 탐색한다.
▪ 너비 우선 탐색(BFS)보다 탐색 시간이 더 소요될 수 있으나, 모든 노드를 완전히 탐색할 수 있다.

▪ 위와 같은 그래프에서 BFS의 탐색 순서는 다음과 같다.
- Start지점에서 A 노드와 이하의 노드들을 끝까지 탐색한다. (S - A - G - K - G - M)
- 탐색 후 그 다음 가까운 노드인 B, C의 노드를 A와 같은 방법으로 탐색한다. (B - H - N / C - I - T)
- 탐색 중 Target 노드를 발견하고 탐색을 종료한다.
- BFS와 DFS의 비교.
▪ 인접 행렬과 인접 리스트 (컴퓨터에서 그래프를 구현하는 방법)
- 인접 행렬
두 정점을 바로 이어주는 간선의 표시가 2차원 배열로 만들어짐
인접 행렬에서 행과 열은 정점을 의미하며, 각 원소는 정점간의 간선을 나타냄 - 인접 리스트
각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 만듬
각 정점마다 하나의 리스트를 가지고 리스트에 인접한 다른 정점을 포함시킨다.
그래프 탐색 | DFS | BFS |
구현 방법 | 재귀 함수 / 스택 | 큐 |
수행 시간 | 느림 | 빠름 |
시간복잡도 | 인접 리스트: O(N + E) 인접 행렬: O(N^2) |
인접 리스트: O(N + E) 인접 행렬: O(N^2) |
▪ 동일한 시간복잡도를 가졌으나 실제 수행 시간의 차이는 구현 방법의 차이 때문이다.
▪ 일반적으로 재귀함수로 구현하는 DFS보다 큐로 구현하는 BFS가 조금 더 빠르게 동작한다.
▪ 그래프의 크기가 크다면 DFS를 사용, 크키가 작고 검색 대상과의 거리가 가깝다면 BFS를 사용하는 것이 유리.
▪ 경로의 특징을 고려해야한다면 DFS를 사용
▪ 최단 거리를 찾는 문제는 BFS를 사용
'개발지 > Today I learn' 카테고리의 다른 글
[1128] 자바 - Tree traversal(트리 순회) (1) | 2023.11.28 |
---|---|
[1128] 자바 - Graph (그래프) (2) | 2023.11.28 |
[1122] 자바 - 자료구조 (Tree) (1) | 2023.11.23 |
[1122] 자바 - 자료구조 (Queue) (0) | 2023.11.22 |
[1026] 자바 - 자료구조 (Stack) (1) | 2023.10.26 |