[javascript] BFS

📶 그래프 탐색

어떤것들이 연속해서 이어질 때, 모두 확인하는 방법 이다.

---

Graph : Vertex (정점) + Edge (이어지는 것)

 

 

- 시작점에 연결된 Vertex 찾기

- 찾은 Vertex 를 Queue 에 저장

- Queue 의 가장 먼저 것 뽑아서 반복

---

 

⏱️ 시간복잡도

알고리즘이 얼마나 오래 걸리는지 / 문제를 해결하는데 걸리는 시간과 입력의 함수 관계 나타낸다.

 

BFS :    O(V+E)

 

 

 

 

---

 BFS 의 기본원리

- 방문여부 확인 (재방문 금지)

- Queue: BFS 실행

 

최단거리는 BFS(너비우선탐색) 로 푸는게 좋다. 

 

탐색 스택, 방문 배열 생성

탐색을 시작하는 정점을 탐색스택에 쌓는다

탐색스택이 없어질때까지 아래 반복

- 스택 최상단에 있는 것을 없애고, 이를 탐색

- 탐색 시에 방문했는지 체크, 했다면 패스

- 방문 안했다면 이를 방문 배열에 넣고 . 그정점과 이어진 정점들을 배열에 다시 쌓는다

 

//graph 자료구조와 startNode 를 입력
const BFS = (graph, startNode) => {
	let visited = []; //탐색을 마친 노드들
    let needVisit = []; //탐색해야할 노드들
    
    needVisit.push(startNode); // 노드 탐색 시작! 
    
    while(needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면,
    	const node = needVisit.shift(); // 가장 오래 남아있던 정점을 뽑아냄.
        if(!visited.includes(node)) { // 해당 노드 방문이 처음이라면,
        	visited.push(node);
        	needVisit = [...needVisit, ...graph[node]];
        }
    }
    return visited;
}