DFS(Depth-First Search)

 

 

 

 

DFS 깊이우선탐색

 - 스택 또는 재귀함수 이용

 - 작은 것부터 탐색

 - 시작노드 1일 경우

 

1 방문처리 / 방문 1

1의 인접노드 2 3 8 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2

2의 인접노드 1 7 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7

7의 인접노드 2 6 8 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 6

6의 인접노드 7 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 6

7의 인접노드 2 6 8 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 6 8

8의 인접노드 1 7 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 6 8

1의 인접노드 2 3 8 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 6 8 3

3의 인접노드 1 4 5 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 6 8 3 4

4의 인접노드 3 5 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 6 8 3 4 5

5의 인접노드 3 4 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 6 8 3 4 5

# DFS 구현
graph = [
    [],         # index 0은 미사용
    [2, 3, 8],  # 1번 노드와 인접한 노드
    [1, 7],     # 2번 노드와 인접한 노드
    [1, 4, 5],  # 3번 노드와 인접한 노드
    [3, 5],     # 4번 노드와 인접한 노드
    [3, 4],     # 5번 노드와 인접한 노드
    [7],        # 6번 노드와 인접한 노드
    [2, 6, 8],  # 7번 노드와 인접한 노드
    [1, 7]      # 8번 노드와 인접한 노드
]

# 해당 노드 방문여부 체크하는 리스트, index 0은 사용하지 않기 위해 9칸 생성
visited = [False] * 9

# 시작노드
n = 1

def DFS(graph, n, visited):
    # 해당 노드 방문으로 처리
    visited[n] = True
    print(n, end=' ')
    # 인접한 노드중에서 방문하지 않은 노드가 있다면 방문
    for i in graph[n]:
        if visited[i] == False:
            DFS(graph, i, visited)

DFS(graph, n, visited)

1 2 7 6 8 3 4 5

 

 

 

출처

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3