BFS 와 DFS 개념

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

홍익대 프로그래밍 경진 대회문제를 푸는데, 재귀로 풀었더니 자꾸 recursion 에러 나서 아예 스택, 큐 구현의 중요성을 느껴 다시 공부한다.

1. BFS 와 DFS란?

• 대표적인 그래프 탐색 알고리즘
  • 너비 우선 탐색: 정점들과 같은 레벨에 있는 노드들( 형제 노드들)을 먼저 탐색하는 방식
  • 깊이 우선 탐색: 정점들의 자식을 먼저 탐색하는 알고리즘

BFS/DFS 방식을 이해하기 위한 예제

• BFS 방식 = A - B - C - D - G - H - I - E - F - J
  • 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들( 형제 노드들 )을 먼저 순회함
• DFS 방식 = A - B - D - E - F - C - G - H - I - J
  • 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회함.

---

2. 파이썬으로 그래프를 표현하는 방법 : BFS

• 파이썬에서 제공하는 딕셔너리와 리스트 자료구조를 활용해서 그래프를 표현할 수 있다.

# 그래프 딕셔너리로 포현하기
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']

---

3. BFS 알고리즘 구현 :BFS

• 자료구조 큐를 사용함.
  • need_visit 큐와 visited 큐 두 개의 큐를 생성
    • need_visit: 방문해야할 노드들
    • visited: 방문 한 노드들

---

큐의 구현은 간단히 파이썬 리스트 활용

def bfs(graph, start_node):
    visited = list()
    need_visit=list()

    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
               need_visit.extend(graph[node])# 리스트를 붙일 수 있다.
    return visited

---

bfs(graph,'A')

---

 

---

---

---

3. DFS 알고리즘 구현

• 자료구조 스택과 큐를 활용함
  • need_visit 스택과 visited 큐, 두 개의 자료 구조를 생성

    BFS 자료구조는 두 개의 큐를 활용하는데 반해, DFS 는 스택과 큐를 활용한다는 차이가 있음을 인지해야한다.

def dfs(graph, start_node):
    visited = list()
    need_visit=list()

    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
               need_visit.extend(graph[node])# 리스트를 붙일 수 있다.
    return visited

4. 시간 복잡도:BFS

• 일반적인 BFS 시간 복잡도

  • 노드 수 : V

  • 간선 수: E

    • 위 코드에서 while need_visit 은 V+E 번만큼 수행함.

  • 시간복잡도 O(V+E)