DFS(깊이 우선 탐색)

그래프 탐색 알고리즘에는 대표적으로 DFS,BFS가 있다.
DFS(depth first search)는 깊이 우선 탐색 알고리즘으로, 최상위(부모)노드에서 가장 깊이있는 최하위(자식)노드까지 일방향 순차적으로 방문하며 최하위 노드에 도달하면 리턴하는 방법으로 그래프를 탐색한다. 코드로 구현시, 재귀함수나 스택의 구조로 구현이 가능하다.

아래 사진을 참고하여 이해를 도울 수 있다.

출처: https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

파이썬의 경우 재귀를 사용할 때, 가장 간단한 코드 구현은 다음과 같다.

def dfs(graph,root,visted):
    visted[root]=True
    print(root,end=' ')
    for i in graph[root]:
      if not visted[i]:
        dfs(graph,i,visted)
graph = [
    [],
    [2,5,9],
    [1,3],
    [2,4],
    [3],
    [1,6,8],
    [5,7],
    [6],
    [5],
    [1,10],
    [9]
]

visted = [False]*(10+1)
dfs(graph,1,visted)



실행결과
> 1 2 7 6 8 3 4 5

다음은 스택(Stack)을 이용한 코드 구현이다.

def dfs():
  root=1
  visted = [False]*(10+1)
  stack = []
  stack.append(root)
  while stack:
    n = stack.pop()
    print(n,end=' ')
    visted[n]=True
    for i in graph[n]:

      if visted[i]:
        continue
      else:
        stack.append(i)

graph = [
    [],
    [2,5,9],
    [1,3],
    [2,4],
    [3],
    [1,6,8],
    [5,7],
    [6],
    [5],
    [1,10],
    [9]
]
dfs()

실행결과
> 1 9 10 5 8 6 7 2 3 4