큐
-
[DFS/BFS] 개념정리3 - DFS과 BFSAlgorithm/개념정리 2021. 7. 17. 14:29
그래프 탐색이란? → 하나의 정점을 시작으로 다수의 정점을 방문하는 것 DFS(Depth First Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 이 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘임 사용 자료구조 : 스택 동작 과정 : 탐색 시작 노드를 스택에 삽입하고 방문 처리함 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문처리 함 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄 2번의 과정을 더 이상 수행할 수 없을 때까지 반복함 —> 방문 처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않..