BFS 알고리즘 구현
대기열 데이터 구조 활용
- need_visit 대기열
- 방문한 큐
개념
위 그래프에 BFS를 구현하면 다음과 같은 순서로 진행된다.
1. 먼저 노드 A가 need_visit 대기열에 추가됩니다.
2. need_visit 대기열에서 첫 번째 데이터를 팝하고 temp_node로 가져옵니다.
3. 방문 큐에 temp_node가 존재하는지 확인
4-1. 그렇지 않은 경우 방문 대기열에 A를 추가합니다.
4-2. 존재하는 경우 아무 작업도 수행하지 않고 2단계부터 다시 시작합니다.
5. graph_dict에서 temp_node였던 A를 키로 찾아 그 결과 값을 need_visit queue에 추가합니다.
6. need_visit 대기열이 비워질 때까지 2-5단계를 반복합니다.
7. 방문한 대기열 반환
위와 같은 과정을 거치게 됩니다.
결과적으로 방문 큐를 얻을 수 있습니다.
암호
graph = dict()
graph('A') = ('B', 'C')
graph('B') = ('A', 'D')
graph('C') = ('A', 'G', 'H', 'I')
graph('D') = ('B', 'E', 'F')
graph('E') = ('D')
graph('F') = ('D')
graph('G') = ('C')
graph('H') = ('C')
graph('I') = ('C', 'J')
graph('J') = ('I')
def bfs(graph):
visited = ()
need_visit = ()
need_visit.append('A')
while need_visit:
temp_node = need_visit.pop(0)
if temp_node not in visited:
visited.append(temp_node)
need_visit.extend(graph(temp_node)) # list 뒤에 list를 그대로 붙여 하나의 list로 만드는 것이기 때문에 extend 사용
return visited
print(bfs(graph))