[DFS&BFS] 개념 정리

** 본문의 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬 (나동빈)' 을 읽고 정리한 내용입니다 **

DFS

표현방법

1. 인접행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식
   • 마치 표처럼!
   • 연결되어 있지않은 노드끼리는 무한의 값(99999999)을 가지고 있다고 작성함 
   • 모든 관계를 저장하므로, 노드 개수가 많을수록 메모리 낭비
2. 인접 리스트 : 리스트로 그래프의 연결관계를 표현하는 방식
   • 각 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
   • 연결된 정보만 저장하기 때문에 메모리 효율성 높음.
   • 연결된 정보를 하나씩 확인 →  특정 두 노드가 연결되어있는지에 대한 정보를 얻는 속도가 느림

특징

• like stack
• 구현시, 재귀 방법 이용 ( 재귀 함수는 내부적으로 스택 자료구조와 동일 )
• 탐색 시간 복잡도: O(n)

예시 코드

def dfs(graph, v, visited):
  # 현재 노드 방문처리
  visited[v] = True
  print(v, end='')
  # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)


# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
# ex) 1번 노드는 2,3,8번 노드와 연결되어 있음
graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8],
         [1, 7]]

#각 노드가 방문된 정보를 리스트 자료형으로 표현
visited = [False] * 9

#정의된 DFS 함수 호출
dfs(graph, 1, visited)

 

BFS

 

표현방법

1. 인접행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식
   • 마치 표처럼!
   • 연결되어 있지않은 노드끼리는 무한의 값(99999999)을 가지고 있다고 작성함 
   • 모든 관계를 저장하므로, 노드 개수가 많을수록 메모리 낭비
2. 인접 리스트 : 리스트로 그래프의 연결관계를 표현하는 방식
   • 각 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
   • 연결된 정보만 저장하기 때문에 메모리 효율성 높음.
   • 연결된 정보를 하나씩 확인 →  특정 두 노드가 연결되어있는지에 대한 정보를 얻는 속도가 느림

특징

• like queue
• 구현 시, deque library 사용
• 탐색 시간 복잡도: O(n)
• 보통 DFS보다 BFS 구현이 조금 더 빠르다

알고리즘

1. 탐색 시작 노드를 queue에 삽입하고 방문 처리 한다
2. queue에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 queue에 삽입한다
3. 2번을 더이상 하지 못할때까지 반복한다 

예시 코드

from collections import deque

def bfs(graph, start, visited):
  queue = deque([start])
  # 현재 노드 방문 처리
  visited[start] = True
  # queue가 빌때까지 반복
  while queue:
    # 하나의 원소를 뽑아 출력
    v = queue.popleft()
    print(v,end=' ')
    # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 queue에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(=DFS)
# ex) 1번 노드는 2,3,8번 노드와 연결되어 있음
graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8],
         [1, 7]]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현 (=DFS)
visited=[False]*9

bfs(graph,1,visited)

 

팁

• 2차원 배열의 '탐색 문제'는 그래프 형태로 바꿔서 풀면 풀이가 쉽다