[Algorithm-2] Depth First Search Algorithm

DFS는 그래프 데디터 구조에서 작동하는 검색 알고리즘이다. Tree traversal 알고리즘으로 Breadth First Search 알고리즘과 함께 가장 넓리 알려진 알고리즘이 아닐까 싶다.

그래프(Graph)와 트리(Tree)에 대한 차이점에 대해서 헷갈려하는 사람들이 많다. 트리의 정의를 다음과 같이 해보았다.

“A tree is just a restricted form of a graph. Trees have direction(parent/children) and don’t contain cycle. So trees are ‘Directed Acyclic Graph’ (aka DAG) with the restriction that a child can only have one parent.”

“트리는 표현 방식이 제한된 그래프이다. 트리는 방향이 있지만, 사이클이 없다. 그래서 트리는 자식이 오직 하나의 부모만을 가진 ‘방향성을 가진 비순환적인 그래프(DAG)’이다.”

하지만 DFS와 BFS는 트리 뿐만이 아니라 그래프 자료 구조형에서 작동하는 알고리즘이다. 그렇다면 DFS가 어떤 알고리즘인지 알아보도록 하자.

Depth First Search

먼저 해당 알고리즘은 평균적으로 그리고 최악에 경우 O(|E|)만큼 걸리는 Linear적인 알고리즘이다. (쉽게 말해 Edge의 갯수가 곧 성능이라는 것이다.) 동작 방식은 이름에서 알수 있듯이 트리의 루트 노드로 부터 시작해서 자식 노드가 없을 때 까지 반복해서 visiting하는 알고리즘이다. 만약 재귀적으로 implement하지 않고 iteration으로 코들 작성했다면, 이때 Stack 데이터 자료를 사용하여 자식 노드(Leaf Node)가 나올 때까지 Stack에 push한다. 그리고 더 이상 visit할 수 있는 노드(자식 노드)가 없으면, Stack에서 Pop을 하고 다시 맨 위에 올라와 있는 노드에 unvisited한 노드를 방분하여 다시 (Leaf node)가 나올 때 까지 visit한다. 아래 그림은 wiki에서 캡쳐해 온 이미지이다. 노드 안에 숫자는 visit한 순서를 뜻한다.

Screen Shot 2013-12-23 at 11.09.15 AM

 

 

Objective-C Code

다음은 오브젝티브-C로 작성한 DFS이다. 아래 코드는 재귀적으로 작성한 코드이다.

 

  1. - (BOOL)depthFirstSearch:(NSNumber *)num fromNode:(Node *)node
  2. {
  3.     //#1.
  4.     if (!node)
  5.         return NO;
  6.  
  7.     //#2.
  8.     node.isVisited = YES;
  9.  
  10.     //#3.
  11.     BOOL isFound = NO;
  12.     for (Node *n in node.linkedNodesSet)
  13.     {
  14.         //#4.
  15.         if ([n.value isEqualToNumber:num])
  16.             return YES;
  17.  
  18.         //#5.
  19.         if (!n.isVisited)
  20.             isFound = [self depthFirstSearch:num fromNode:n];
  21.  
  22.         //#6.
  23.         if (isFound)
  24.             return YES;
  25.     }
  26.  
  27.     //#7.
  28.     return isFound;
  29. }

 

코드 설명

  1. 전달된 Input 데이터가 없으면 NO로 반환한다.
  2. 노드의 ‘visited’ 변수를 YES로 설정해주고, 다음에 동일한 노드에 visited 했을 때 사용한다.
  3. 전달 받은 노드의 자식 노드들을 구한다.
  4. 찾고자 하는 Num 변수와 비교한다.
  5. 만약 n 변수가 한번도 visited 한적이 없으면 다시 찾고 있는 변수와 함께 재귀적으로 반복해서 작업한다.
  6. 찾고자 하는 값을 찾았으면 YES 값으로 반환한다.
  7. iSFound 객체를 반환한다.