C++ 로 그래프에서 BFS (너비 우선 탐색) 마스터하기 - 알고리즘 학습

소개

이 랩에서는 C++ 를 사용하여 그래프에 대한 BFS (Breadth-First Search) 순회 알고리즘을 구현하는 방법을 배우게 됩니다. BFS 알고리즘은 그래프의 노드에서 시작하여 다음 레벨의 노드로 이동하기 전에 현재 깊이 레벨의 모든 노드를 탐색합니다. BFS 순회는 큐 (Queue) 라는 자료 구조를 활용합니다. 큐 자료 구조에 대해서도 자세히 설명하겠습니다.

프로젝트 설정

project 디렉토리로 이동합니다:

cd project

다음 명령을 사용하여 main.cpp라는 새 C++ 파일을 생성합니다:

touch main.cpp

필요한 라이브러리 포함

C++ 에서는 입출력을 위해 iostream을 사용하고, 요소를 동적으로 저장하기 위해 vector를 사용하며, BFS 순회 알고리즘을 구현하기 위해 queue를 사용합니다. 또한 모든 표준 라이브러리를 포함하기 위해 bits/stdc++.h 헤더 파일을 사용합니다. main.cpp 파일에 다음 코드를 입력합니다:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<bool> v;
vector<vector<int>> g;

BFS (너비 우선 탐색) 알고리즘 구현

시작 노드를 인수로 받는 bfsTraversal이라는 함수를 생성합니다. 이 함수는 BFS 순회 알고리즘을 처리합니다.

void bfsTraversal(int b)
{
    queue<int> q; // b 에 연결된 모든 노드를 저장할 큐 선언
    q.push(b); // 큐에 b 삽입
    v[b] = true; // b 를 방문한 것으로 표시

    cout << "\n\nThe BFS Traversal is:  ";

    while (!q.empty())
    {
        int a = q.front();
        q.pop(); // 큐에서 첫 번째 요소 삭제

        // 현재 노드에 연결된 모든 노드를 반복 처리
        for (auto j = g[a].begin(); j != g[a].end(); j++)
        {
            if (!v[*j])
            {
                v[*j] = true;
                q.push(*j); // 처리할 연결된 노드를 큐에 추가
            }
        }
        cout << a << "  ";
    }
}

그래프에 엣지 (Edge) 추가

두 개의 정점을 받아 그 사이에 엣지를 생성하는 makeEdge라는 함수를 생성합니다. 이 함수는 그래프의 각 엣지에 대해 호출됩니다.

void makeEdge(int a, int b)
{
    g[a].push_back(b); // 정점 a 에서 정점 b 로의 엣지
}

그래프 정보 입력 받기

이 단계에서는 정점 및 엣지 수, 엣지의 소스 및 대상 정점을 포함한 그래프 정보를 사용자로부터 입력받고, 벡터를 초기화합니다.

int main()
{
    int n, e, a, b, i;

    cout << "정점의 수를 입력하세요: ";
    cin >> n;

    cout << "엣지의 수를 입력하세요: ";
    cin >> e;

    v.assign(n, false);
    g.assign(n, vector<int>());

    cout << "소스 및 대상 정점을 사용하여 엣지를 입력하세요: ";

    for (i = 0; i < e; i++)
    {
        cin >> a >> b;
        makeEdge(a, b);
    }

    for (i = 0; i < n; i++)
    {
        if (!v[i])
        {
            bfsTraversal(i);
        }
    }

    return 0;
}

프로그램 컴파일 및 실행

다음 단계는 코드를 컴파일하고 실행하는 것입니다. 터미널에서 다음 명령을 실행합니다.

g++ main.cpp -o main && ./main

터미널에서 그래프의 BFS (너비 우선 탐색) 순회 알고리즘의 출력을 확인할 수 있습니다.

`main.cpp` 파일의 전체 코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<bool> v;
vector<vector<int>> g;

void bfsTraversal(int b)
{
    queue<int> q;
    q.push(b);
    v[b] = true;

    cout << "\n\nThe BFS Traversal is:  ";

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

        for (auto j = g[a].begin(); j != g[a].end(); j++)
        {
            if (!v[*j])
            {
                v[*j] = true;
                q.push(*j);
            }
        }
        cout << a << "  ";
    }
}

void makeEdge(int a, int b)
{
    g[a].push_back(b);
}

int main()
{
    int n, e, a, b, i;

    cout << "정점의 수를 입력하세요: ";
    cin >> n;

    cout << "엣지의 수를 입력하세요: ";
    cin >> e;

    v.assign(n, false);
    g.assign(n, vector<int>());

    cout << "소스 및 대상 정점을 사용하여 엣지를 입력하세요: ";

    for (i = 0; i < e; i++)
    {
        cin >> a >> b;
        makeEdge(a, b);
    }

    for (i = 0; i < n; i++)
    {
        if (!v[i])
        {
            bfsTraversal(i);
        }
    }

    return 0;
}

요약

이 랩에서는 C++ 을 사용하여 그래프에서 BFS (너비 우선 탐색) 순회 알고리즘을 구현하는 방법을 배웠습니다. 이 알고리즘은 시작 노드에서 시작하여 그래프의 모든 노드를 탐색합니다. BFS 알고리즘을 구현하기 위해 큐 (queue) 자료 구조를 사용했습니다. 이 랩을 완료함으로써 그래프 순회 알고리즘에 대한 이해도를 높였습니다.

그래프에서 BFS (너비 우선 탐색) 구현하기

소개