DongDD's IT

BFS(Breadth-First-Search) Algorithm BFS Algorithm - 그래프나 트리같은 자료구조에서 사용하는 Search 알고리즘- DFS에서는 재귀 호출로 구현하는 경우가 많지만, BFS에서는 보통 queue 자료구조를 사용해 구현한다.- 갈 수 있는 경로를 쭉 따라가는 DFS와 달리, 현재 Vertex에서 갈 수 있는 모든 정점을 방문한 후 방문한 정점을 기준으로 다시 갈 수 있는 모든 정점을 방문하는 식으로 진행된다. BFS Complexity - 인접 리스트를 이용해 그래프를 구현하는 경우와 인접 행렬을 이용해 구현하는 경우에 따라 시간복잡도가 다름 1) 인접 리스트- 한 정점에서 방문할 수 있는 정점을 간선 기준으로 탐색할 수 있기 때문에 O(V+E)의 시간 복잡도를 가진..