[C++] 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

정의

BFS(Breadth-First Search): 현재 노드에서 인접한 노드 탐색

DFS(Depth-First Search): 최대한 깊이 이동 후 다음 경로 탐색

• 모든 노드를 탐색할 때의 시간 복잡도는 같지만, 그렇지 않을 경우 BFS가 더 빠르다.
• DFS를 재귀로 구현할 때 스택 영역 오버플로우를 주의해야 한다.
• DFS의 스택 구현은 방문 하다가 막히면 pop 하는 방식이다.

	BFS	DFS
언제 사용할까?	최소 경로를 탐색할 때	경로의 특징을 저장해야 할 때
무엇으로 구현할까?	queue	stack 또는 재귀
시간복잡도	인접 리스트 O(V+E) 인접 행렬 O(n²)	인접 리스트 O(V+E) 인접 행렬 O(n²)

 

BFS 예시 코드

// 간선으로 이동

bool visited[101]; // 방문 배열 (중복 확인)
vector<int> edge[101]; // 정점 별 간선

void bfs() {
    queue<int> q;
    visited[1] = true;
    q.push(1);
    
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        
        for(int i = 0; i < edge[cur].size(); i++) {
        	int next = edge[cur][i];
            
            if(visited[next]) continue;
     		
            visited[next] = true;
            q.push(next);
        }
    }
}

 

DFS 예시 코드

// 연결된 간선으로 이동

bool is_cycle = false;
bool visited[101]; // 방문 배열 (중복 확인)
bool finished[101]; // 종료 배열 (사이클 확인)
vector<int> edge[101]; // 정점 별 간선

void dfs(int cur) {
	if(is_cycle) return;
	
    if(!visited[cur]) {
    	visited[cur] = true;
    	for(int i = 0; i < edge[cur].size(); i++) {
        	int next = edge[cur][i];
            dfs(next);
    	}
    }
    else if(visited[cur] && !finished[cur])
    	is_cycle=true;
        
    finished[cur] = true;
}