깊이우선탐색(DFS, Depth First Search)

DFS는 그래프를 탐색할 때 쓰는 알고리즘이며 어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘입니다.

수도코드

DFS의 수도코드는 다음과 같습니다. 

수도코드(pseudocode)? 는 프로그램의 로직을 표현하기 위해 쓰이는 코드입니다. 주로 어떤 알고리즘이 어떠한 로직을 갖고 있는 지 나타내기 위해 쓴다. 

 

 

<설명>

어떠한 정점 u의 visited를 참으로 바꾸고 u로 부터 연결되어있는 v지점을 탐새합니다.

이 때 방문되어있지 않은 노드에 대해 재귀적으로 DFS를 호출합니다. 

재귀적으로 1,2,4번까지 방문한다. 또한, 4번에서 다시 2번으로 가려고 했지만 이미 방문한 노드이기 때문에 다시 방문하지 못하고 5번으로 간다. 

 

1 - 2 - 4 -5 - 3

 

DFS 구현방법

1. 돌다리 두드려보기

visited 되어있는지 확인

2. 일단 GO

일단 방문되어있던 안되어있던 무조건 dfs를 호출하고 해당 함수에서 만약에 방문되어있다면 return 해 함수를 종료시키는 방법입니다.