DFS

- DFS(Depth First Search)

그래프 탐색의 한 종류

깊이 우선 탐색

Stack을 활용하여 데이터 탐색

 

* 구현 방법

1. 인접 행렬

- 행렬로 정점들 사이의 관계를 표현 하는 것

- 간선 방향의 존재 유무에 따라 표현하는 방법에 차이 존재

- 예시

- 용어 정리

(1) edge - 간선의 수

(2) vertex - 정점의 수 

(3) map - 정점 간의 연결 정보를 담는 객체

(4) visit - 정점을 방문했는지 체크하기 위한 객체

 

2. 인접 리스트

- 인접 리스트 방식은 리스트 방식으로 각 정점이 연결 된 노드들이 정보를 저장한다.

- 예시

- 인접 행렬과 다르게 모든 정점의 수를 나타내지 않고 한 정점과 연결된 것들만 보여준다.

- 메모리를 신경써야 할 때 인접 리스트로 표현해주는 것이 좋다. 

- 코드 관련 용어

(1) arrayList : 정점간의 관계를 담는 객체

(2) dfsList : 방문한 순서대로 저장하기 위한 리스트 객체

(3) visit : 정점을 방문했는지 체크하기 위한 객체