깊이 우선 탐색 알고리즘(DFS) - JAVA

깊이 우선 탐색(Depth-first Search)이란? "루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법" 넓이 우선 탐색과 (Breadth-first Search) 대비되는 알고리즘으로 말 그대로 넓이 보단 깊이를 우선적으로 탐색하겠다는 뜻 먼저 그림을 통해 이해를 해보자 이제 위에서 본 그림을 인접리스트를 사용한 JAVA 코드로 풀어보자 사용할 LinkedList와 boolean타입의 배열 선언부 /* * 먼저 정점들의 연결 다리가 되어줄 * LinkedList와 * * 방문 여부를 확인할 * boolean 타입의 배열을 선언 */ public class DFS { private LinkedList list[]; // 정점들의 인접 리스트를 저장하는 배열 pri.....