너비 우선 탐색
그래프 탐색 알고리즘
정점들과 같은 레벨에 있는 형제 노드들을 먼저 탐색 하는 방식
한 단계 씩 내려가면서 현재 노드와 같은 레벨에 있는 형제 노드들을 먼저 순회함.
출처 : https://www.fun-coding.org/
파이썬 식 그래프 표현법
BFS 알고리즘
큐를 활용 하기 !
크게 두개 활용
1) 방문해야 할 노드 저장 하는 큐
2) 방문 한 노드 저장하는 큐
코드로 설명 ~!
먼저, 그래프 생성 후
visited , need_visit 두개의 리스트 생성
첫 번째 노드를 need_visit에 append 시켜준다 -> 첫번째 방문 노드임
그리고 need_visit 안에 있는 노드들이 다 없어질 때 까지 while문 반복
need_visit에 첫번째 원소를 방문처리 하기 위해 pop(0) 활용
- pop(0) 시, 해당 리스트의 첫번째 원소가 빠져 나오고 그 뒤의 원소들이 앞으로 땅겨짐
그리고 need_visit 리스트의 pop으로 빠진 노드가 방문 처리가 안된 노드라면 visited 에 추가
동시에 해당 노드의 형제노드들을 방문 되어져야 할 need_visit 리스트에 추가!
그리고 마지막으로 방문된 node들만 존재하는 visited 리스트 반환
정리하자면,
need_visit 에 첫번째 노드를 심어주고 첫 번째 노드의 형제 노드들을 need_visit에 심어준다 그리고 pop을 당할 때 visited 에 없으면 넣어주고 넣어줬다면 해당 노드의 또다른 형제 노드들을 심어주고 visited에 들어간다 ! 역으로 그렇지 않으면( 이미 방문처리가 된 노드라면 ) 넣어주지 않는다.
시간복잡도
O(간선의 수 + 노드의 수)
WILL is ALL