그래프 탐색2 그래프 탐색 - 너비 우선 탐색 BFS 이번에는 그래프 탐색의 다른 방식인 BFS에 대해서 소개해드리겠습니다. 1. 너비 우선 탐색 Breadth First Search, BFS 지난번에 본 깊이 우선 탐색(DFS)는 한 정점에서 시작해서 갈 수 있는 정점까지 방문한 후에 방문하지 않은 인접 정점이 있는 정점으로 돌아와서 진행하는 방식이었습니다. 이번에 배울 너비 우선 탐색은 정점에 인접한 정점들을 모두 한 번씩 방문하고 나서 방문했던 정점들의 인접한 정점들을 다시 한 번씩 방문하는 방식입니다. 또한 정점들마다 너비 우선 탐색을 수행하기 위해서 큐를 이용합니다. 이점도 DFS와 차이점을 보이고있습니다. DFS와 마찬가지로 배열과 큐를 이용하는데 배열에는 방문 정보를 담고 큐에는 방문 기록을 남기기 위해 사용합니다. A에서 시작하도록 하겠습니다.. 2021. 10. 9. 그래프 탐색 - 깊이 우선 탐색 DFS 그래프의 탐색 혹은 그래프의 순회라고 불리우는 개념은 그래프의 모든 정점을 반드시 한 번은 방문하는 것을 말합니다. 그래프의 탐색 방법에는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 두 종류가 있는 그중에서 깊이 우선 탐색 부터 알아보겠습니다. 1. 깊이 우선 탐색 Depth First Search, DFS 깊이 우선 탐색은 한 정점에서 시작하여 한 방향으로 진행해 갈 수 있는 정점까지 최대한으로 탐색합니다. 그러다가 더이상 진행할 수 없다면 가장 최근에 만난 갈림길이 있는 정점으로 돌아가서 다른 방향의 간선으로 진행할 수 있는지 탐색하는 방식입니다. 깊이 우선 탐색에서는 탐색한 경로의 정보를 담기 위해서 스택을 이용하고, 정점에 대해 방문한 정보를 기록하기 위해서배열을 이용합니다. 말로했을 때.. 2021. 10. 8. 이전 1 다음 300x250
