DFS

DFS란?

깊이 우선 탐색( Depth-First Search ) : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.

방문 처리,  스택, 재귀 함수 이용

스택 : https://jun2ee22.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D
그래프 자료구조 url

 

tip.1차원 배열이나 2차원 배열을 그래프 형태로 생각하면 수월함.

---

방문하지 않은 인접 노드가 없을 때까지 스택에 하나씩 삽입(방문 처리)
-> 스택의 최상단 노드에 인접 노드가 없으면 스택에서 pop()

더 이상 수행할 수 없을 때까지 반복

방문 순서: 1 -> 2 -> (2) -> 4 -> 3 -> 5 -> (5) -> (3) -> (4) -> (1)

---

ex) DFS

#DFS 함수 정의
def dfs(graph, v, visited):
    
    visited[v] = True
    print(v, end=' ')
    
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            
graph = [
    [],
    [2, 4],
    [1],
    [4, 5],
    [1, 3, 5],
    [3, 4]
]

visited = [False] * 6

dfs(graph, 1, visited)

---

이것이 코딩 테스트다 - 나동빈

정리하긔