BFS 너비 우선 탐색

BFS : Breadth Frist Search : 너비 우선 탐색

출처 : 나무위키

트리나 그래프에서 특정 노드를 시작으로 인접 노드를 먼저 탐색한 후, 다음 레벨로 이동하여 인접 노드를 탐색한다

이러한 방법으로 모든 노드를 탐색하는 것을 BFS라고 한다

 

큐로 구현 가능하다

 

최단 경로 찾기, 최소 비용 문제, 최소 이동 or 변경 문제, 스도쿠 등에서 활용 가능하다

 

void bfs(int node, vector<int> graph[], bool visited[], std::queue<int> q)
{
	q.push(node);
	visited[node] = true;
    
    while (!q.empty())
    {
    	int current = q.front();
        q.pop();
        
        std::cout << current << ' ';
        
        for (int i = 0; i < graph[current].size(); i++)
        {
        	int next = graph[current][i];
            
        	if (!visited[next])
            {
            	q.push(next);
                visited[next] = true;
            }
        }
    }
}

// 큐 생성
std::queue<int> q;	// #include <queue>

// 방문 체크용 배열 생성
bool visited[노드 개수 + 1] = {false};

// 그래프 생성
vector<int> graph[노드 개수 + 1];

for (int i = 0; i < 간선 개수; i++)
{
	int x, y;
    
    std::cin >> x >> y;
    
    graph[x].push_back(y);
    graph[y].push_back(x);
}

for (int i = 1; i <= 노드 개수; i++)
{
	std::sort(graph[i].begin(), graph[i].end());	// #include <algorithm>
}

// BFS 사용
bfs(시작할 노드 번호, graph, visited, q);

 

활용은 알아서~