알고리즘, 코테 준비

그래프 탐색

Multitab 2022. 11. 6. 21:52

DFS,BFS 뼈대 코드

//DFS 뼈대코드
//스택을 이용
bool visited[N];
vector<int> graph[N];

void dfs(int x) {
    visited[x] = true;
    for (int i = 0; i < graph.size(), i++) {
        int y = graph[x][i];
        if (!visited[y])
            dfs(y);
    }
}
//BFS의 뼈대 코드
//Queue를 이용
#include <queue>

bool visited[N];
vector<int> graph[N];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            q.push(y);
            visited[y] = true;
        }
    }
}