BFS

BFS ( Breadth First Search )

이전 시간에 DFS를 알아보았는데 이번 시간에는 BFS에 대해 알아보자.
BFS(넓이 우선 탐색)은 정점으로 부터 탐색 할 수 있는 거리가 같은 곳은 모두 탐색한 후 다음 거리에 있는 것들을 탐색하는 기법이다.
거리가 모두 1씩 떨어져 있다고 가정하고 거리가 1인 노드들을 다 탐색한 후 거리가 2인 곳을 탐색을 한다.
그래서 그림으로 알아보면, 이전에 DFS에서 사용했던 그래프를 보면,

시작점을 0번이라고 하자.
0번은 거리가 1인 1번과 3번 노드를 탐색 예약을 할 것이다.
그래서 1번 노드를 먼저 탐색하고 그 자식 노드들을 또 예약할 것이다.

이 구조를 자세히 보면 선입선출 구조라는 것을 볼 수 있는데
큐(Queue)로 관리하면 편하다.

그래서, 위의 그래프는 0 - 1 - 3 - 2 - 4 - 5 순으로 예약 시스템에 들어가서 탐색을 할 것이다.

int[,] adj = new int[6, 6]
{
    { 0, 1, 0, 1, 0, 0 },
    { 1, 0, 1, 1, 0, 0 },
    { 0, 1, 0, 0, 0, 0 },
    { 1, 1, 0, 0, 1, 0 },
    { 0, 0, 0, 1, 0, 1 },
    { 0, 0, 0, 0, 1, 0 },
};
public void BFS(int start)
{
	bool[] found = new bool[6];
    int[] parent = new int[6];
    int[] distance = new int[6];
    
	Queue<int> q = new Queue<int>();
    q.Enqueue(start);
    found[start] = true;
    parent[start] = start;
    distance[start] = 0;
    while(q.Count>0)
    {
    	int now = q.Dequeue();
        Console.WriteLine(now); // 탐색중인 노드 출력
        
        for(int next = 0; next < 6; next++)
        {
        	if(adj[now,next] == 0)
            	continue;
            if(found[next])
            	continue;
            q.Enqueue(next);
            found[next] = true;
            parent[next] = now;
            distance[start] = distance[now] + 1;
            
        }
    }
}

parent 와 distance 배열로 부모 노드와 거리까지 정보를 모두 알 수 있다.