BFS
Breadth First Search. 흔히 줄여서 BFS로 씁니다.
너비 우선 탐색으로 그래프 탐색의 두 종류 중 하나 입니다. (BFS,DFS)
너비 우선 탐색의 탐색 방법은 아래와 같습니다.
1.
루트에서 시작한다.
2.
자식 노드들을 [1]에 저장한다.
3.
[1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
4.
[2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
5.
위의 과정을 반복한다.
6.
모든 노드를 방문하면 탐색을 마친다.
좀 더 상세하게 설명해보겠습니다.
위 그림은 BFS를 찾는 순서를 나타낸 그림입니다.
BFS는 Queue와 밀접한 관련이 있습니다. 이 탐색 순서를 Queue를 이용하여 풀어보겠습니다.
가장 먼저, 시작이 되는 1번의 자식 노드를 찾습니다.
시작 탐색 현재 Queue
(1)
탐색한 1번은 Queue에서 제외하며 1번과 관련되어있는 모든 자식 노드들을 Queue에 담습니다.
그럼 2,3,4번의 노드들이 담기게 됩니다.
첫 번째 탐색
(2) (3) (4)
다음 탐색으로 2번의 노드의 자식 노드들을 탐색합니다.
Queue에 담긴 2번 노드는 제외되며, 5,6번이 다음으로 담기게 됩니다.
두 번째 탐색
(3) (4) (5) (6)
이런 식으로 계속해서 Queue의 규칙에 따라 탐색하면, 자연스럽게 너비 즉, 트리의 레벨에 맞춰 탐색하게 됩니다.
아래 코드는 간단한 그래프를 BFS로 탐색한 방법입니다.
Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>()
{
{ 0, new List<int> { 1, 2 } },
{ 1, new List<int> { 2, 3 } },
{ 2, new List<int> { 0, 3 } },
{ 3, new List<int> { 1, 2 } }
};
int start = 0;
BFS(graph, start);
void BFS(Dictionary<int, List<int>> graph, int start)
{
Dictionary<int, bool> visited = new Dictionary<int, bool>();
foreach (var node in graph.Keys)
{
visited[node] = false;
}
Queue<int> queue = new Queue<int>();
visited[start] = true;
queue.Enqueue(start);
while (queue.Count != 0)
{
int current = queue.Dequeue();
foreach (var neighbor in graph[current])
{
if (!visited[neighbor])
{
visited[neighbor] = true;
queue.Enqueue(neighbor);
}
}
}
}
C#
복사
