BFS 기본.

BFS 구현을 위한 자료구조.

큐

오버플로 : 자료구조에 데이터의 크기까지 가득 찬 상태에서 삽입연산을 수행할 때 발생.
언더플로 : 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생.

큐란?
선입선출(Fist In First Out)구조라 한다.

_collections 에서 deque를 임포트해서 사용
append()메소드로 자료구조에 추가한다.
popleft()메소드로 자료구조에서 데이터를 뽑아낸다.

• 그리고 deque의 초기화 하는 경우에 리스트를 넣어줘야 한다.

from _collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)
queue.reverse()
print(queue)

BFS

• 너비 우선 탐색 (그래프에서 현재 노드와 가까운 노드부터 탐색하는 것)

노드의 연결 관계를 인접 행렬 또는 리스트로 나타낸 후 BFS를 수행한다.

인접 행렬 : 2차원 배열에 그래프의 연결 관계를 표현.(모든 노드에서의 연결관계를 표시한다.)

INF = 999999999
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

장점 : 두 노드의 연결 여부에 대한 확인이 빠름.
단점 :메모리가 불필요하게 낭비됨.(모든 노드의 연결관계를 나타내기 때문에)

인접 리스트 : 연결된 노드에 대한 정보만 리스트에 append()하는 것.

graph = [[] for _ in range(3)]

graph[0].append((1, 7))
graph[0].append((2, 5))

graph[1].append((0, 7))

graph[2].append((0, 5))

장점 : 메모리를 효율적으로 사용.
단점 : 두 노드의 연결 여부에 대한 확인은 느림.

동작과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 하고 방문 처리를 한다.
3. (2.)의 과정을 반복.

from _collections import deque

def BFS(graph, start, visit):
    #동작과정1 : 탐색 시작 노드를 큐에 삽입 하고 방문 처리.
    q = deque([start])
    visit[start] = True

    while q:
        # 2. 큐에서 노드를 꺼내 
        node = q.popleft()
        print(node, end=" ")
        for next_node in graph[node]:
            # 2. 방문 하지 않은 노드를 방문 처리 하고 큐에 추가.
            if not visit[next_node]:
                q.append(next_node)
                visit[next_node] = True

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [5, 6],
    [3, 4],
]
visit = [False] * 6
BFS(graph, 1, visit)