BFS

BFS

그래프를 탐색하는 알고리즘이며 어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기전 현재 깊이의 모든 정점을 탐색하며 방먼한 정점은 다시 방문하지 않는 알고리즘으로 같은 가중치를 가진 그래프에서 최단거리알고리즘으로 쓰인다.

 

BFS(G, u){
	u.visited = 1;
    q.push(u);
    while(q.size()){
    	u = q.front();
        q.pop()
        for each : G.adj[u]
        	if v.visited = false{
            	v.visited = u.visited + 1
                q.push(v)
            }
    }
}

 

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> adj[100];
int visited[100];
int nodeList[] = {10, 12, 14, 16, 18, 20, 22, 24};

void bfs(int here){
    queue<int> q;
    visited[here] = 1;
    q.push(here);
    while(q.size()){
        int here = q.front();
        q.pop();
        for(int there : adj[here]){
            if(visited[there]) continue;
            visited[there] = visited[here] + 1;
            q.push(there);
        }
    }
}

int main()
{
    adj[10].push_back(12);
    adj[10].push_back(14);
    adj[10].push_back(16);
    
    adj[12].push_back(18);
    adj[12].push_back(20);
    
    adj[20].push_back(22);
    adj[20].push_back(24);
    bfs(10); //10번부터 탐색
    for(int i : nodeList){
        cout << i << " : " << visited[i] << '\n';
    }
    cout << "10번으로부터 24번까지 최단거리는 :" << visited[24] - 1 << '\n';
}

 

Q. 시작지점이 다수라면 ?

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> adj[100];
int visited[100];
int nodeList[] = {10, 12, 14, 16, 18, 20, 22, 24};

void bfs(int here){
	queue<int> q;
	for(int i = 0; i < 3; i++){
    	visited[i] = 1;
        q.push(i);
    }

    while(q.size()){
        int here = q.front();
        q.pop();
        for(int there : adj[here]){
            if(visited[there]) continue;
            visited[there] = visited[here] + 1;
            q.push(there);
        }
    }
}