[ 데이터구조 ] DFS, BFS

기초 지식

• 트리/그래프 순회 (traversal)의 방법 중 하나
  • 순회 (traversal) : 중복 없이 모든 노드를 한번씩 방문하는 것.

[요약] Stack, Queue

• stack
  • LIFO (last-in first-out)
  • push : top에서 새로운 원소 삽입
  • pop : top에서 원소 빼내며 삭제
  • 재귀함수를 이용해서 구현하기도 한다.
  • Python의 list 이용
• queue
  • FIFO (first-in first-out)
  • enqueue : rear에서 새로운 원소 삽입
  • dequeue : front에서 원소 빼내며 삭제
  • Python의 deque 라이브러리 이용 (from collections import deque)

[요약] Graph

• node + edge로 구성된 자료구조
• 기본 용어
  • cycle : node가 edge를 통해 다시 본인 node로 돌아오는 것 (현재 node 제외 중복 X)
  • 노드의 degree : edge (branch) 개수

• 인접 리스트 : n개의 node 각각에 대해 인접한 node들을 표현한 리스트

  

DFS (Depth-first search/traversal)

• stack (재귀 ver.)으로 구현한다.
• 필요한 변수들
  • graph : 그래프의 인접 리스트 (2차원 리스트)
  • v : 현재 node의 index
  • visited : 방문한 node 리스트 (boolean list)

• 알고리즘

  현재 node 방문 → 인접한 node를 재귀적으로 방문

• 구현예제

    # DFS 함수 정의
    def dfs(graph, v, visited):
        # 현재 노드를 방문 처리
        visited[v] = True
        print(v, end=' ')
        # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for i in graph[v]: # 현재 노드 v의 인접 리스트 내 원소들 방문
            if not visited[i]:
                dfs(graph, i, visited)
      
    # 인접 리스트 (이걸로 그래프 모양을 추정할 수 있다.)
    # node 번호를 1번부터 시작하기 위해 첫번째 리스트 원소는 빈 리스트이다.
    graph = [
      [],
      [2, 3, 8],
      [1, 7],
      [1, 4, 5],
      [3, 5],
      [3, 4],
      [7],
      [2, 6, 8],
      [1, 7]
    ]
      
    # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
    visited = [False] * 9
      
    # 정의된 DFS 함수 호출
    dfs(graph, 1, visited)
  

BFS (Breadth-first search/traversal)

• queue로 구현한다.
• 필요한 변수들
  • graph : 그래프의 인접 리스트
  • start : 최초 시작 node의 index
  • visited : 방문한 node 리스트
• 재귀 사용하지 않는다.

• 알고리즘

    1. [초기세팅] start 들어간 deque 생성 & visited 방문 처리
    2. deque가 빌 때까지
        1. 현재 노드 pop (from front)
        2. 꺼낸 얘의 인접한 노드들에 대해
                방문하지 않은 노드라면
                그 노드 append (from rear)
                visited 방문 처리   
    

• 구현예제

    '''
    deque 자료구조를 구현한 라이브러리를 이용하지만 
    실질적으로는 queue를 이용해서 구현하므로
    "한 방향으로만" 넣고 빼야 한다!!!!!
    '''
      
    from collections import deque
      
    # BFS 함수 정의
    def bfs(graph, start, visited):
        queue = deque([start])  # start를 원소로 갖는 리스트가 deque이 된다.
        visited[start] = True  # 현재 노드를 방문 처리
          
        while queue:  # 큐가 빌 때까지 반복
            v = queue.popleft()  # 큐에서 하나의 원소를 (front에서) 뽑는다.
            print(v, end=' ')
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i) # 곧 방문한 노드이므로 (rear로) 추가
                    visited[i] = True
      
    # 인접 리스트 (이걸로 그래프 모양을 추정할 수 있다.)
    # node 번호를 1번부터 시작하기 위해 첫번째 리스트 원소는 빈 리스트이다.
    graph = [
      [],
      [2, 3, 8],
      [1, 7],
      [1, 4, 5],
      [3, 5],
      [3, 4],
      [7],
      [2, 6, 8],
      [1, 7]
    ]
      
    # 각 노드가 방문된 정보를 리스트 자료형으로 표현 (1차원 리스트)
    visited = [False] * 9
      
    # 정의된 BFS 함수 호출
    bfs(graph, 1, visited)