그래프 순회

그래프 순회

그래프 순회란 그래프 탐색이라고도 불리며 그래프의 각 정점을 방문하는 과정을 이야기한다. 그래프 순회에는 크게 깊이 우선 탐색과 너비 우선 탐색의 두가지 알고리즘이 있다.

BFS

graph = {
		'A': ['B', 'D', 'E'],
		'B': ['A', 'C', 'D'],
		'C': ['B'],
		'D': ['A', 'B'],
		'E': ['A']
}

너비 우선 탐색을 그래프를 가까운데 부터 탐색한다는 것이다.

탐색 순서

a → b→ d → e → c

너비 우선 탐색을 구현한 코드

from collections import deque

# start_v : 시작노드
def bfs(graph, start_v):
  visited = [start_v]
  
  # 사전세팅 : 가장 처음에 있는 노드를 큐에 집어넣는다.
  queue = deque(start_v)
  
  # 큐가 있으면 순회
  while queue:
    # 큐가 있다면 해당 큐를 디큐 시킨다.
    cur_v = queue.popleft()
    
    # 그래프 딕션어리에 있는 리스트들(연결된 애들)을 한번씩 방문할거임
    for v in graph[cur_v]:
      # 처음 vertex에 연결된 애가 아직 visited 리스트에 없다면
      # 만약 한번 방문을 했다면 visited에 들어가있기 때문에 다시 방문하지 않는다.
      if v not in visited:
        # visited리스트에 넣는다(방문했다는 것)
        # 여기까지 예를들어서 A노드가 처음에 있다면 연결된 B D E 중에 B를 먼저 방문한다.
        visited.append(v)
        # 그리고 바로 위에서 방문했던 노드를 큐에 넣어준다(방문 대기열)
        queue.append(v)
  return visited

DFS

간단한 코드

graph = {...}
visited = []

def dfs(cur_v):
  visited.append(cur_v)
  for v in graph[cur_v]:
    if v not in visited:
      dfs(v

원조 코드

graph = {...}

def dfs(graph, cur_v, visited = []):
    visited.append(cur_v)
    for v in graph[cur_v]:
      if v not in visited:
        visited = dfs(graph, v, visited)
    return visited

트리랑 원리가 거의 똑같아서 따로 주석으로 설명은 안적었음 재귀적으로 본인 자식 본인이 해결하는 방식임