대표적 그래프 탐색 알고리즘
- 그래프
정점과 그 정점을 연결하는 간선으로 이루어진 자료구조의 일종
그래프를 탐색하는 것은 하나의 정점으로부터 시작해 차례대로 모든 정점을 한번씩 방문하는 것
DFS
깊이 우선 탐색
최대한 깊이 이동
정점의 자식을 먼저 탐색하는 방식
루트 노드에서 시작해 다음 분기로 넘어가기 전에 다음 분기를 완벽하게 탐색하는 방식
특징
- 모든 노드를 방문하고자 할 경우 선택
- 깊을수록 빠르고, 메모리 소모가 적다.
- 깊이의 끝이 없거나 너무 깊으면 사용을 지양해야 한다.
- 스택이나 재귀함수로 구현
- 노드 방문 여부를 반드시 검사해야함
- 깊이 제한을 사용
- 목표가 발견되지 않으면 부모노드로 돌아오기 (백트래킹)
- BFS와 차이
- 좀 더 간단함
- 느림
장점
- 현 경로 상 노드만 기억하면 되므로 메모리 낭비가 적다
- 목표 노드가 깊은 단계에 있다면 해를 빠르게 구할 수 있다.
단점
- 얻은 해가 최단 경로가 된다는 보장이 없다.
- 해가 없는 경로에 빠질 수 있다.
구현
- 재귀
def dfs_recursive(v,discovered=[]):
discovered.append(v)
for w in graph[v]:
if w not in discovered:
discovered=dfs(w,discovered)
return discovered- 스택
def dfs_iterative(start_v):
discovered=[]
stack=[start_v]
while stack:
v=stack.pop()
if v not in discovered:
discovered.append(v)
for w in graph[v]:
stack.append(w)
return discoveredBFS
너비 우선 탐색
최대한 넓게 이동
정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식, 인접한 노드 먼저 탐색
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
특징
- 두 노드 사이의 최단 경로를 찾고 싶을 때 사용
- 큐로 구현
- 방문했는지 여부를 반드시 검사해야 함
장점
- 최단 경로를 보장함
단점
- 경로가 길 경우 메모리 낭비가 있음
- 해가 존재하지 않는 유한 그래프 경우, 탐색 후 실패로 끝난다.
- 무한 그래프의 경우 해를 찾지도 못하고 끝내지도 못한다.
구현
def bfs(start_v):
discovered=[start_v]
queue=[start_v]
while queue:
v=queue.pop(0)
for w in graph[v]:
if w not in discovered:
discovered.append(w)
queue.append(w)
return discoveredDFS & BFS 시간 복잡도
모든 노드를 검색한다는 점에서 시간 복잡도는 동일
O(노드 개수 + 간선 개수)임
-> 인접 리스트로 구현하는 게 시간 복잡도가 작음
문제 유형
- 모든 정점을 방문하는 것이 주요 문제 ➡️ dfs,bfs
- 경로의 특징을 저장할 필요가 있는 문제 ➡️ dfs
bfs는 경로의 특징을 갖지 못한다. - 최단 거리 구하기 ➡️ bfs 유리
dfs는 처음 발견하는 해답이 최단 거리가 아닐 수 있음
bfs는 현재 노드에서 가장 가까운 곳부터 찾기에 먼저 나오는 것이 곧 최단 거ㄹ - 검색 대상 그래프가 크다면 ➡️ dfs
- 규모가 크지 않고 원하는 대상이 멀지 않다면 ➡️ bfs
[참고]
터벅터벅 개발(은좋은)자 로그