CS 기초/자료구조 및 알고리즘
[자료구조 및 알고리즘] 너비우선탐색(BFS)
땅어
2020. 10. 27. 17:16
728x90
300x250
BFS(너비우선탐색)는 DFS와 함께 그래프를 탐색하는 알고리즘 중 하나이다. BFS는 큐로 구현할 수 있다. BFS는 최단거리를 찾는데 많이 이용된다.
BFS는 다음과 같은 알고리즘으로 작동한다.
- 큐에서 하나의 노드를 꺼낸다.
- 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 큐에 삽입한다.
아래와 같은 그래프가 있을 때, 이를 BFS로 탐색한다고 해보자. 노드를 방문할 때 해주어야 할 것이 두가지가 있는데 하나는 방문처리를 하는 것(그래프에선 빨강색으로 표시)이고 또 다른 하나는 큐에 넣어주는 것이다.
시작노드 1번을 큐에 넣고 방문처리한다.
큐에서 노드 1을 뺀다.(뺀 노드는 위쪽에 표시하였다.) 1과 연결된 노드 중 아직 방문하지 않은 2,3 노드를 큐에 넣고 방문처리한다.
큐에서 2를 빼고 2와 연결된 노드 중 3은 이미 방문했으니 4,5를 큐에 넣는다.
큐에서 3을 빼고 3과 연결된 노드 중 방문하지 않은 노드인 6,7을 큐에 넣는다.
이후, 4,5,6,7이 큐에서 차례로 빠진다.
이 같이 BFS로 탐색하면 최종적으로 방문순서는 1->2->3->4->5->6->7
이를 파이썬 코드로 구현하면 아래와 같다.
visit = [False for _ in range(8)]
a = [[] for _ in range(8)]
def bfs(start):
q = []
q.append(start)
visit[start] = True
while q:
x = q.pop(0) # 0번째 원소를 return하고 제거
print(x)
for i in a[x]:
y = i
if not visit[y]:
q.append(y)
visit[y] = True
# 연결리스트 구현
connection = [(1,2),(1,3),(2,3),(2,4),(2,5),(4,5),(3,6),(3,7),(6,7)]
for i,j in connection:
a[i].append(j)
a[j].append(i)
bfs(1)
참고
728x90
300x250