자료구조 (1) 썸네일형 리스트형 BFS BFS? BFS는 너비 우선 탐색이다. 이 자료구조는 웹 크롤링, 퍼즐이나 게임 풀기, 소셜 네트워크(친구 찾기) 등에서 쓰인다. 그래프를 탐색하는 방법 중 하나이다. 그래프는 vertex(정점), edge(간선)으로 이루어져 있으며 시간복잡도는 O(V+E)로 알려져 있다. 탐색 과정 BFS 방식으로 그래프를 탐색하는 과정은 아래와 같다. 레벨 0이 시작 정점이자 레벨 1의 부모 정점이라고 하자. 그럼 BFS는 레벨 1에 있는 모든 정점 즉, 정점 s의 자식 정점들인 레벨 1에 있는 정점들을 모두 탐색한다. 이 과정의 반복이다. 또 레벨 1의 정점들은 레벨 1의 자식 정점인 레벨 2의 정점들을 모두 탐색한다. 한 정점을 파고들어 그 정점의 끝 정점까지 파고드는 것이 아닌, 한 정점의 모든 자식 정점을 탐.. 이전 1 다음
