BFS
-
[정리] - The graph theory and the DFS, BFS methods - 2정리 2021. 10. 2. 20:37
DFS는 Depth-First Search의 약자로 어떤 그래프가 있을 때, 임의의 한 정점[Vertex, Node]에서부터 시작하여 순회를 함에 있어서 한 노드의 끝까지 갔다가 Backtracking을 하는 알고리즘입니다. 그렇다면 BFS라고 불리는 Breadth-First Search는 어떠한 알고리즘일까요? 이는 Queue을 이용하여 문제를 푸는데 많은 도움을 줍니다. 저는 왜 Queue을 써야하는지 왜 그런 식으로 코드를 짜서 문제를 푸는지 이해하는데 많은 어려움을 겪었습니다. 일단 Queue자체는 Insertions(push)과 Deletions(pull or pop)이 상수 시간 내에 동작한다는 특징을 갖고 있습니다. 그렇기 때문에 어떤 연결된 그래프, Spanning Tree을 순회하기 위해..