깊게만 파면 아쉬우니까 옆으로, 그래프 순회 - 2. BFS

그래프 순회 - 1. DFS에서 이어집니다.

그래프 순회 방식의 다양화

그래프 순회 방식인 DFS와 BFS는 모든 정점을 순회하여, 원하는 결과값을 얻는 다는 아이디어는 유사하지만, 상황에 따라 다른 효율을 보이기 때문에 둘 다 능숙히 사용하는 것이 좋다.

- 그래프의 모든 정점을 방문해야하는 문제

모든 정점을 방문하는 것이 목적인 경우 DFS, BFS 두 방식 모드 좋다.

• 그래프의 크기가 크다면 DFS
• 시작 정점으로부터 하위노드가 멀지 않으면 BFS
  
  

- 경로의 특징을 저장해둬야 하는 문제

• 각각의 경로마다 특징을 저장해둬야 할 때는 DFS
  
  

- 최단거리 구해야 하는 문제

• 미로 찾기 등 최단거리를 구해야 할 경우, BFS
  
  

BFS의 구현

지금부터는 BFS 방식 알고리즘을 파이썬 함수로 구현할 것이다. 구현 방식은 큐를 이용한 반복구조이다.

큐를 이용한 반복구조의 BFS함수

# 함수 선언
def bfs_queue(start) :
    #시작점 visited에 저장
    visited = [start]
    # 큐에 start 값 저장
    q = deque([start])
    
    # 큐에 원소가 있으면
    while q :
        # 큐에서 요소 하나 꺼내기
        node = q. popleft()
        
		# 노드 값을 키 값으로 그래프에서 리스트 호출, 해당 리스트의 요소 하나씩 순회
        for adj in graph[node]:
            # 만약 adj가 방문한 적 없는 정점이라면
            if adj not in visited:
                # 해당 adj를 큐와 visited에 추가
                q.append(adj)
                visited.append(adj)
    # visited 값 반환
    return visited

큐구조를 활용한 BFS함수이다. 핵심은 큐에 저장한 노드 값을 선입선출하기 때문에, 새로 획득한 정점보다 방문한 값에 직접 연결된 점들을 먼저 순회한다. 따라서 얕고 넓은 탐색이 우선적으로 이루어진다.

실행순서표

---

마무리

그래프 탐색보다 어려운 건 사실 데이터 그래프로 만들기..