[c++] DFS(Depth First Search) 알고리즘

BFS 알고리즘은 깊이를 우선으로 탐색하는 알고리즘 입니다.

즉, 현재 정점에 갈 수 있는 노드까지 들어가며 탐색합니다.

주로 stack 혹은 재귀함수를 이용해서 구현합니다.

 

 

 

 

c++로 dfs를 구현해보겠습니다.

위 그래프의 1 노드에서 갈 수 있는 노드까지 들어가며 탐색합니다.

아래 코드를 참고해주세요.

 

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<vector<int>> graph(7, vector<int> ());
vector<bool> visit(7, false);
 
void dfs(int start) {
    if (visit[start] == true)
        return;
    
    visit[start] = true;
    print("%d", start);
    
    for (int i = 0; i < gragh[start].size(); i++) {
        dfs(graph[start][i]);
    }
}
 
int main(void){
    graph[1].push_back(2);
    graph[2].push_back(1);
    
    graph[1].push_back(3);
    graph[3].push_back(1);
    
    graph[2].push_back(4);
    graph[4].push_back(2);
    
    graph[2].push_back(3);
    graph[3].push_back(2);
    
    graph[2].push_back(5);
    graph[5].push_back(2);
    
    graph[3].push_back(4);
    graph[4].push_back(3);
    
    graph[3].push_back(6);
    graph[6].push_back(3);
    
    dfs(1);
    
    return 0;
}