백준 1260 DFS와 BFS [C++]

문제 링크 : https://www.acmicpc.net/problem/1260

소스코드

#include <iostream>

#include <queue>

using namespace std;

class GraphType {

    int n;

    int adj_list[1001][1001];

    bool visted[1001];

    int start;

public:

    GraphType(int n, int v) {

        this->n = n;

        for (int i = 1; i <= n; ++i)

            visted[i] = false;

        for (int i = 1; i <= n; ++i) {

            for (int j = 1; j <= n; ++j)

                adj_list[i][j] = 0;

        }

    }

    void insert_edge(int u, int v);

    void depth_frist_search(int v);

    void breadth_first_search(int v);

    void resetVisted() {

        for (int i = 1; i <= n; ++i)

            visted[i] = false;

    }

};

void GraphType::insert_edge(int u, int v) {

    if (u > n || v >n)

        return;

    adj_list[u][v] = 1;

    adj_list[v][u] = 1;

}

void GraphType::depth_frist_search(int v) {

    visted[v] = true;

    cout << v << ' ';

    for (int i = 1; i <= n; ++i) {

        if (!visted[i] && adj_list[v][i])

            depth_frist_search(i);

    }

}

void GraphType::breadth_first_search(int v) {

    visted[v] = true;

    cout << v << ' ';

    queue<int> q;

    q.push(v);

    while (!q.empty()) {

        v = q.front();

        q.pop();

        for (int i =1; i <= n; ++i) {

            if (!visted[i] && adj_list[v][i]) {

                visted[i] = true;

                cout << i << ' ';

                q.push(i);

            }

        }

    }

}

int main() {

    int n, vCount, start;

    cin >> n >> vCount >> start;

    GraphType *g = new GraphType(n, vCount);

    for (int i = 0; i < vCount; ++i) {

        int u, v;

        cin >> u >> v;

        g->insert_edge(u, v);

    }

    g->depth_frist_search(start);

    cout << endl;

    g->resetVisted();

    g->breadth_first_search(start);

    delete g;

}

DFS는 깊이 우선 탐색으로 노드에서 가장 인접한 노드 순서 대로 방문합니다.

만약 인접한 노드들 중, 방문한 노드가 있다면 넘어갑니다.

정점을 방문 후, 인접한 노드에 대해 방문하지 않았다면 그 노드에 대한 DFS를 반복합니다.

BFS는 너비 우선 탐색으로 시작 정점으로 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문합니다.

큐를 사용하여 노드를 큐에 넣고, 방문을 하면 큐에서 뺍니다. 노드에서 인접한 노드들을 큐에 넣고, 방문을 하며 큐에서 빼고 방문한 노드의 인접한 점을 다시 큐에 넣습니다. 이렇게 모든 노드를 방문 할 때까지 반복합니다.