DFS : 깊이 우선 탐색 (Depth First Search) | Python 구현

BFS : 너비 우선 탐색 / 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. (같은 레벨의 노드들 먼저 탐색)

DFS : 깊이 우선 탐색 / 정점의 자식들의 방향으로 모든 정점들을 우선 방문하는 방법이다. (아래로 탐색)

 

DFS

장점 :

    현 경로상의 노드들만 기억하면 되므로 저장공간의 수요가 비교적 적다. 

    목표노드가 깊은 단계에 있을 경우 빨리 해를 구할 수 있다.

 

단점 : 

    해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 미리 지정한 임의의 깊이 까지만 탐색하고 목표 노드를 찾지 못한다면 다음 경로를 탐색하는 것이 유용하다. (백트레킹)

    얻어진 해가 최단 경로가 된다는 보장이 없다. 깊이 우선 탐색은 해에 다다르면 탐색을 종료하므로, 얻어진 해는 최적이 아닐 수도 있다.

 

 

Python으로 DFS 그래프를 표현해보자.

1. 딕셔너리를 통해 그래프 표현

graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

 

2. 리스트 자료구조를 활용하여 dfs 구현

# 스택/큐 활용 - list 
def dfs(graph, start_node):
    need_visited, visited = list(), list()

    # 시작 노드 지정
    need_visited.append(start_node)

    # 만약 방문이 필요한 노드가 있다면
    while need_visited:
        # 그 중에서 가장 마지막 데이터 추출 (스택 구조 활용을 위해)
        node = need_visited.pop()

        # 만약 그 노드가 방문한 목록에 없다면
        if node not in visited:
            # 방문한 목록에 추가하기
            visited.append(node)

            # 해당 노드에 연결된 노드를 제거 - visited에 추가했으므로
            need_visited.extend(graph[node])

    return visited

need_visited : 아직 방문하지 않은 노드들을 저장하는 스택의 역할

visited : 방문한 노드들을 저장하는 스택의 역할

 

 

 

결과 코드

# 딕셔너리 정의 (노드 구조)
graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

# 스택/큐 활용 - list 
def dfs(graph, start_node):
    need_visited, visited = list(), list()

    # 시작 노드 지정
    need_visited.append(start_node)

    # 만약 방문이 필요한 노드가 있다면
    while need_visited:
        # 그 중에서 가장 마지막 데이터 추출 (스택 구조 활용을 위해)
        node = need_visited.pop()

        # 만약 그 노드가 방문한 목록에 없다면
        if node not in visited:
            # 방문한 목록에 추가하기
            visited.append(node)

            # 해당 노드에 연결된 노드를 제거
            need_visited.extend(graph[node])

    return visited

print(dfs(graph, 'A'))

어떤 자식을 먼저 탐색하는지는 상관없다.