traverse algorithms

algorithm
algorithm, graph, tree

Backtracking

  • 특징

    • 주로 재귀호출 사용
    • tree traverse, 특히 state tree traverse 문제의 해결방법
    • 모든 가능성을 뒤져보는 행위 : 느릴 수 밖에 없음
    • 보통 지수함수 이상의 time complexity를 가진다
    • 가지치기 (Prunning)을 사용하면 효과의 향상을 가져올 수 있음 (DFS와의 차이)

  • rough implementation

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # recursive
    def backtracking (candidate):
      # 01. Reject or accept
      answer = []
      if isReject(candidate)  return []
      if isAccept(candidate)  answer.append(candidate)
      # 02. Recursive call
      subProblem = getFirstChild(candidate)
      while isValid(subProblem):
        answer += backtracking(subProblem)
        subProblem = getNextChild(candidate)
      return answer

DFS

  • 특징

    • recursive / iterative 둘 다 구현 가능
    • iterative하게 구현할 경우 stack을 써서 candidate 관리
    • Time complexity : O(V + E)
    • Space complexity : O(V)

  • rough implementation ()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # recursive
    def dfs(graph, start, visited=None):
      # 01. check visit status
      if visited == None:
        visited = set()
      visited.add(start)
      # 02. do something with the start vertex
      doSomething(start)
      # 03. recursive call
      candidates = [v for v in grpah.getAdj(start) if isVisited(v)]
      for v in candidates:
        dfs(graph, v, visited)

BFS

  • 특징

    • candiate을 queue로 구현함
    • iterative하게 구현해야함 (recursive로는 어려움)
    • Time complexity : O(V + E)
    • Space complexity : O(V)

  • rough implementation

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # iterative
    def bfs(graph, start):
      # 01. initialization
      visited, queue = set(), [start]
      while queue != []:
        # 02. do something with the start vertex
        doSomething(start)
        # 03. find the candidates
        candSet = [v in graph.getAdj(start)]
        for cand in candSet:
          if isVisited(v) in not visited:
            queue.append(v)
        queue.pop(0)

Shortest path finding in graph

  • dijkstra algorithm
  • Bellman-ford algorithm
  • A* search

Backtracking in Wikipedia

BFS & DFS in python

Depth first search

Breadth first search

Share Comments