BFS(너비 우선 탐색)

• 스택을 이용하는 DFS와 달리 BFS는 반복 구조를 구현할 때 큐를 사용한다.
• 재귀로 구현 불가
  • 큐를 이용하는 반복구현만 가능하다.

출처: 패스트캠퍼스

---

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'G', 'H', 'I'],
    'D': ['B', 'E', 'F'],
    'E': ['D'],
    'F': ['D'],
    'G': ['C'],
    'H': ['C'],
    'I': ['C', 'J'],
    'J': ['I']
}

BFS 구현(큐 2개 사용)

	
    visited = deque()
    need_visited = deque()
    need_visited.append(list(graph.keys())[0])

• 첫번째 키 값인 'A'를 먼저 방문이 필요한 큐에 넣어준다.

    while need_visited:
        node = need_visited.popleft()
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])

• 방문이 필요한 노드에서 값을 꺼내준다.
• 노드가 방문하지 않았다면 방문 큐에 값을 넣어주고
• 그래프[노드] 의 요소들을 다시 방문이 필요한 큐(need_visitied)에 추가해준다.

진행

node = 'A'

need_visited = ['A'] / visited = []

'A' not in visited

visited = ['A'] -> graph['A'] = ['B', 'C'] -> need_visited = ['B','C']

--------------------

node = need_visited.popleft() => 'B'

need_visited = ['C'] / visited = ['A']

'B' not in visited

visited = ['A', 'B'] -> graph['B'] = ['A', 'D'] -> need_visited = ['C','A','D']

 

시간 복잡도

• 일반적인 BFS 시간 복잡도
  • 노드 수 : V
  • 간선 수 : E
    • 위 코드에서 V+E번 만큼 수행함
  • 시간 복잡도 : O(V+E)

---

BFS(큐 1개 이용)

• 큐를 굳이 2개를 이용하지 않아도 될 것 같다. 2개 사용 시 공간복잡도가 증가 
• visited 큐를 하나만 두고 코드를 고쳐본다.

def bfs_queue(start):
    visited = [start]
    q = deque([start])
    while q:
        node = q.popleft()
        for adj in graph[node]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)
    return visited