DFS
-
[정리] - 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을 순회하기 위해..
-
[정리] - The graph theory and the DFS, BFS methods - 1정리 2021. 10. 1. 22:16
DFS, BFS은 응용하기 참 까다롭습니다. 왜 Queue을 사용하는지, 왜 Stack인지, 왜 재귀인지 받아들이는 것이 어렵습니다. Graph Theory에서 배우는 간단한 용어를 알고 있으면 좋습니다. 어떤 식으로 BFS와 DFS의 논리가 작동하는지 뼈대를 알아야 응용함에 있어서 어려움을 최소화 할 수 있다고 믿습니다. The number of edges 일반적으로 간단한 그래프[Simple Graph]는 임의의 정점[Vertex, Node]의 집합과 엣지[Edge]들의 집합으로 구성되어 있습니다. 그리고 그래프는 다시 크게 Directed Graph와 Undirected Graph로 나눌 수 있습니다. 이름이 직관적으로 설명하는 것처럼 전자는 정점과 정점 사이에 방향이 존재하지만 후자는 그렇지 않습..