mondegreen

너비우선탐색 개념 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후, 방문했던 정점을 시작점으로 하여 그 시작점과 인접한 정점을 다시 차례로 방문하는 방식을 말한다. 이 때 방문했던 인접 정점도 순서대로 다시 인접 정점을 탐색해야 하므로 선입선출 형태의 자료구조인 Queue(큐)를 활용한다. 방문 여부 검사를 통해 무한루프에 빠지지 말아야 한다. 너비우선탐색 특징 1) 시작 노드로부터 단계적으로 거리에 따라 탐색한다. 2) 재귀적으로 작동하지 않는다. 3) 프림 및 다익스트라 알고리즘과 유사하다. 구현 방식1) 인접행렬 두 정점이 연결되어 있는 여부를 한 눈에 확인 가능하나, 시간도 많이 사용하고 메모리 낭비가 심하다. 들어오고 나가는 간선이 한 눈에 보이기 때문에 간선이 많을 때(밀집 그래프)..