TIL #14 : BFS & DFS

📝 BFS

너비 우선 탐색 : 정점과 같은 레벨에 있는 형제 노드들 먼저 탐색

BFS는 루트노드(or 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

• 두 개의 큐로 구현 가능
  • visited_node : 방문한 노드
  • to be visited node : 방문할 노드
• 👏 시간 복잡도 : O(V+E)

def BFS(graph, start):
    visited_node = list()
    to_be_visited_node = list()

    to_be_visited_node.append(start)

    while to_be_visited_node:
        node = to_be_visited_node.pop(0)
        if node not in visited_node:
            visited_node.append(node)
            to_be_visited_node.extend(graph[node])

    return visited_node

📝 DFS

깊이 우선 탐색 : 정점의 자식 노드를 먼저 탐색

DFS는 루트노드(or 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법으로 미로 탐색을 예로 들면, 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림림길로 돌아와 다른 방향으로 탐색을 진행하는 방법과 유사하다.

• 한 개의 스택과 한 개의 큐로 구현 가능
  • 스택 ➜ to be visited node : 방문할 노드
  • 큐 ➜ visited_node : 방문한 노드
• 👏 시간 복잡도 : O(V+E)

def DFS(graph, start):
    visited_node = list()
    to_be_visited_node = list()

    to_be_visited_node.append(start)

    while to_be_visited_node:
        node = to_be_visited_node.pop()
        if node not in visited_node:
            visited_node.append(node)
            to_be_visited_node.extend(graph[node])

    return visited_node

❗❗ 파이썬으로 구현한 BFS와 DFS에서 다른 점은 while 구문 안에서 방문할 노드를 가져오는 부분 뿐이다.

• BFS : 큐 ➜ .pop(0) : FIFO
• DES : 스택 ➜ .pop() : LIFO