DFS

02 Aug 2022 in Study / Computer science on Dfs

Algorithm

• Depth First Search for graph
• Backtracking (move easily back to previous node)
  • != BFS
• can be used when we should memorize the previous nodes’ weight value (가중치) in the same path (BFS is used when all nodes have same value for solving minimum distance)
• can be used when we should search all nodes
  • Consequently, we can check whether there are nodes that are not connected from the graph
  • Size of graph ↑ → inefficient
  • We can use DP for removing the repeating search in DFS
• can be used for topology sorting
• can be used for big graph
  

Implementation

• by stack
  • LIFO (Last in, First Out)
  • Implementation 1 in python : deque (bidirectional queue) : efficient

    from collections import deque
    q = deque()
    q.append(1)  # [1]
    q.append(2)  # [1, 2]
    q.pop()  # [1]
    

  • Implementation 2 in python : recursion (Recursion originally uses the principle of stack)
• Procedure
  1. node → stack
  2. A top node escapes from stack
  3. This node is marked “visited”
  4. All adjacent nodes of this node are processed by first step simultaneously (repeating)
     
• Mark “visited”
  • example 1
    

    graph[i][j] = 0 # originally 1
    

  • example 2
    

    visited = []
    visited.append(/*specific node*/)
    if node not in visited:
    # statement
    

  • examnple 3
    
    • We can use set instead of list for implementing the ‘visited’
    • “in” takes O(N) for list but it will take O(1) when we use set

Pseudocode (implementation 1)

from collections import deque

def DFS(graph, start_node):
  visited = []
  need_visit = deque()
  need_visit.append(start_node)

  while need_visit:
    node = need_visit.pop()
    visited.append(node)

    ## movement toward adjacent nodes of the node (adjacent_node가 여러 개이므로 for문으로)
      if adjacent_node not in visited:
        need_visit.append(adjacent_node)

Pseudocode (implementation 2)

from collections import deque

def DFS(graph, start_node, visited=[]):
  visited.append(start_node)

  ## movement toward adjacent nodes of the node (adjacent_node가 여러 개이므로 for문으로)
    if adjacent_node not in visited:
      DFS(graph, adjacent_node, visited)
  return