목록큐 (1)

책 읽다가 코딩하다 죽을래

[알고리즘] BFS(Breadth-First Search)

📚 BFS (Breadth-First Search) 란? 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서 넓이 우선 검색을 적용한다. DFS는 인접한 한 노드를 끝까지 탐색했다면 BFS는 인접한 모든 정점을 방문합니다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모드 노드들을 저장하고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 됩니다. 처음에 넣은 노드이므로 큐를 이용해서 BFS를 구현할 수 있다. 📋 BFS 전체 과정 BFS의 알고리즘 방식을 설명하면 다음과 같다. 1. 루트 노드를 큐에 넣는다 2. 현재 큐의 노드를 빼서 visited에 추가한다. 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않..
이론/알고리즘 2021. 9. 17. 05:43
이전 Prev 1 Next 다음