TIL-074 | 그래프 탐색(1)-DFS

🌈 그래프 탐색

• 그래프 탐색이란, 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미한다.
• 그래프 탐색에는 BFS(Breadth-First Search), 다익스트라(Dijkstra), 플로이드 와샬(Floyd Washall)이 있다. 상황에 맞춰 적절한 탐색 기법을 사용한다.

깊이 우선 탐색(Depth-First Search, DFS)란?

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 방법이다

• 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.

• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.

• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

DFS의 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태이다.
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
• 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.
  • 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
• DFS에서 데이터를 찾을 때는 항상 "앞으로 찾아야 가야할 노드"와 "이미 방문한 노드"를 기준으로 데이터를 탐색한다.

DFS의 시간복잡도

• DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회한다.
  • 인접 리스트로 표현된 그래프: O(N+E)
  • 인접 행렬로 표현된 그래프: O(N^2)
• 즉, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

DFS의 구현

• DFS의 구현 방법으로는 기본적으로 "스택/큐"와 "재귀함수"를 통해 구현하는 방법이 있다.

# 리스트를 활용한 DFS 구현
def dfs(graph, start_node):
    # 아직 방문하지 않은 노드의 리스트와 이미 방문한 노드의 리스트 2개를 생성하는 것이 기본이다.
    need_visit, visited = list(), list()    
    need_visit.append(start_node)
    
    while need_visit:
        # 스택 구조를 활용       
        node = need_visit.pop()
        
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

• 간편한 구현방법이긴 하나, list에서 pop을 사용하면 성능이 떨어진다.

# 재귀함수를 이용한 DFS 구현
def recursive_dfs(graph, start, visited = [])
    visited.append(start)
    
    for node in graph[start]:
        if node not in visited:
            recursive_dfs(graph, node, visited)

    return visited

• 재귀함수를 이용한 DFS 구현 예시이며, visited 자료형을 기본 함수 인자로 포함시키고, 방문한 리스트들을 재귀함수를 통해서 계속 visited에 담는 방식이다.

📝 Reference

1. https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
2. https://data-marketing-bk.tistory.com/44
3. https://www.fun-coding.org/Chapter18-dfs-live.html