DFS

앞서 알아본 그래프에서 순회를 하려면 어떻게 해야 할까?

그래프는 배열처럼 인덱스를 증가시키면서 할 수 없는 구조이다. 

 

따라서 순회를 하는 알고리즘이 존재하는데 그 중 하나가 DFS라는 놈이다.

 

DFS는 Depth First Search로 깊이 우선 탐색이다. 

 

깊이 우선 탐색은 연결된 길이 끝날때까지 쭉~ 가는것이다. 그리고 막다른 길이 나올 시 안갔던 길로 다시 쭉~ 가는 것

 

지금 그림에서는 0 - 1 - 2 를 가고 더이상 길이 없으니 가지 않았던 길 3 - 4 이렇게 가는것

 

한번 Graph와 DFS를 구현한다면 

먼저 행렬로 구현한 그래프로 DFS를 진행하려면

 

내가 방문한 Vertex의 정보가 있어야한다. 

 

방문 기록용 변수를 하나 생성

 

먼저 DFS 함수 시작으로 시작점(Vertex) 값을 받고 그 위치는 내가 갔다고 기록을 해둔다!!

 

연결되어있고(행렬 방식이라 연결되어 있지 않은 점도 모두 포함되서 조건을 걸어야함),

내가 가지 않은 길을 찾기 위해서 조건을 걸어서 스킵한다.

조건에 부합한 수가 있으면 

다시 DFS함수를 실행한다. 

 

이것은 재귀함수로, 함수에서 자기 자신 함수를 또 호출하는것. 흐름도를 생각해보면 

 

0번에서 시작한다고 가정했을 때, 방문했으니 체크를 진행해야할것.

그리고 연결되있고, 방문하지 않은 1번 Vertex를 찾을것임. 그 1번 Vertex에 갔으면?? 또 조건에 부합한 Vertex를 찾아야 한다. 그러므로 조건에 부합한 Vertex를 넘겨주고 동일한 함수를 실행하는것.

 

이런식으로 간단하게 DFS를 구현! 한번 실행해보면 

순회한 0, 1, 2, 3, 4 값이 나오는것을 볼 수 있다.

 

그렇다면 시작점을 3번으로 넣어보면?

정상적으로 출력된다. 여기서 ~ 잠깐 헷갈린것이 있는데..

 

0으로 갔을때, 더이상 갈 길이 없으니까 contunue 되서 끝나는것 아닌가라고 생각할수도 있는데! 

 

아니다. 재귀함수를 사용했으니까.. 0번 함수가 끝나면 아직 1번 Vertex를 가지고 있는 함수로 되돌아간다. 하지만 1번 Vertex를 가지고 있는 함수는 아직 for문을 전부 돌지 않았으니 다시 2로 갔다가 막다른길에 도달했으니 3으로 갔다가 4로감!!

 

재귀함수...솔찍히 넘 헷갈림.. ㅠ

 

암튼 이렇게 해서 DFS 구현 완료!

 

하지만 이 구조에서는... 한가지 문제점이 존재한다! 바로 

 

모든 Vertex가 연결되어 있지 않다면? 

 

지금의 로직 상으로는 연결된것과 갔던 것을 처리하고 있어서 연결된 것에서 무시가 되니까 방문하지 못함.

그래서 모든 Vertex에 접근해서 가보지 않은 길에 DFS를 돌려줌으로서 처리한다!