[c++/그래프] BFS (너비 우선 탐색)

너비 우선 탐색이란

1.현재 정점과 인접한 모든 정점 방문

2. 이들 정점과 인접한 모든 정점 찾아서 방문

그래프의 모든 정점을 탐색할 때까지 위의 과정 반복

​

시작 정점으로부터 가까운 정점 먼저 방문, 멀리 떨어져있는 정점 나중에 방문한다.

​

큐 이용하여 구현

​

DFS와 같은 수식

bool isVisited[N] = { };

-> 정점 방문 여부 검사

-> 정점 방문 여부를 검사하지 않으면 무한 루프에 빠질 수 있다.

<큐를 이용한 BFS 구하기>

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

vector<int> bfs(const vector<vector<int>>& adj_list, int s) {
	vector<bool> visited(adj_list.size(), false);
	vector<int> visit_order;
	queue<int> q;
	q.push(s);

	while (!q.empty()) {
		int v = q.front();
		q.pop();

		if (visited[v]) continue;

		visited[v] = true;
		visit_order.push_back(v);

		for (int a : adj_list[v]) {
			if (!visited[a])
				q.push(a);
		}
	}
	return visit_order;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<vector<int>> adj_list = { {1,3,4},{0,2,4},{1,5},{0,4},{0,1,3},{2} };

	bfs(adj_list, 0);
	cout << endl;
} //0 1 3 4 2 5

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> isVisited(n,false);
    int cnt=0;
    
    //전체 다 돌면서 네트워크 연결 됐나 확인 
    for(int i=0;i<n;i++){
        //만약 이미 연결 되어있으면 pass
        if(isVisited[i]) continue;
        
        queue<int> q;
        q.push(i);
        
        while(!q.empty()){
            int v=q.front();
            q.pop();
            
            if(isVisited[v]) continue;
            
            isVisited[v]=true;
            
            for(int j=0;j<n;j++){
                if(computers[v][j]==1 && !isVisited[j])
                    q.push(j);
            }
        }
        cnt++;
    }
    
    answer=cnt;
    return answer;
}