그래프와 BFS, DFS

• 그래프를 직접 그려볼 수 있는 사이트

Graph Traversal (Depth/Breadth First Search) - VisuAlgo

DFS🏃‍♀️

• source에서 가장 가까운 곳부터 방문 ⇒ 점점 멀리 이동

  • 자식을 확인하고, 없다면 더 먼 곳 방문

• 타겟이 존재하는지 확인합니다.

• 깊은 곳까지 빠르게 이동 합니다.

  • 그래프가 깊어질수록 느려짐

• ex) 미로 풀이 (가장 짧은 길을 알 수 없음)

BFS🏃‍♂️

• source에서 가장 가까운 곳을 방문하고 다시 돌아옴

  • parent node와 children node를 트랙킹

• 가장 가까운 길을 확인합니다.

• 최단 거리를 구합니다.

  • recommendation engines, peer to peer networks

• ex) 구글 맵, 페이스북 친구 추천

---

NextPage