bfs js

[그래프탐색] BFS - JS, Python

너비 우선 탐색 - Breath Frist Search 가까운 노드부터 탐색하는 알고리즘 DFS는 최대한 멀리있는 노드를 우선으로 탐색하는 방식으로 동작한다했는데, BFS는 가까이 있는 노드부터 우선탐색 큐를 이용한 선입선출방식 가중치 없는 그래프에서 최단 경로 문제에서 많이 쓰인다 ex) 서울에서 부산으로 가는데 거쳐야하는 최소 정거장의 수 ex) 임의의 4자리 숫자 x에서 한자리(0~9)로 변경하면 다른 숫자 y를 만들 수 있음 이떄 x에서 z를 만들기 위한 최소 변경횟수 ex) 친구관계에서의 단계 1. 탐색 시작 노드를 큐에 삽입하고 방문처리 2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 3. 2번 과정을 더이상 수행할 수 없을 때까지 반복 ..