[알고리즘] DFS(깊이 우선 탐색) 정리

[알고리즘] DFS 정리

아래와 같이 두 가지 그래프가 있을 때 DFS 구현 방법에 대해 작성한다.

• 그래프 2가지

  graph = [
      [],
      [2,3,8], # 1번 노드에 연결된 노드: 2번, 3번, 8번 노드
      [1,7], # 2번 노드에 연결된 노드: 1번, 7번 노드
      [1,4,5],
      [3,5],
      [3,4],
      [7],
      [2,6,8],
      [1,7]
  ]
  
  graph2 = {
      'A': ['B'],
      'B': ['A', 'C', 'H'],
      'C': ['B', 'D'],
      'D': ['C', 'E', 'G'],
      'E': ['D', 'F'],
      'F': ['E'],
      'G': ['D'],
      'H': ['B', 'I', 'J', 'M'],
      'I': ['H'],
      'J': ['H', 'K'],
      'K': ['J', 'L'],
      'L': ['K'],
      'M': ['H']
  }

• DFS for graph

  • 재귀를 쓰지 않는 DFS - 스택(stack) 사용

    def dfs(graph, start, visited):
        path = []
        stack = []
        stack.append(start)
    
        while stack:
            current_node = stack.pop()
            if not visited[current_node]:
                path.append(current_node)
                visited[current_node] = True
                stack.extend(reversed(graph[current_node]))
    
        return path
    
    visited = [False] * 9
    print(dfs(graph, 1, visited))

  • 재귀를 쓰는 DFS

    def dfs_with_recursive(graph, start, visited):
        visited[start] = True
        print(start, end = ' ')
    
        for i in graph[start]:
            if not visited[i]:
                dfs(graph, i, visited)
    
    visited = [False] * 9
    dfs_with_recursive(graph, 1, visited)

• DFS for graph2

  • 재귀를 쓰지 않는 DFS - 스택(stack) 사용

    def dfs2(graph, start):
        path = []
        visited = []
        stack = []
        stack.append(start)
    
        while stack:
            current_node = stack.pop()
            if current_node not in visited:
                path.append(current_node)
                visited.append(current_node)
                stack.extend(reversed(graph2[current_node]))
    
        return path
    
    print(dfs2(graph2, 'A'))

  • 재귀를 쓰는 DFS

    def dfs2_with_recursive(graph, start, visited):
        visited.append(start)
    
        for i in graph[start]:
            if i not in visited:
                dfs2_with_recursive(graph, i, visited)
    
    visited = []
    dfs2_with_recursive(graph2, 'A', visited)
    print(visited)