DFS(Depth Fisrt Search)

이거는 깊이 우선 탐색으로 그래프를 전체 탐색하는 방법 중 하나로 branch로 넘어가기 전에 해당 branch를 탐색하고 다음으로 넘어가는 방법

재귀함수와 스택으로 구현

- 노드 방문 여부를 반드시 검사해야함

- 탐색과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한이 필요

- 발견되지 않을시 노드의 부모노드로 돌아옴

장점

- 경로 발견에 용이

특정 노드에 도달하는 경로를 빠르게 찾고 싶을 때 유용합니다.

- 사이클 탐지에 유리

방향 그래프에서 사이클 존재 여부를 판별하는 데 유용

단점

- 최단 경로 보장 X

- 무한 루프 위험

순환 구조(사이클)가 있는 그래프에서 방문 기록을 남기지 않으면, 무한 루프에 빠질 수 있슴

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

// index 0은 사용하지 않음으로 배열을 하나 더 추가
bool visited[10]; // 노드가 1~9까지 있으므로 크기는 10으로 설정
vector<int> graph[10]; // 그래프의 인접 리스트

// DFS 함수 (재귀 호출)
void dfs(int x) {
    visited[x] = true; // 현재 노드 방문 처리
    cout << x << " "; // 방문한 노드 출력

    // 현재 노드에 인접한 노드들 탐색
    for (int i = 0; i < graph[x].size(); i++) {
        int y = graph[x][i]; // 인접 노드 번호
        if (!visited[y]) { // 방문하지 않은 노드라면
            dfs(y); // 재귀적으로 DFS 호출
        }
    }
}

int main(void) {
    // 주어진 방향 그래프 정의
    graph[1].push_back(2);

    graph[2].push_back(3);
    graph[2].push_back(4);

    graph[3].push_back(7);
    graph[3].push_back(8);
    graph[3].push_back(9);

    graph[7].push_back(8);

    graph[4].push_back(5);
    graph[4].push_back(6);

    // DFS 실행 (시작 노드는 1)
    dfs(1);

    return 0;
}

BFS(Breadth First Search)

이거는 너비 우선 탐색으로 그래프에서 가장 가까운 노드로부터 우선적으로 탐색하는 알고리즘이다

큐 자료구조를 활용한다

- 탐색 시작 노드를 큐에 삽입하고 방문 처리한다

- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 상입 후 방문 처리한다

장점

- 최단 경로 탐색에 유리하다

- 모든 노드를 탐색가능하다

단점

- 높은 메모리 사용량이 필요하다

- 속도가 느릴 수 있다

- 가중치 있는 그래프 탐색에 부적합하다.

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

using namespace std;

// 방문 여부 확인 배열 (노드 1 ~ 6 사용)
bool visited[7];
vector<int> graph[7];

// BFS 함수 정의
void bfs(int start) {
    queue<int> q;
    q.push(start); // 시작 노드 삽입
    visited[start] = true; // 시작 노드 방문 처리

    // 큐가 빌 때까지 반복
    while (!q.empty()) {
        int x = q.front(); // 큐의 맨 앞 노드 추출
        q.pop();
        cout << x << " "; // 방문한 노드 출력

        // 해당 노드와 연결된 인접 노드 방문
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) { // 방문하지 않은 노드라면
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

int main(void) {
    // 그래프 초기화 (주어진 노드 연결 구조)
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(6);

    graph[2].push_back(1);
    graph[2].push_back(3);
    graph[2].push_back(4);

    graph[3].push_back(1);
    graph[3].push_back(2);
    graph[3].push_back(4);

    graph[4].push_back(2);
    graph[4].push_back(3);

    graph[6].push_back(1);
    graph[6].push_back(5);

    graph[5].push_back(6);

    // BFS 실행 (시작 노드는 1)
    bfs(1);

    return 0;
}