DFS [c++]

ㅇ 시작 노드와 가까운 순서대로 맹목적 탐색이 이루어진다.

ㅇ 스택을 이용하여 구현하지만 재귀함수를 이용하면 재귀함수는 스택의 원리를 이용하고 있기 때문에

스택이 없어도 구현 가능하다.

 

1. 스택에서 최상단 노드를 확인한다.

2. 최상단 노드에 방문하지 않은 연결된 노드가 있으면 그 노드를 스택에 넣고 방문처리한다. 인접노드가

없다면 스택에서 최상단 노드를 제거한다.

 

아래 코드는 baekjoon 1260번 문제의 양식에 맞게 작성한 코드 이다.

 

// dfs
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,m,startNode;

 

vector<bool> visit;
vector<vector<int>> node;

void dfs(int start) {
    if(visit[start]) return; // 해당(시작) 노드가 방문 노드라면 리턴
    visit[start] = true; // 방문하지 않았다면 방문처리
    cout << start << ' ';
    for(int i=0; i < node[start].size(); i++) { // 해당 노드의 연결 노드들을 모두 확인하기 위한 코드
        int y = node[start][i]; 
        dfs(y);
    }
}

int main() {
    int a,b;
    cin >> n >> m >> startNode;
    node.resize(n+1);
    for(int i=0; i<m; i++) {
        cin >> a >> b;
        node[a].push_back(b);   
        node[b].push_back(a);
    }
    for (int i = 0; i < node.size(); i++) { 
    sort(node[i].begin(), node[i].end()); 
    }
    visit = vector<bool>r(n + 1, false); // for initialize 

    dfs(startNode);
    
    return 0;    
}

아래 그림은 bfs와 dfs의 차이를 설명한 그림이다.

[그림 출처 : https://namu.wiki/w/BFS]

 

 

cf) visit를 배열을 써서 구현 할 경우 memset(visit, false, sizeof(visit)) 로 초기화를 할 수 있다.

 

 

 

 

ref) http://youtube.com/watch?v=l0Rsu7dziws