너비탐색 썸네일형 리스트형 [javascript] BFS 📶 그래프 탐색 어떤것들이 연속해서 이어질 때, 모두 확인하는 방법 이다. Graph : Vertex (정점) + Edge (이어지는 것) - 시작점에 연결된 Vertex 찾기 - 찾은 Vertex 를 Queue 에 저장 - Queue 의 가장 먼저 것 뽑아서 반복 ⏱️ 시간복잡도 알고리즘이 얼마나 오래 걸리는지 / 문제를 해결하는데 걸리는 시간과 입력의 함수 관계 나타낸다. BFS : O(V+E) BFS 의 기본원리 - 방문여부 확인 (재방문 금지) - Queue: BFS 실행 최단거리는 BFS(너비우선탐색) 로 푸는게 좋다. 탐색 스택, 방문 배열 생성 탐색을 시작하는 정점을 탐색스택에 쌓는다 탐색스택이 없어질때까지 아래 반복 - 스택 최상단에 있는 것을 없애고, 이를 탐색 - 탐색 시에 방문했는지 .. 더보기 이전 1 다음