211025월 - 너비 우선 탐색(Breadth First Search)

211025월 - 너비 우선 탐색(Breadth First Search)

1. 너비 우선 탐색 : 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식.

2. 깊이 우선 탐색(Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식

1. 너비우선탐색 (BFS)

: 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회함.

2. 깊이 우선 탐색 (DFS)

: 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내력며 순회함.

방식에 따라 노드를 탐색하는 순서가 달라진다.

1. 너비우선탐색 (BFS)

=> 파이썬의 딕셔너리(map)와 리스트(array) 자료 구조를 활용해서 그래프를 표현할 수 있다.

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']

- 알고리즘 구현

자료구조 큐를 활용함 need_visit 큐(방문이 필요한 노드들의 정보)와 visited 큐(방문한 노드를 순서대로 저장), 두 개의 큐를 생성

need_visit 큐에서 시작점key 부터 하나씩 꺼내서 visited 큐에 저장. 그 과정에서 key 의 value들을 need_visit 큐에 저장. 만약 need_visit 큐에서 막 꺼낸 key가 이미 visited 큐 속의 key와 중복일 시, 아무것도 안하고 다음 need_visit 큐 pop

=> 이런식으로 그래프 쭉 가면 BFS 방식의 탐색이 된다.

- 코드로 구현

def bfs(graph, start_node): visited = list() need_visit = list() need_visit.append(start_node) while need_visit: node = need_visit.pop(0) if node not in visited: visited.append(node) need_visit.extend(graph[node]) return visited

- 시간복잡도

* 노드수: V

* 간선 수: E

* 위코드에서 while need_visit 은 V+E 번 만큼 수행함.

* 시간 복잡도: O(V+E)

from http://jun01.tistory.com/96 by ccl(A) rewrite - 2021-10-25 22:26:37