BFS(Breadth-First Search)

 

 

 

 

BFS 너비우선탐색

 - 가까운 노트부터 먼저 탐색하는 알고리즘

 - queue 사용

 - 시작노드 1일 경우

큐에 1 삽입 / 현재 큐 1 / 방문 1

1을 꺼내서 인접노드 2 3 8 중 방문하지 않은 노드는 큐에 삽입하고 방문처리 / 현재 큐 2 3 8 / 방문 1 2 3 8

2를 꺼내서 인접노드 1 7 중 방문하지 않은 노드는 큐에 삽입하고 방문처리 / 현재 큐 3 8 7 / 방문 1 2 3 7 8

3을 꺼내서 인접노드 1 4 5 중 방문하지 않은 노드는 큐에 삽입하고 방문처리 / 현재 큐 8 7 4 5 / 방문 1 2 3 4 5 7 8

8을 꺼내서 인접노드 1 7 중 방문하지 않은 노드는 큐에 삽입하고 방문처리 / 현재 큐 7 4 5 / 방문 1 2 3 4 5 7 8

7을 꺼내서 인접노드 2 6 중 방문하지 않은 노드는 큐에 삽입하고 방문처리 / 현재 큐 4 5 6 / 방문 1 2 3 4 5 6 7 8

4를 꺼내서 인접노드 3 5 중 방문하지 않은 노드는 큐에 삽입하고 방문처리 / 현재 큐 5 6 / 방문 1 2 3 4 5 6 7 8

5를 꺼내서 인접노드 3 4 중 방문하지 않은 노드는 큐에 삽입하고 방문처리 / 현재 큐 6 / 방문 1 2 3 4 5 6 7 8

6을 꺼내서 인접노드 7 중 방문하지 않은 노드는 큐에 삽입하고 방문처리 / 현재 큐 null / 방문 1 2 3 4 5 6 7 8

from collections import deque

# BFS 구현
graph = [
    [],         # index 0은 미사용
    [2, 3, 8],  # 1번 노드와 인접한 노드
    [1, 7],     # 2번 노드와 인접한 노드
    [1, 4, 5],  # 3번 노드와 인접한 노드
    [3, 5],     # 4번 노드와 인접한 노드
    [3, 4],     # 5번 노드와 인접한 노드
    [7],        # 6번 노드와 인접한 노드
    [2, 6, 8],  # 7번 노드와 인접한 노드
    [1, 7]      # 8번 노드와 인접한 노드
]

# 해당 노드 방문여부 체크하는 리스트, index 0은 사용하지 않기 위해 9칸 생성
visited = [False] * 9

# 시작노드
n = 1

def BFS(graph, n, visited):
    # deque 라이브러리로 queue 구현
    queue = deque([n])
    visited[n] = True
    # 큐가 빌때까지 반복
    while queue:
        # 큐에서 하나씩 뽑아 출력
        temp = queue.popleft()
        print(temp, end=' ')
        # 인접한 노드중에 방문하지 않은 노드를 큐에 삽입하고 방문처리
        for i in graph[temp]:
            if visited[i] == False:
                queue.append(i)
                visited[i] = True

BFS(graph, n, visited)

1 2 3 8 7 4 5 6

 

 

 

 

출처

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3