[Algorithm] 그래프 순회(1) - DFS

DFS 방법을 사용해서 그래프 순회하기

: 먼저 구현한 코드부터 올려보면 위와 같다.

• DFS는 스택을 사용해서 그래프를 순회하는 것인데, 스택이란 일종의 발자취를 기록하는 자료구조와 같다. 또한, 스택은 재귀함수로 구현되기 때문에 결과적으로 DFS도 스택으로 구현할 수 있다.
  : 위의 그림을 DFS 방법으로 순회하고자 위의 코드를 만들었고, 이를 위해 이러한 그래프를 자바스크립트의 객체와 배열을 이용하여 먼저, 자료구조의 형태로 만드는 작업을 해줬다.
  : 위의 코드를 통해 아래 그림과 같은 그래프 자료구조를 만들어냈고, 이제는 실제로 맨위의 코드를 하나하나 쫓아가면서 위의 그래프를 DFS 방식으로 순회해보고자 한다.

  ---

• 먼저, 스택이라는 배열을 만들어서 거기에 탐색을 시작하고자 하는 노드의 인덱스에 true값을 넣어준다. 이는 이미 해당 노드를 방문했음을 표기해놓기 위함이다.
  : 그럼 다음은 재귀함수 구현 부분이데, 처음에 이 재귀함수의 매개변수로 노드 1의 인접 노드가 담긴 배열을 넣어준다(graph[1]을 넣어주면 된다). 이 때, 매시행마다 arr를 오름차순 정렬하는 이유는 이번 DFS에서는 인접 노드를 탐색할 때 그 수가 가장 작은 노드부터 탐색하기 위함이다. 그러면 graph[1]의 인접 노드들의 배열인 [2,4]를 먼저 탐색할 것이고, 그중에서도 2를 먼저 탐색한다. 이 때, 해당 요소가 이미 방문한 기록이 있는 노드인지를 확인하기 위해
  이 부분을 써줬다. 방문하지 않은 노드에 한해서 다시 재귀 호출로 해당 노드의 인접 리스트를 매개변수로 넣어주는데, 그 전에 역시 앞에서와 마찬가지로 방금 방문한 노드 2를 stack의 인덱스에 true로 표기해준다. 결과적으로 우리는 DFS가 어떤 경로로 탐색을 하는지 보고싶은 것이기에 방문할 때마다 해당 노드를 출력해주도록 했다.
  ** process.stdout.write()를 써주면 자동으로 개행이 되지 않고 출력할 수 있다.
• 위와 같이 DFS는 발자취를 남겨가며 탐색을 하고, 더이상 탐색할 곳이 없을 때 걸어온 발자취를 따라서 돌아간다. 그래서 이러한 방식대로면 처음 시작한 노드에서 가장 깊은 노드, 즉, 더이상 갈곳이 없는 노드까지 탐색을 먼저 할 것이기에 이걸 깊이 우선 탐색이라한다. 그리고 끝까지 간 뒤에 돌아오면서 탐색하지 못한 경로로도 방문하게 된다.
  
  : 결과적으로 위의 경로로 탐색을 했음을 알 수 있다.

마무리 및 첨언

• DFS는 모든 곳이 연결되어있다면 '무조건' 그래프내의 모든 정점을 순회한다.
• DFS의 시간복잡도는 O(V+E)이다. 이 때, V는 전체 정점의 개수이고, E는 간선의 수이다. 본래는 O(V+2E)가 맞지만 상수는 떨어져서 2E=>E가 된 것이다. 이 때, 기억해야할 것이 '차수의 합 = 2 간선의 수'라는 점이다. DFS를 할 때, 모든 노드들은 자기 자신을 방문하고 +1, 자기 자신 외의 인접 노드를 방문한다(= 차수). 이 때, 자기 자신 외의 인접 노드의 개수는 차수로 표현할 수 있고, 이러한 계산법이 모든 노드에 해당되기 때문에 전체의 차수 합 = 2E(E=간선수)와 모든 노드가 자기 자신을 방문하는 개수 1V(=노드수)를 더해서 O(V+E)가 되는 것이다.