C++ 그래프를 이용한 BFS / DFS 계속 업데이트할 예정

출처 : https://www.youtube.com/watch?v=tWVWeAqZ0WU

 

첫번째 문제

#include <iostream>
#include <format>
#include <vector>
#include <stack>
#include <queue>
 
using namespace std;
 
#define TOTAL_SIZE 1000
#define y first
#define x second
 
vector<char> graph[TOTAL_SIZE];
bool visited[TOTAL_SIZE]{ false };
int edge = 0;
 
void DFS(int _start)
{
    cout << "DFS 시작" << endl;
    // 출력 순서 > a b d f c e
    stack<char> s;
    s.push(_start);
    visited[_start] = true;
 
    while (!s.empty())
    {
        auto top = s.top();
        cout << format("{} ", top);
        s.pop();
 
        for (int i = 0; i < graph[top].size(); i++)
        {
            auto current = graph[top][i];
 
            if (!visited[current])
            {
                visited[current] = true;
                s.push(current);
            }
        }
    }
}
 
void BFS(int _start)
{
    cout << "\n\nBFS 시작" << endl;
    memset(visited, 0, sizeof(visited));
    // 출력 순서 > a b c d e f
    queue<char> q;
    q.push(_start);
    visited[_start] = true;
 
    while (!q.empty())
    {
        char front = q.front();
        cout << format("{} ", front);
        q.pop();
 
        for (int i = 0; i < graph[front].size(); i++)
        {
            auto current = graph[front][i];
 
            if (!visited[current])
            {
                visited[current] = true;
                q.push(current);
            }
        }
    }
}
 
int main()
{
    // 그래프 생성
    // a > c
    // v   v
    // b   e
    // v  
    // d > f
    pair<char, char> tmp_pair[]
    {
        { 'a' , 'c'},
        { 'a' , 'b'},
        { 'c' , 'e'},
        { 'b' , 'd'},
        { 'd' , 'f'}
    };
    for (int i = 0; i < 5; i++)
    {
        auto data = tmp_pair[i];        
        graph[data.y].push_back(data.x);
        graph[data.x].push_back(data.y);
    }
    DFS(tmp_pair[0].y);
    BFS(tmp_pair[0].y);
    return 0;
}

두번째 문제

#include <iostream>
#include <format>
#include <vector>
#include <stack>
#include <queue>
 
using namespace std;
 
#define TOTAL_SIZE 1000
#define y first
#define x second
 
vector<char> graph[TOTAL_SIZE];
bool visited[TOTAL_SIZE]{ false };
int edge = 0;
 
bool DFS(int _start, char _find)
{
    cout << "DFS 시작" << endl;
    // 출력 순서 > a b d f c e
    stack<char> s;
    s.push(_start);
    visited[_start] = true;
 
    while (!s.empty())
    {
        auto top = s.top();
        cout << format("{} ", top);
        s.pop();
 
        if (top == _find)
            return true;
 
        for (int i = 0; i < graph[top].size(); i++)
        {
            auto current = graph[top][i];
 
            if (!visited[current])
            {
                visited[current] = true;
                s.push(current);
            }
        }
    }
    return false;
}
 
bool BFS(int _start, char _find)
{
    cout << "\n\nBFS 시작" << endl;
    memset(visited, 0, sizeof(visited));
    // 출력 순서 > a b c d e f
    queue<char> q;
    q.push(_start);
    visited[_start] = true;
 
    while (!q.empty())
    {
        char front = q.front();
        cout << format("{} ", front);
        q.pop();
 
        if (front == _find)
            return true;
 
        for (int i = 0; i < graph[front].size(); i++)
        {
            auto current = graph[front][i];
 
            if (!visited[current])
            {
                visited[current] = true;
                q.push(current);
            }
        }
    }
    return false;
}
 
int main()
{
    // 그래프 생성
    // f > g > h
    // v /> 
    // i < j
    // v  
    // k
    pair<char, char> tmp_pair[]
    {
        { 'f' , 'g'},
        { 'f' , 'i'},
        { 'i' , 'k'},
        { 'i' , 'g'},
        { 'j' , 'i'},
        { 'g' , 'h'}
    };
    char src = 'j', dst = 'f';
    for (int i = 0; i < sizeof(tmp_pair) / sizeof(int); i++)
    {
        auto data = tmp_pair[i];        
        graph[data.y].push_back(data.x);
        graph[data.x].push_back(data.y);
    }
    cout << DFS(src, dst) << endl;
    cout << BFS(src, dst) << endl;
    return 0;
}