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

그래프 & 인접 행렬 & 인접리스트

https://devnuts.tistory.com/69?category=1003685 

인접행렬과 인접리스트

 

DFS

그래프 탐색의 한 종류로, 트리 순회의 방식입니다. 루트 노드나 임의의 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색한 후,

돌아와 다른 노드로 탐색하는 방식입니다.

 

👇 내가 DFS가 헷갈렸던 이유

---

 

dfs 는 그래프 탐색 알고리즘이고,

트리 또는 그래프 둘 다 탐색하기 위한 알고리즘입니다.

깊이라고 생각을해서, 계속 트리 구조로 생각을 한 상태에서 문제에 접근하니깐 depth 끝이라는 개념이 모호했던 거 같습니다.

 

그래프 탐색이란?

- 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

---

 

 

아래 와같은 순서로 정점 순회를 하게 됩니다.

그래프 구조로 되어있는 그림을  가지고 온 이유는, 제가 헷갈렸던 부분 때문에 이런식으로 처음부터 받아들이는 게 개념 잡기가 좋아서 이 그림을 선택했습니다.

다시 말해, DFS는 트리 순회처럼 움직여, 트리 구조로 그려서 볼 수 있지만, 그래프 탐색 알고리즘입니다.

 

 

DFS 특징

• DFS는 일반적으로 스택이나 재귀호출을 통해 구현합니다. (재귀호출을 통한 메서드 스택)
• 리프노드를 한 번에 잘라내기 용이하여 백트래킹 알고리즘에 자주 사용됩니다.
• 어떤 노드를 방문 했었는지, 여부를 반드시 검사 해야 합니다 (무한루프 에 빠질 위험이 많음)
• 트리 순회(전위, 중위, 후위 순회)는 모두 DFS 의 한 종류입니다.

 

DFS 장단점

장점

• 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적음 
• 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음
• 구현이 너비 우선 탐색(BFS) 보다 간단함

단점

• 찾아낸 목표가 최단거리의 최적해가 아닐 수 있습니다.
• 일반적으로 BFS보다 속도가 느립니다.
• 해가 없는 경로로 깊이 먼저 탐색 할 경우 최악의 탐색 성능이 나올 수 있습니다.
• 스택으로 구현시 구현시 스택오버플로우에 유의해야합니다.

 

DFS 와 BFS 차이

DFS

한 루트로 탐색하다가, 특정 상황에서 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식.

대표적으로 백트래킹에 사용됩니다.

일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 합니다.

모든 경우의 수를 고려해야하는 문제라면 BFS보단, DFS로 구현하는 게 좋습니다.

그 이유는 BFS 로 구현하면 큐가 커지게 됩니다.

그리고 스택으로 구현합니다.

 

사용되는 문제 유형

• 몇 개 중에 몇 개를 뽑는 조합류
• 목적지에 도달할 수 있는 지 여부
• 경로의 특징을 저장해둬야 하는 문제
• 검색 대상 그래프가 정말 큰 경우
• 한 가지 정점과 연결된 모든 정점을 탐색하는 경우

BFS

DFS와 큰차이로, 여러 갈래 중 무한한 길이를 가지는 경로가 존재하고, 탐색 목표가 다른 경로에 존재하는 경우, DFS로 탐색할 시에는 무한한 길이의 경로에서 영원히 종료되지 못하지만, BFS의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다는 게 특징입니다.

그리고 큐로 구현합니다.

 

사용되는 문제 유형

• 최단거리(최단경로)
• 가중치가 같고 최소비용(최소횟수)
• 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀디 않은 경우

 

https://namu.wiki/w/BFS

 

DFS 구현 방식

DFS 를 구현 방법은 두 가지가 있습니다.

• Recursive DFS - 순환 호출 이용 (재귀)
• Iterative DFS - 명시적 스택 사용

 

Recursive DFS

Input : 그래프 G, G의 정점 v

Output : v로 부터 탐색 가능한 모든 정점들

procedure DFS(G, v) is
    label v as discovered // 현재 정점 v를 탐색 완료 되었다는 표시 (중복 방문 방지를 위함)
    
    // 그래프 G의 모든 인접한 간선 (v, w)에 대해서
    for all directed edges from v to w that are in G.adjacentEdges(v) do
    
    	// 만약 w가 탐색되지 않았다면?
        if vertex w is not labeled as discovered then 
            recursively call DFS(G, w) // 재귀적으로 w를 탐색
           
//        -> 현재 정점 v의 인접 정점 w를 매개변수로 하여, 같은 서브루틴으로 다음 정점을 탐색

최악의 복잡도는 O(|V|) 입니다.

현재 탐색하고 있는 경로의 정점들과 이미 방문한 정점들의 스택을 저장하고 있기 때문입니다.

 

 

Iterative DFS

Input : 그래프 G, G의 정점 v

Output : v로 부터 탐색 가능한 모든 정점들

procedure DFS-iterative(G, v) is
    let S be a stack // S라는 스택을 하나 생성.  현재 방문 정점의 인접 정점들을 담는 용도
    S.push(v) // 탐색하고자 하는 시작 정점 v를 스택에 pus
    
    // 스택이 빈 공간이 아닐 때까지 아래의 반복문 구현을 반복합니다.
    while S is not empty do
        v = S.pop() // 현재 탐색하고 있는 정점을 v에 넣습니다.
        
        // 만약 v가 탐색되지 않았다면,
        if v is not labeled as discovered then 
            label v as discovered // 탐색 완료 표시를 합니다.
           
            for all edges from v to w in G.adjacentEdges(v) do // 현재 정점 v의 모든 인접한 정점 w를
                S.push(w) // w(인접 정점)을 스택에 push 합니다.

최악의 복잡도는 O(|E|) 입니다.

재귀적인 방법과 달리, 어떤 해당 정점에서 인접 정점들의 정보를 모두 스택에 저장하기 때문에,

최악의 설정으로 하나의 정점이 다른 모든 정점과 직접 연결되어 있을 시 최악의 복잡도가 됩니다.

 

 

두 가지 접근의 차이점

위에서 살펴 본 두 가지 DFS의 탐색 방법은 각 정점들의 이웃 방문 순서가 서로 반대입니다.
재귀적인 방법에서는 인접리스트 방식에서 정점 v의 첫 번째 이웃을 먼저 방문하는 반면,
스택을 이용하는 방법은 정점 v의 이웃들이 stack에 역순으로 저장되기 때문에 인접 리스트 관점에서 정점 v의 첫 번째 이웃은 제일 마지막(First In last out)에 탐색이 된다.

위 그래프를 예로 들면,

재귀적인 방법으로 방문순서는 A, B, D, F, E, C, G 이 되고,

스택을 이용한 반복적 접근은 A, E, F, B, D, C, G 입니다.

 

 

DFS 시간 복잡도

정점의 수가 n 개이고, 간선의 수가 e인 그래프의 경우

• 그래프가 인접 리스트로 표현된 경우 O(n+e)
• 그래프가 인접 행렬로 표현된 경우 O(n²)

희소 그래프인 경우 인접리스트의 사용이 인접 행렬보다 유리합니다.

(희소 그래프는 그래프 내에 적은 수의 간선을 가지는 그래프로 인접 행렬을 사용하면, 메모리 낭비가 크기 때문입니다)

 

 

 

참고

https://lemidia.github.io/algorithm/DFS-Implementation-stack/

깊이우선탐색(DFS) 구현 - Iterative using stack