깊이 우선 탐색 DFS & 너비 우선 탐색 BFS

 

DFS (Depth First Search) : 깊이 우선 탐색

• 그래프 탐색의 종류
• 루트 노드 또는 임의의 노드에서 시작해서 최대 깊이까지 탐색 후 돌아와서 다른 노드 탐색
• Stack 사용 
• 현재 경로에 있는 노드만 기억하면 된다
• 목표 노드가 깊은 단계에 있으면 해를 빨리 구할 수 있다
• 해가 없는 경로가 깊을 경우 탐색 시간이 오래 걸림
• 얻어진 해가 최단 경로라는 보장이 없음 

구현 방법

1. 인접 행렬 (Adjacency Matrix) : 행렬로 정점 사이의 관계 표현 
2. 인접 리스트 : 리스트 방식으로 정점이 연결된 노드의 정보 저장

 

BFS (Breadth First Search) : 너비 우선 탐색

• 그래프 탐색의 종류
• 루트 노드 또는 임의의 노드에서 시작해서 인접한 노드 먼저 모두 확인 후 다른 노드 탐색
• Queue 사용 
• 거리가 가까운 순서로 탐색
• 재귀 동작 X
• FIFO (First In, First Out : 선입선출)

구현 방법

1. 인접 행렬 (Adjacency Matrix) : 행렬로 정점 사이의 관계 표현 
2. 인접 리스트 : 리스트 방식으로 정점이 연결된 노드의 정보 저장

 

 

출처

 

https://www.youtube.com/watch?v=waPwUJu0-lo