BFS & DFS

HyeonWoo·2021년 1월 4일
0

알고리즘

목록 보기
2/5
post-thumbnail

BFS

  • 너비 우선 탐색이라 하며 BFS(Breadth-First Search)라 부름.

  • 루트 노드 혹은 임의의 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법.

  • 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

  • 즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다.

  • 큐를 사용한다. (해당 노드의 주변부터 탐색해야 하기 때문이다.)

  • 최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합하다.

code


# 딕셔너리 타입인 graph와 시작 노드를 인자로 받는다.

def bfs(graph, start_node):

    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
    	# BFS는 큐를 사용하기 때문에 pop(0)을 사용.(FIFO)
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
     
     return visited

DFS

  • 깊이 우선 탐색이며 DFS(Depth-First Search)라고 부른다.

  • 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다.

  • 넓게 탐색하기 전에 깊게 탐색하는 것이다.

  • 예를 들어, 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

  • 스택이나 재귀함수를 통해 구현한다.

  • 모든 경로를 방문해야 할 경우 사용에 적합하다.


def dfs(graph, start_node):

    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
    	# DFS는 스택을 사용하기 때문에 pop()을 사용.(FILO)
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
     
     return visited

참고자료

profile
학습 정리, 자기 개발을 위한 블로그

0개의 댓글