[알고리즘] 너비 우선 탐색(BFS) 이해 및 구현 ( C++, Java, Python )

너비 우선 탐색(BFS, Breadth-First Search) 에 대해서 알아보겠습니다.

 

목차

1. 너비 우선 탐색( BFS, Breadth-First Search) 의 개념

2. 너비 우선 탐색( BFS, Breadth-First Search) 의 과정

3. 너비 우선 탐색( BFS, Breadth-First Search) 의 구현

 

1. 너비 우선 탐색( BFS, Breadth-First Search ) 의 개념

---

너비 우선 탐색은 Breadth First Search 로, 흔히 BFS 로 줄여서 사용합니다. 

시작점의 인접한 정점들을 차례로 모두 방문하고, 방문했던 정점을 시작점으로해서 다시 인접한 정점들을 차례로 모두 방문 하는 방식입니다.  즉, 넓게 탐색 하는 것입니다. 

 

너비 우선 탐색(BFS) 는 두 노드 사이의 최단 경로 를 찾을 때 주로 사용합니다. 왜냐하면 전체 노드를 탐색하는 것과 달리 시작과 끝 지점에 대해 하나씩 파악해 나가기 때문에 끝 지점을 비교적 빠르게 찾을 수 있습니다. 

 

이러한 방식을 구현 하기 위해서는 선입선출(FIFO) 자료구조인 Queue 를 이용하여 구현하게 됩니다. 

 

2. 너비 우선 탐색( BFS, Breadth-First Search ) 의 과정

---

너비 우선 탐색(BFS)

 

1. 루트에서 시작한다.

2. 자식 노드들을 Queue 에 저장한다.

3. Queue 에 저장된 노드들을 차례로 방문하고, 또한 각각의 자식들을 Queue 에 저장한다.

4. 위 과정을 반복한다.

5. 모든 노드를 방문하면 탐색을 마친다. 

 

3. 너비 우선 탐색( BFS, Breadth-First Search ) 의 구현

---

자료구조 Queue 를 사용하는 경우가 일반적입니다. 그래서 Queue 를 사용하여 어떻게 구현하는지 알아보도록 하겠습니다. 

 

1 ) C++

const int MAX = 100;

deque<int> q;
bool visited[MAX]; // 방문 배열. visited[node] = true이면 node는 방문이 끝난 상태이다.

// graph는 인접 리스트, source는 시작 노드
void bfs(const vector<int> graph[], int source) 
{ 
    // 시작 노드 방문
    q.push(source);
    visited[source] = true;

    while(!q.empty()) 
    {
        // 큐에서 방문할 노드를 꺼냅니다. 
        int current = q.front(); q.pop();

 		// current의 인접 노드들을 방문합니다.
        for(int next: graph[current]) 
        {
        	// 방문 한적이 없다면 visited[next] 를 true 로 변경하고 queue 에 노드를 넣습니다.
            if(!visited[next]) 
            { 
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

2) Java

void BFS(LinkedList<Integer> adj[], int source ) 
{
	// 각 노드의 방문 여부를 저장하기 위해
	boolean visited[] = new boolean[adj.length]; 
	LinkedList<Integer> queue = new LinkedList<Integer>();
		
	visited[source] = true;
	queue.add(source);
		
	while (queue.size() != 0) {
		source = queue.poll();

		Iterator<Integer> i = adj[source].listIterator();
		while (i.hasNext()) {
			int next = i.next();
			if (!visited[next]) {
				visited[next] = true;
				queue.add(next);
			}
		}
	}
}

3) Python 

def BFS(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited
  
print(BFS(graph_list, root_node))