1260 : DFS와 BFS (C++)

1260번: DFS와 BFS

---

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

using namespace std;

void dfs(int start, vector<int> graph[], bool check[]) {
    check[start] = true;
    printf("%d ", start);

    for(int i = 0; i < graph[start].size(); i++) {
        int next = graph[start][i];
        if(check[next] == false) {
            dfs(next, graph, check);
        }
    }
}

void bfs(int start, vector<int> graph[], bool check[]) {
    queue<int> q;

    q.push(start);
    check[start] = false;

    while(!q.empty()) {
        int tmp = q.front();
        q.pop();
        printf("%d ", tmp);
        for(int i = 0; i < graph[tmp].size(); i++) {
            if(check[graph[tmp][i]] == true) {
                q.push(graph[tmp][i]);
                check[graph[tmp][i]] = false;
            }
        }


    }
}

int main() {
    int n, m, start;
    cin >> n >> m >> start;

    vector<int> graph[n + 1];
    bool check[n + 1];
    fill(check, check+n+1, false);

    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    for(int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end());
    }

    dfs(start, graph, check);
    printf("\n");
    bfs(start, graph, check);

    return 0;
}

C++의 vector를 통해 인접리스트로 구현한 DFS와 BFS.

 

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

#define MAX_VALUE 1001

int N, M, V;
int mat[MAX_VALUE][MAX_VALUE];
int visit[MAX_VALUE];

void dfs(int v) {
    printf("%d ", v);

    visit[v] = 1;

    for(int i = 1; i <= N; i++) {
        if(visit[i] == 0 && mat[v][i] == 1) {
            dfs(i);
        }
    }
}

void bfs(int v) {
    queue<int> q;

    q.push(v);
    visit[v] = 0;
    while(!q.empty()) {
        v = q.front();
        printf("%d ", v);
        q.pop();
        for(int i = 1; i <= N; i++) {
            if(visit[i] == 1 && mat[v][i] == 1) {
                q.push(i);
                visit[i] = 0;
            }
        }
    }
}
 
int main() {
    int x, y;
    cin >> N >> M >> V;

    for(int i = 0; i < M; i++) {
        cin >> x >> y;
        mat[x][y] = mat[y][x] = 1;
    }
    dfs(V);
    printf("\n");
    bfs(V);

    return 0;
}

인접 행렬로 구현한 DFS와 BFS.