너비우선탐색
-
너비 우선 탐색알고리즘공부 2018. 5. 28. 17:44
너비 우선 탐색 Breath-First Search두 항목 간의 최단 경로를 찾는다.너비 우선 탐색은 두 가지 질문에 대답할 수 있다. 질문 1. 정점 A에서 정점 B로 가는 경로가 존재하는가?질문 2. 정점 A에서 정점 B로 가는 최단 경로는 무엇인가? 망고 판매상 찾기 문제 (질문 1. 나의 네트워크에 망고 판매상이 있는가?)나는 망고 농장의 주인이다.망고를 팔기 위해 페이스북 친구 목록 중 망고 판매상을 찾으려고 한다.먼저, 페이스북 친구 목록을 살펴보았다. 그런데, 친구 중에 망고 판매상이 없다.이제 친구의 친구를 찾아볼 차례이다. 만약 앨리스가 망고 판매상이 아니면 앨리스의 친구를 목록에 올린다.앨리스의 친구, 앨리스의 친구의 친구, 이런식으로 망고 판매상을 찾을 때까지 전체 네트워크를 탐색하게..