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))
장점 : 메모리를 효율적으로 사용.
단점 : 두 노드의 연결 여부에 대한 확인은 느림.
동작과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 하고 방문 처리를 한다.
- (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)
Author And Source
이 문제에 관하여(BFS 기본.), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BFS-기본저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)