[자료구조] 그래프 탐색 : DFS / BFS

📌 그래프 탐색

- 하나의 정점으로부터 시작, 차례대로 모든 정점을 방문하는 것.

- 방문한 노드와, 방문할 노드를 저장해두어야 무한루프를 방지할 수 있다.

- 대표적으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.

 

💡 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

1. 너비우선 탐색(BFS)

• A → B → C → H → D → I → J → M → E → G → K → F → L
• 한 단계씩 나아가며 현재 노드와 같은 레벨에 있는 노드(형제 노드)들을 순회하는 방식.
• 큐(Queue) 를 사용해 선입선출(FIFO) 원칙으로 탐색.

 

2. 깊이 우선 탐색(DFS)

• A → B → C → D → E → F → G → H → I → J → K → L → M
• 노드 하나의 자식을 타고 끝까지 순회한 다음, 시작 노드의 형제 노드를 타고 내려가며 순회하는 방식.