너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS) 정리

👩‍💻 너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS) 정리 with Python

🥘 너비 우선 탐색 (Breadth-First-Search)

Node 같은 레벨에 있는 Node들 (형제 Node들)을 먼저 탐색하는 방식입니다.

 

 

파이썬을 이용한 그래프 표현 코드

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']

 

 

너비 우선 탐색 (Breadth-First-Search) 알고리즘 구현

def BFS(graph, startNode):
    visited,needVisited = list(),list()

    needVisited.append(startNode)

    while needVisited:
        node = needVisited.pop(0)
        if node not in visited:
            visited.append(node)
            needVisited.extend(graph[node])
    return visited

자료구조 Queue를 활용하여서

visited와 needVisited 두 개의 Queue를 생성하여서 알고리즘 구현하게 됩니다.

Queue의 규현은 간단히 파이썬 리스트를 활용합니다.

 

 

코드 실행 결과

 

🍳 깊이 우선 탐색 (Depth-First-Search)

Node의 Child들을 먼저 탐색하는 방식입니다.

 

 

깊이 우선 탐색 (Depth-First-Search) 알고리즘 구현 

def BFS(graph, startNode):
    visited,needVisited = list(),list()

    needVisited.append(startNode)

    while needVisited:
        node = needVisited.pop()
        if node not in visited:
            visited.append(node)
            needVisited.extend(graph[node])
    return visited

자료구조 Stack과 Queue를 활용하게 됩니다.

needVisited Stack과 visited Queue, 두 개의 자료구조를 생성하여 알고리즘을 구현하게 됩니다.

Queue와 Stack은 간단히 파이썬 리스트를 활용하였습니다.

 

 

코드 실행 결과

 

 

BFS 자료구조는 두 개의 Queue를 활용하는데 반해,

DFS는 Stack과 Queue를 활용한다는 차이가 있음을 확인합시다!

 

🍪 시간 복잡도

 

일반적인 DFS 시간 복잡도

• 노드 수: V
• 간선 수: E
  • 위 코드에서 while need_visit 은 V + E 번 만큼 수행하게 됩니다.
• 시간 복잡도: O(V + E)

 

일반적인 BFS 시간 복잡도

• 노드 수: V
• 간선 수: E
  • 위 코드에서 while need_visit 은 V + E 번 만큼 수행하게 됩니다.
• 시간 복잡도: O(V + E)