BFS 나름 이론정리

개념

• 너비우선으로 탐색하는 알고리즘

• 위와 같이 그래프가 주어진다면
  1 -> 2 -> 7 -> 8 -> 3 -> 6 -> 9 -> 12 -> 4 -> 5 -> 10 -> 11
  순서로 탐색한다.

활용자료구조

• 큐자료구조

코드구현방법

1. 그래프 초기 배열 생성
2. 방문 배열 생성
3. 방문할 큐 배열 생성
4. 큐에 노드를 넣고 방문처리를 한다.
5. 큐에서 노드를 꺼내어 그래프의 해당 노드를 돌며 방문하지 않았으면 큐에 노드를 넣고 방문처리를 한다.
6. 큐에 요소가 없을때까지 5번을 반복한다.

코드

let graph = [[], [2,7,8],[1,3,6],[2,4,5],[3],[3],[2],[1],[1,9,12],[8,10,11],[9],[9],[8]];
//순서를 맞춰주기 위해 index 0 은 빈배열을 넣어준다.
let visited = new Array(graph.length+1).fill(false);

bfs(graph, 1, visited);

function bfs(graph, start, visited){
	let queue = [start];
    visited[start] = true;
    while(queue.length){
    	v = queue.shift();
        for(let i=0; i<graph[v].length; i++){
        	if(visited[i] == false){
            	queue.push(graph[v][i]);
                visited[i] = true;
            }
        }
    }

활용문제

• 최단경로찾기