[알고리즘] Graph/Tree - 너비 우선 탐색 BFS (Breadth First Search)

지난 포스팅에서 그래프 구조의 탐색 알고리즘 중 하나인 DFS에 대해 알아보았습니다.

이번 포스팅에서는 깊이가 아닌, 너비를 우선으로 탐색하는 BFS에 대해 알아보며, 두개의 탐색 알고리즘이 어떤 차이점을 가지고 있는지 알아보겠습니다.

※ 깊이 우선 탐색 (DFS)

 

너비 우선 탐색 (Breadth First Search)

BFS - https://www.wscubetech.com/resources/dsa/dfs-vs-bfs

• 시작 노드에서 가까운 노드 순서로 탐색하는 알고리즘
• 현재 깊이와  동일한 모든 이웃노드를 방문 후 다음 깊이(레벨)로 탐색하는 방식
• FIFO(선입선출)형태의 자료구조 큐를 사용하여 방문한 노드를 먼저 처리한다.
• 각 레벨을 차례대로 방문하기 때문에 시작 노드에서 다른 노드까지의 최단경로를 찾을 수 있다.
  • 간선(Edge)가 비가중치인 경우에 최단경로가 보장되며, 가중치가 있을 경우 다른 알고리즘을 사용한다.
• 큐에 모든 노드를 저장해야하므로 노드가 많을 경우 메모리 사용량이 증가한다.
• 시간복잡도 : O(V + E) 
  • V : Vertex
  • E : Edge

 

BFS 탐색 과정

• 선택 노드 0에서 시작 
  
  • 노드 0 큐에 삽입, Visited = true
• 0계층의 이웃 노드 방문 (1 ~ 3)
  
  • 현재 노드에 (0)에 대해 방문하지 않은 인접노드(1,2,3)들을 찾아 큐에 추가, Visited = true
  • 방문체크, 방문하지 않은 노드만 큐에 삽입
• 1계층의 모든 노드 방문 후 2계층 방문 (반복)
  
  • 방문체크 하지 않은(Visited == false)  노드 (4,5 / 6, 7) 큐에 삽입, Visited = true
• 반복
• Queue가 비어있는 경우 탐색 종료

 

BFS 구현 예시 코드

struct Vertex
{
	int data;

	Vertex() : data(0) {}
	Vertex(int data) : data(data) {}
};

vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> isVisited;

void CreateGraph()
{
	vertices.resize(8);
	adjacent.resize(8);

	adjacent[0].push_back(1);
	adjacent[0].push_back(2);
	adjacent[0].push_back(3);
	adjacent[1].push_back(4);
	adjacent[1].push_back(5);
	adjacent[2].push_back(6);
	adjacent[3].push_back(7);
	adjacent[3].push_back(0);
	adjacent[4].push_back(1);
	adjacent[5].push_back(1);
	adjacent[6].push_back(2);
	adjacent[7].push_back(3);

	for (int i = 0; i < vertices.size(); i++)
	{
		vertices[i].data = i;
	}
}

void BFS(int start)
{
	queue<int> q;
	isVisited.resize(vertices.size(), false);

	// 방문한 Vertex True 후 큐에 삽입
	isVisited[start] = true;
	q.push(start);

	cout << "Start BFS Node : " << start << endl;

	while (!q.empty())
	{
		// 삽입된 인접 노드 꺼내기
		int current = q.front();
		q.pop();

		cout << "Current VertexData : " << vertices[current].data << endl;

		for (int near : adjacent[current])
		{
			if (!isVisited[near])
			{
				isVisited[near] = true;
				q.push(near);
			}
		}
	}

	cout << endl;
}

BFS(Start : 0) 출력 결과

 

DFS VS BFS

DFS VS BFS - https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89

 

항목	BFS (너비 우선 탐색)	DFS (깊이 우선 탐색)
탐색 방식	가까운 노드부터 차례대로 탐색 (레벨별 탐색)	한 방향으로 깊게 탐색 후 되돌아가서 다른 방향 탐색
사용 자료 구조	큐 (Queue)	스택 (Stack) 또는 재귀 (Recursion)
최단 경로	가중치가 동일한 경우 최단 경로 보장	최단 경로 보장하지 않음
공간 복잡도	큐에 많은 노드를 저장해야 하므로 메모리 사용 많음	깊이에 따라 스택이나 재귀로 메모리 사용 적음
탐색 순서	레벨 순서대로 탐색	깊이 순서대로 탐색
적합한 경우	최단 경로를 찾거나, 레벨 기반 문제 해결 시	경로를 찾거나, 그래프의 연결 여부를 확인할 때

 

 

 

 

---

https://www.wscubetech.com/resources/dsa/dfs-vs-bfs

DFS vs BFS Algorithm (All Differences With Example)