DFS . 4

 

 

 

 

 

 

DFS 동작 예시:  스택 자료구조인 경우

방문 기준: 번호가 낮은 인접 노드부터

 

 

 

 

 

DFS 코드 예제 :  재귀함수를 사용한 경우

(재귀함수로 구현하고 노드 방문 순서를 출력한 예시)

 

 

일반적으로 그래프 문제에서는 노드의 번호가 1번부터 시작하기 때문에
그래프를 초기화할 때 인덱스 0에 대한 내용은 비워두고 1번 인덱스부터 채운다

 

그렇기에 방문여부를 확인하는 리스트의 요소 개수를 노드 개수보다 1 높은 수로 선언하기

 

 

2차원 리스트를 선언할 때 숫자들을 작은 수부터 차례대로 써서
재귀함수를 통해 우리가 원하는 대로 출력이 되게 만들 수 있었다.

 

 

 

 

 

 

 

자바
ArrayList 는 특정 인덱스에 접근하기 위해 상수시간이 소요되기 때문에 일반 배열보다 더 좋다

ArrayList를 중첩된 형태로 이용해서 그래프를 표현할 수 있다