그래프탐색 썸네일형 리스트형 [Computer Science] 자료구조 - 그래프 탐색 DFS, BFS DFS(depth-first search) - 깊이우선탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. LIFO 스택 자료구조(혹은 재귀함수)를 이용 DFS 동작과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더이상 2번 과정을 수행할 수 없을 때까지 반복. Backtracking DFS에서 활용되는 방법, 노드가 있을만한 곳을 되돌아가서 모두 살펴본다는 개념 위의 그림처럼 DFS는 깊이우선적으로 탐색을 진행하고, 재귀적으로 아래에서부터 탐색하지 않은 정점이 있는지 확인하는 방법으로 되돌아가는 것에서 backtracki.. 더보기 이전 1 다음