DFS(Depth-First Search)

📖Graph

📖DFS(Depth-First Search)

시작 노드에서 시작해서 branch(다음 분기)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 그래프 순회 방법

📖특징

• 재귀적으로 동작
• 그래프에 cycle이 있는지 파악 가능
• 현재 순회 중인 노드만 저장하는 stack을 사용하므로 메모리 공간의 낭비가 적음

📖과정

1. 시작 노드를 방문해 스택에 삽입하고 방문 처리
2. 스택의 top에 위치하는 노드에 방문하지 않은 인접 노드 정보를 전부 스택에 삽입하고 방문 처리
3. 방문하지 않은 인접 노드가 없다면 스택의 top을 pop
4. 2,3 번의 과정을 더 이상 수행할 수 없을 때(스택에 노드가 하나도 없을 때)까지 반복

📖구현

📎재귀

from collections import deque
 
visited = []
 
def dfs(graph, node, visited):
    visited.append(node)
    
    for adj in graph[node]:
        if adj not in visited:
            dfs(graph, i, visited)

• visited에 탐색 순서대로 노드가 들어감

📎Stack

def dfs(graph, node):
    stack = [node]
    visited = []
    
    while stack:
        v = stack.pop()
        visited.append(v)
        
        for adj in graph[v]:
            if adj not in visited:
                stack.append(i)

• visited에 탐색 순서대로 노드가 들어감

📖시간 복잡도

그래프 구현 방법	시간복잡도
인접 행렬	O(n²)
인접 리스트	O(n+e)

📖BFS & DFS