시간복잡도

N은 노드, E는 간선일 때
▶ 인접 리스트 : O(N+E)
▶ 인접 행렬 : O(N²)

그래프 : 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종

깊이 우선 탐색 (Depth-First Search)

탐색을 함에 있어서 깊이를 우선으로 하여 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆의 노드로 이동

▶ Stack 또는 재귀함수를 사용

▶ 알고리즘

1. 스택의 최상단 노드를 확인
2. if 최상단 노드에게 방문하지 않은 인접 노드가 있다 :
   그 노드를 스택에 넣고 방문처리
   else :
   스택에서 최상단 노드를 뺌
   

▶ 사용 목적

• 맹목적인, 모든 정점을 방문할 때 사용
• 경로의 특징을 저장해둬야 할 때 (bfs는 경로의 특징을 가지지 못함)
• 검색 대상 그래프가 크다면 DFS 고려

너비 우선 탐색 (Breadth-First Search)

탐색을 함에 있어서 너비를 우선으로 하여 최대한 넓게 이동한 뒤, 더이상 갈 곳이 없을 경우 아래의 노드로 이동

▶ Queue 사용

▶ 알고리즘

1. 큐에서 하나의 노드를 꺼냄
2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문한 후 , 차례대로 큐에 삽입

▶ 사용 목적

• 맹목적인, 모든 정점을 방문할 때 사용
• 최단경로를 찾아준다는 점에서 최단 길이를 보장해야할 때 사용하는 탐색 기법
• 검색 대상 규모가 크지 X, 검색 시작 지점부터 원하는 대상이 멀지 않다면 BFS

예제

[코테연습/python] BFS,DFS 예시 문제들