cp-algorithm1 BFS 0. 서론 BFS는 그래프에서 가장 기본적이고 필수적인 탐색 알고리즘이다. BFS의 동작원리 때문에 BFS로 찾아진 모든 경로들은 항상 어떤 노드 v로 부터의 최단거리경로가 된다. 알고리즘의 시간복잡도는 \( O \left( n + m \right) \)인데, 이 때 n은 정점(vertices)의 개수, m은 간선(edges)의 개수이다. 그 이유는 BFS에서는 모든 정점과 노드들을 딱 한번씩만 방문하기 때문이다. 1. BFS(Breadth First Search) 란? BFS 알고리즘은 입력으로 unweighted graph와, source vertex s, 총 두개를 받는다. 입력으로 주어지는 그래프는 directed graph, undirected graph 둘 다 가능하다. 아래에 BFS가 어떻게.. 2021. 12. 6. 이전 1 다음
