[알고리즘] 너비 우선 탐색 (BFS)

치치·2025년 1월 23일

알고리즘

알고리즘C++

목록 보기

16/24

너비 우선 탐색

시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 탐색 방법이다
더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 탐색을 적용한다
주로 Queue 자료구조를 사용한다
-> Queue 자료구조는 먼저 들어온 요소가 먼저나가는 선입선출(FIFO)방식이기 때문에 너비 우선 탐색에 알맞다

아래의 그래프를 사용해서 깊이 우선 탐색을 진행해보자

너비 우선 탐색을 사용한 그래프 탐색

배열 생성 & 값 초기화 & 정점들의 간선 연결

깊이 우선 탐색과 동일하게 방문배열과 정점의 집합을 담을 그래프 배열을 선언
너비 우선 탐색은 Queue를 사용하기 때문에 #include<.queue>
무방향 그래프로 만들었기 때문에 간선을 서로 연결해준다

#include <iostream>
#include <vector>
#include <queue>
#define SIZE 8
using namespace std;

class Graph
{
private:
	// 방문 배열
	bool visited[SIZE];

	// 정점의 집합 (그래프)
	vector<int> graph[SIZE];

	// 탐색할 노드 관리할 큐
	queue<int> queue;

public:
	Graph()
	{
		// 방문 배열 초기화
		for (int i = 0; i < SIZE; i++)
		{
			visited[i] = false;
		}
	}

	// 정점들을 연결
	void Insert(int vertex, int edge)
	{
		graph[vertex].push_back(edge);
		graph[edge].push_back(vertex);
	}

너비 우선 탐색

순서
1. 첫 시작노드는 큐에 넣고 방문체크를 해준다
-> 큐가 비어있지 않아야 아래의 while문이 실행되기 때문이다

큐가 비어있지 않다면, 큐의 가장 앞의 값을 따로 저장해두고 큐의 가장 앞의 값을 빼준다
따로 저장한 값을 출력한다
해당 정점과 연결된 정점들을 탐색한다
-> 만약 연결된 정점이 방문되지 않은 정점이라면 큐에 넣고 방문체크 해준다
연결된 정점을 다 탐색했으면 안쪽 로직을 다 끝내고 다시 while문 반복(큐가 비어있지 않기 때문에)
큐가 빌때까지 반복 수행

// 너비 우선 탐색
void Search(int start)
{
	// 큐에 root노드의 값 넣기
	queue.push(start);

	// 방문체크
	visited[start] = true;
	
	
	// 큐가 비지 않았으니 반복문 시작 (start = 1이 들어간 상태)
	while (!queue.empty())
	{
		// 1. 임시 변수에 큐의 가장 앞에 값 저장
		int x = queue.front();

		// 2. 큐에서 빼기 -> 밑에 로직을 수행한 뒤 큐가 비었다면 종료된다
		queue.pop();

		// 3. 출력
		cout << x << " " ;

		// 4. 연결된 정점들 탐색
		for (int i = 0; i < graph[x].size(); i++)
		{
			// 연결된 정점
			int next = graph[x][i];

			if (!visited[next])
			{
				// 방문되지 않았다면 연결된 정점을 큐에 다 넣어주기
				queue.push(next);
				visited[next] = true; // 방문 체크
			}
		}
	}
}

너비 우선 탐색 전체코드

#include <iostream>
#include <vector>
#include <queue>
#define SIZE 8
using namespace std;

class Graph
{
private:
	// 방문 배열
	bool visited[SIZE];

	// 정점의 집합 (그래프)
	vector<int> graph[SIZE];

	// 탐색할 노드 관리할 큐
	queue<int> queue;

public:
	Graph()
	{
		// 방문 배열 초기화
		for (int i = 0; i < SIZE; i++)
		{
			visited[i] = false;
		}
	}

	// 정점들을 연결
	void Insert(int vertex, int edge)
	{
		graph[vertex].push_back(edge);
		graph[edge].push_back(vertex);
	}
	
	// 너비 우선 탐색
	void Search(int start)
	{
		// 큐에 root노드의 값 넣기
		queue.push(start);
	
		// 방문체크
		visited[start] = true;
		
		
		// 큐가 비지 않았으니 반복문 시작 (start = 1이 들어간 상태)
		while (!queue.empty())
		{
			// 1. 임시 변수에 큐의 가장 앞에 값 저장
			int x = queue.front();

			// 2. 큐에서 빼기 -> 밑에 로직을 수행한 뒤 큐가 비었다면 종료된다
			queue.pop();

			// 3. 출력
			cout << x << " " ;

			// 4. 연결된 정점들 탐색
			for (int i = 0; i < graph[x].size(); i++)
			{
				// 연결된 정점
				int next = graph[x][i];

				if (!visited[next])
				{
					// 방문되지 않았다면 연결된 정점을 큐에 다 넣어주기
					queue.push(next);
					visited[next] = true; // 방문 체크
				}
			}
		}
	}
};

int main()
{
#pragma region 너비 우선 탐색 (Breadth First Search)
	// 시작 정점을 방문한 후 시작 정점에 인접한
	// 모든 정점들을 우선 방문하는 방법입니다.

	// 더 이상 방문하지 않은 정점이 없을 때까지
	// 방문하지 않은 모든 정점들에 대해서도 너비 우선 탐색을 적용합니다.

	Graph graph;

	graph.Insert(1, 2);
	graph.Insert(1, 3);

	graph.Insert(2, 4);
	graph.Insert(2, 5);

	graph.Insert(3, 6);
	graph.Insert(3, 7);


	graph.Search(1);

#pragma endregion





	return 0;
}