깊게만 파면 아쉬우니까 옆으로, 그래프 순회 - 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함수이다. 핵심은 큐에 저장한 노드 값을 선입선출하기 때문에, 새로 획득한 정점보다 방문한 값에 직접 연결된 점들을 먼저 순회한다. 따라서 얕고 넓은 탐색이 우선적으로 이루어진다.

실행순서표

마무리

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