DFS(깊이 우선 탐색)

그래프 탐색

■ 하나의 정점으로부터 시작해서 차례대로 모든 정점들을 한 번씩 방문하는 탐색 과정

EX) 특정 도시에서 다른 도시로 갈 수 있는 지 없는 지에 대한 탐색 과정

 

DFS(깊이 우선 탐색)

■ root node나 다른 임의의 노드에서 시작하여 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방법

■ 넓게 탐색하기전에 깊게 탐색하는 것

■ DFS가 BFS보다 좀 더 간단함

 

DFS(깊이 우선 탐색)의 특징

■ 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

■ 그래프 탐색의 경우 어떤 노드를 방문했었는 지 여부를 반드시 검사해야 한다.

■ DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 한다.

   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

# 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)

# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현 초기에는 false로 초기화
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)


# 결과 1 2 7 6 8 3 4 5