03)BFS[Breadth-First Search, 너비 우선탐색]

▣Breadth-First Search(너비우선탐색)

: 그래프의 모든정점을 방문하는 알고리즘 중 하나이다.

-> 탐색의 기준 : 자신과 인접한 모든 간선을 우선적으로 검사하며, 그 중  visit하지 않은 정점을 찾아 순차적으로 visit해 나아간다.

                    : 더이상 visit할 정점이 없을 때 까지 반복한다.

                    : 인전한 간선을 우선적으로 검사하기 위하여 Queue를 이용하여 준다.

<알고리즘 진행순서>

현재 visit한 정점에 인접한 모든 정점을 우선적으로 수행하기 위하여 큐에 넣어준다.

example)

1을 visit 하면서 인접한 정점인 2, 3 그리고 7을 큐에 넣어준다.

그리고 큐에 들어간 순서대로 visit하면 반복 수행해 준다.

(큐의 상태가 empty가 될 때까지 반복 됨을 알 수 있다.)

Tip) BFS는 pop된 vertex에 연결되어 있는 vertex를 검사하여 queue에 넣을때 거리를 1증가시켜 저장 시켜놓으면 해당 vertex로부터 얻고자하는 vertex까지의 거리를 구할 수 있습니다.

물론, 각 노드까지의 거리를 저장할 자료구조는 따로 고려를 해야합니다.

<소스코드>

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
 
#define MAX_VERTEX 101
#define VISIT 1
#define UN_VISIT 0
#define CONNECTED 1
using namespace std;
/*
기본적으로 행렬기반으로 구현
v : vertex
e : edge
n : vertex의 개수
m : edge의 개수

Edge_table : 간선 연결 여부 테이블
Vertex_table : 정점 visit 여부 확인 테이블
Finish_table : 탐색이 완료된 정점 순서대로 저장하는 테이블
Visit_table : visit 된 순서대로 vertex를 저장

UN_VISIT : 아직 탐색
VISIT : 자식 탐색이 종료
*/
int Edge_table[MAX_VERTEX][MAX_VERTEX];
int Vertex_table[MAX_VERTEX];
 
void BFS(int v_i) {
    Vertex_table[v_i] = VISIT;
    queue<int> q;
    q.push(v_i);
    cout << v_i << " ";
    while (!q.empty()) {
        int t_v = q.front();
        q.pop();
 
        for (int i = 0; i < MAX_VERTEX; i++) {
            if (Edge_table[t_v][i] == CONNECTED && Vertex_table[i] == UN_VISIT) {
                cout << i << " ";
                q.push(i);
 
                Vertex_table[i] = VISIT;
            }
        }
    }
}
 
 
 
int main() {
    int n;
    int m;
    cout << "vertex 개수 : ";
    cin >> n;
    cout << "edge 개수 : ";
    cin >> m;
 
    cout << "edge 정보 입력" << endl;
    for (int i = 0; i < m; i++) {
        int v_1, v_2;
        cin >> v_1 >> v_2;
        Edge_table[v_1][v_2] = 1;
        Edge_table[v_2][v_1] = 1;
    }
 
 
    memcpy(Vertex_table, Vertex_table + MAX_VERTEX, UN_VISIT);
    cout << "BFS 탐색결과" << endl;
 
    for (int i = 1; i <= n; i++) {
        if (Vertex_table[i] == UN_VISIT) {
            BFS(i);
        }
    }
    cout << endl;
    
    return 0;
}

: 그래프 자체는 배열을 기반으로 구현하였습니다.

<성능>

모든 정점을 방문 하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)이다.

(그림 참고)https://www.codeground.org/common/popCodegroundNote