DFS / BFS

1. DFS  : 깊이 우선 탐색 , 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.  시간복잡도는 O(N) 

 

- 인접 행렬 방식  ( 잘 사용 안 함 ) 

: 연결된 것들을 단순지 2차원 배열로 표현한다.  찾는 속도가 빠르지만 크기가 커지면 메모리를 많이 차지함. 

graph = [[] for _ in range(3)]

graph[0].append((1,7))
graph[0].append((2,5))

graph[1].append((0,7))

graph[2].append((0,5))

print(graph)

결과 : [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]] 

 

- 인접 리스트 방식  ( 주로 사용 ) 

나와 연결된 것들을 나열한 리스트로 표현한다. 찾는 속도가 늘지만 메모리 효율성이 높다. ( 필요한 정보만 저장하기 때문에 ) 

다음과 같이 재귀함수를 사용하여 구현 가능하다. 

def dfs( graph, v, visited ):

  visited[v] = True 
  print(v, end=' ')

  for i in graph[v]:       # 나랑 연결된 것 중에서 
    if not visited[i]:     # 방문하지 않은 곳이 있다면 
      dfs(graph,i,visited) # 방문한다. 


graph = [
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

visited = [False]*9 

dfs(graph,1,visited)

 

결과 : 1 2 7 6 8 3 4 5 

 

 

2. BFS : 너비 우선 탐색 , 가까운 노드 부터 탐색하는 알고리즘. 시간복잡도는 O(N) 

큐 자료구조를 이용하여 구현한다. 

from collections import deque 

def bfs(graph, start, visited ):
  queue = deque([start])
  visited[start] = True 

  while queue:
    v = queue.popleft()
    print(v, end=' ')

    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True 

graph = [
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

visited = [False]*9
bfs(graph, 1, visited )

결과 : 1 2 3 8 7 4 5 6