4-2. 그래프의 탐색(DFS, BFS)

그래프의 탐색 목적: 시작점 X로 시작하여 모든 정점을 1번씩 방문하고자 한다. 깊이 우선 탐색(DFS) 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고, 더 이상 갈 수 없으면 이전 정점으로 돌아간다. 스택을 이용하는 가장 쉬운 방법은 재귀 호출을 이용하는 방법이다. 인접 행렬을 이용한 구현은 다음과 같다. 정점의 갯수를 V라고 할 때, 시간 복잡도는 O(v^2)가 된다. void dfs(int x) { check[x] = true; printf("%d ", x); for(int i=0; i

2019.05.16