비선형 구조
데이터를 저장하기 위한 방법으로 데이터 간의 관계를 이루면서 계층적인 구조를 가지며 일렬로 나열되지 않은 자료구조 형태를 의미한다.
- 대표적인 비선형 구조는 트리, 그래프 등이 있다.
그래프
비선형 구조 중 하나로 정점과 그들 사이를 연결하는 간선으로 표현된 자료구조
각 정점은 데이터를 저장하며 간선은 정점들 간의 관계를 나타낸다.
DFS 알고리즘 (깊이 우선 탐색)
DFS 알고리즘이란 ?
그래프 탐색 알고리즘 중 하나로 한 방향으로 갈 수 있을 때까지 최대한 깊게 탐색한 후 더 이상 갈 수 없게 되면, 다시 돌아와 다음 경로를 탐색하는 방식을 의미한다.
- 한 노드에서 시작하여 가능한 한 깊이 탐색한 후, 다음 분기로 넘어간다.
DFS의 주요 특징
- 탐색 과정
- 한 정점에서 시작하여 최대한 깊게 탐색한 후, 더 이상 방문할 수 있는 정점이 없을 경우 이전 정점으로 돌아와 다른 경로로 탐색한다.
- 위 과정을 반복하여 그래프의 모든 정점을 탐색한다.
- 최단 경로를 찾는 문제와 다르게, 경로의 길이를 고려하지 않는다.
- 탐색을 시작한 정점에서부터 가능한 한 깊이까지 탐색하기 때문에, 최단 경로를 찾는 문제에는 다른 알고리즘(ex. BFS)을 사용해야 한다.
DFS 구현 방법
- 재귀 함수
- 그래프의 깊은 부분을 탐색할 경우에는 스택 오버플로우가 발생할 수 있으므로 반복적인 구현이 필요할 수 있다.
- 스택