[알고리즘] 깊이 우선 탐색 DFS(Depth - First- Search)-C++

DFS

DFS(Depth-First-Search) : 깊이 우선 탐색

현재 탐색중인 경로를 끝까지 탐색하고 다음 경로로 넘어간다.

1. root 노드부터 먼저 검색

2. root노드의 자식 중 가장 왼쪽 노드 부터 탐색

3. 왼쪽 노드의 자식 중 왼쪽….을 탐색하고 다시 부모 노드로 돌아가서 오른쪽 자식 노드 탐색

4. 위 과정을 반복

   → 깊이 우선 탐색은 한 부모노드의 자식을 모두 한번에 검사하는게 아니라 한 가지를 타고 내려가서 가장 멀리있는 노드에 도달하고 나서 다음 다시 부모노드로 돌아와 다른 자식을 탐색한다.

🌟 주로 백트래킹 알고리즘에 사용

🎯EX

root 노드 1 부터 출발해서 다시 1로 돌아오는 경로 찾기

1. root 노드 1에서 인접한 자식 찾기(방문처리 +스택에 추가)

2. 5 노드를 스택에 추가하고 이어서 6번 노드 방문

3. 6번 노드를 스택에 추가하고 다음 경로가 없기 때문에 6번을 스택에서 제거

4. 다시 5번 노드로 되추적해서 연결된 다른 노드 7번 방문

   7번 노드에 연결된 다음 경로가 없기 때문에 7번은 스택에서 제거

   5번에 연결된 다른 노드가 없기 때문에 다시 루트노드로 되추적

5. 1번 노드에 연결된 다른 노드 2번으로 이동, 스택에 추가

6. 2번에 연결된 노드….를 반복

최종 경로 : 1→2→3→4→1

구현

• 주로 재귀 함수나 스택(stack)을 사용해 구현
  • 탐색 시작 노드를 스택에 삽입하고 방문처리
  • 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
    
  • 2번의 과정을 수행할 수 없을 때까지 반복
• 이미 방문한 노드에 대해서는 방문 처리를 해야한다. 그렇지 않으면 무한루프에 빠지게 된다.
• 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)를 사용.
  • 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 추가된 노드의 부모노드로 돌아와서(백트래킹-backtracking), 다른 자식 노드 탐색

의사 코드

void depth_first_tree_search (node v) {
	node u;
	visit v;
	for (each child u of v)//방문중인 노드의 자식 u에 대해
		depth_first_tree_search(u);//depth-fisrt-seach 적용
}

C++ 구현

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 그래프의 정점을 표현하는 구조체
struct Node {
    int data;
    vector<Node*> children;
    bool visited; // 방문 여부를 나타내는 변수

    // 생성자
    Node(int d) : data(d), visited(false) {}
};

// 깊이 우선 탐색 함수
void depth_first_search(Node* start) {
    stack<Node*> s;
    s.push(start);

    while (!s.empty()) {
        Node* current = s.top();
        s.pop();

        // 현재 노드를 방문
        if (!current->visited) {
            cout << "Visiting node: " << current->data << endl;
            current->visited = true;

            // 현재 노드의 자식들을 스택에 넣기
            for (Node* child : current->children) {
                s.push(child);
            }
        }
    }
}

int main() {
    // 그래프 생성
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    Node* node5 = new Node(5);

    // 그래프의 간선 설정
    node1->children.push_back(node2);
    node1->children.push_back(node3);
    node2->children.push_back(node4);
    node2->children.push_back(node5);

    // 깊이 우선 탐색 실행
    depth_first_search(node1);

    return 0;
}