[알고리즘] BFS/DFS 의사코드

 

 

BFS 의사코드 (Pseudocode)

// 그래프의 인접 리스트 표현
vector<vector<int>> adj;
// start에서 시작해 그래프를 너비 우선 탐색한다.
// 그리고, 각 정점의 방문 순서를 반환한다. (order)
vector<int> bfs(int start) {
	// 각 정점의 방문 여부 
    vector<bool> discovered(adj.size(), false);
    // 방문할 정점 목록을 유지하는 큐
    queue<int> q;
    
    // 정점의 방문 순서
    vector<int> order;
    discovered[start] = true;
    
    // (1) 초기값 하나 넣고
    q.push(start);
    while(!q.empty()) {
    	// (2) 하나 poll한 후.
    	int here = q.front();
        q.pop();
        // here를 방문한다.
        order.push_back(here);
        // 모든 인접한 정점을 검사한다.
        for (int i = 0; i < adj[here].size(); ++i) {
        	int there = adj[here][i];
            // 처음 보는 정점이면 방문 목록에 집어넣는다.
            // (3) 큐에 하나 넣고, 방문 목록 집어넣기.
            if (!discovered[there]) {
            	q.push(there);
                discovered[there] = true;
            }
        }
    }
    return order;
}

 

 

 

DFS 의사코드

// 그래프의 인접 리스트 표현
vector<vector<int>> adj;
// 각 정점을 방문했는지 여부를 나타낸다.
vector<bool visited;

void dfs(int here) {
	cout << "DFS visits " << here << endl;
    // (1) 방문 목록에 추가.
    visited[here] = true;
    // (2) 모든 인접 정점을 순회하면서
    for (int i = 0; i < adj[here].size(); ++i) {
    	int there = adj[here][i];
        // 아직 방문한 적 없다면 방문한다.
        // (3) 방문 목록에 없다면, 깊이 탐색
        if (!visited[there]) {
        	dfs(there);
        }
    }
    // 더이상 방문할 정점이 없으니, 재귀 호출을 종료하고 이전 정점으로 돌아간다.
}
// 모든 정점을 방문한다.
void dfsAll() {
	// visited를 모두 false로 초기화
    visited = vector<bool>(adj.size(), false);
    // 모든 정점을 순회하면서, 아직 방문한 적 없으면 방문한다.
    for(int i = 0; i < adj.size(); ++i) {
    	if (!visited[i]) {
        	dfs(i);
        }
    }
}

 

참고자료

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html