About DFS

DFS(깊이 우선 탐색)

BFS 와 마찬가지로 대표적인 그래프 탐색 알고리즘이다.

• BFS: 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식
• DFS: 정점의 자식 노드들을 먼저 탐색하는 방식

그래프의 표현 방법

HashMap 또는 Array 를 이용해서 그래프를 주로 표현함.

HashMap 은 키(key)와 값(value) 를 저장하는 자료구조로, 내부에서 해쉬 함수 를 통해 키 에 대한 값 을 빠르게 검색할 수 있다.

DFS 알고리즘의 구현

• HashMap: 각 노드(키)마다 연결된 노드를 배열(값)로 저장
• needVisit stack: 방문해야하는(각 노드에 연결된) 노드들을 스택 으로 저장
• visited queue: 이미 방문한 노드들을 큐로 저장

BFS 와 DFS 알고리즘 구현의 차이점은,

방문할 필요가 있는 노드들을 저장하는 자료구조를

• BFS는 큐
• DFS는 스택
  에 저장한다는 것이다.

알고리즘 순서

1. 처음 방문하는 노드를 needVisit stack에 넣은 채로 초기화한다.
2. needVist stack이 비어있지 않으면 stack에서 노드 하나를 뽑는다.
3. 뽑은 노드가 이미 방문된 노드가 아니면(visited queue에 없으면) visited queue에 넣는다.
4. 뽑은 노드와 연결된 노드들을 needVisit stack에 추가한다.
5. 다시 2번으로.

예제 코드

class DFS:
    def __init__(self):
        self.hashMap = {
            'a': ['b', 'c'],
            'b': ['a', 'd'],
            'c': ['a', 'g', 'h', 'i'],
            'd': ['b', 'e', 'f'],
            'e': ['d'],
            'f': ['d'],
            'g': ['c'],
            'h': ['c'],
            'i': ['c', 'j'],
            'j': ['i'],
            }
        self.visited = [] #queue
        self.needVisit = [] #stack

    def dfs_search(self, start_node):
        self.needVisit.append(start_node)

        while not len(self.needVisit) == 0:
            need_visit = self.needVisit.pop()
            if not need_visit in self.visited:
                self.visited.append(need_visit)
                self.needVisit.extend(self.hashMap[need_visit])
        print(self.visited)

dfs = DFS()
dfs.dfs_search('a')

시간 복잡도

일반적인 DFS의 시간 복잡도는 다음에 의존한다.

• 노드의 수: V
• 간선의 수: E 위의 구현에서 while 문은 V+E 만큼 수행된다.

따라서 시간 복잡도는 O(V + E)가 된다.
(BFS와 동일하다.)