[#1260] DFS와 BFS

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
int n, m, v;
vector<vector<int>> node(10001);
vector<bool> visit(10001, false);
queue<int> q;
vector<bool> discover(10001, false);
 
void dfs(int here) {
    visit[here] = true;
    printf("%d ", here);
 
    for (int i = 0; i < node[here].size(); i++) {
        int there = node[here][i];
        if (!visit[there]) {
            dfs(there);
        }
    }
}
 
int main() {
    
    
    scanf("%d %d %d", &n, &m, &v);
 
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        node[a].push_back(b);
        node[b].push_back(a);
    }
 
    for (int i = 1; i <= n; i++) {
        sort(node[i].begin(), node[i].end());
    }
    
    //dfs
    dfs(v);
    printf("\n");
 
    //bfs
    q.push(v);
    discover[v] = true;
    
    while (!q.empty()) {
        int here = q.front();  
        printf("%d ", here);
        q.pop();  //방문
 
        for (int i = 0; i < node[here].size(); i++) {
            int there = node[here][i];
            if (!discover[there]) {
                q.push(there);
                discover[there] = true;
            }
        }
    }
 
    return 0;
}

 

그래프 표현에 인접 리스트 사용

dfs는 재귀 또는 스택, bfs는 큐