dfs
-
그래프 순회자료구조 2021. 1. 23. 13:43
그래프 순회란 그래프 탐색이라고도 불리며 그래프의 각 정점을 방문하는 과정을 이야기 한다. 그래프 순회는 크게 깊이 우선 탐색(Depth First Search)와 너비 우선 탐색(Breadth First Search)의 2가지 알고리즘이 있다. DFS - 일반적으로 BFS에 비해 더 널리 쓰인다. - 코테에서도 그래프 탐색은 주로 DFS로 구현하게 된다. - 주로 스택이나 재귀로 구현하며 백트래킹을 통해 뛰어난 효용을 보인다 앞서 말했듯 DFS는 스택으로 구현하며 재귀를 이용 하면 좀 더 간단하게 구현 할 수 있다. 코테에서도 재귀 구현이 더 선호된다. 재귀 구조로 구현 해당 사진은 위키피디아에 제시된 수도코드이다. 이 수도코드에서 정점 v(vertex)의 모든 인접 유향(Directed) 간선들을 반..