그래프 깊이우선탐색(DFS), 너비우선탐색(BFS)

# 구현

import sys  
# 그래프
# 1 ----- 2 ----- 6
#  \     / \     /
#   \   /   4 - 5
#    \ /   / \  
#     3 - 7 - 8 - 9
 
# 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> 6 -> 8 -> 9 
 
# 9 12 (노드갯수, 간선정보)
# 1 2
# 1 3
# 2 3
# 2 4
# 2 6
# 3 7
# 4 5
# 4 7
# 4 8
# 5 6
# 7 8
# 8 9
def DFS(x):
  global myGraph, visited, n, m
  # x부터 시작해서 DFS하여 그 순서를 출력하는 함수.
  # 단, visited에 방문 기록이 있음
  visited[x] = True
  print(x, end=' ')
  # myGraph[x]
  for i in range(len(myGraph[x])):
    # x와 y가 연결이 되어 있다.
    y = myGraph[x][i]
    if not visited[y]:
      DFS(y) 
      
if __name__ == "__main__":
  input   = sys.stdin.readline
  
  n, m    = map(int, input().split())
  myGraph = [[] for _ in range(n+1)]
  visited = [False]*(n+1)
  
  for i in range(m):
    a, b = map(int, input().split())
    myGraph[a].append(b)
    myGraph[b].append(a) 
  
  DFS(1) # 1부터 시작해서 DFS한 결과를 출력

입력
9 12
1 2
1 3
2 3
2 4
2 6
3 7
4 5
4 7
4 8
5 6
7 8
8 9

출력
1 2 3 7 4 5 6 8 9 

 

- 너비우선탐색 (Breadth First Search)

큐를 이용한 방법이다보니 이부분은 시뮬레이션을 통해 보는 것이 좀 더 이해하기가 수월하다.

 

https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/visualize/

Breadth First Search visualize | Graphs | Algorithms | HackerEarth

 

#코드

import sys
from collections import deque
# 1 ----- 2 ----- 6
#  \     / \     /
#   \   /   4 - 5
#    \ /   / \
#     3 - 7 - 8 - 9
 
# DFS : 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> 6 -> 8 -> 9
# BFS : 1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 5 -> 8 -> 9
 
def BFS():
  global n, myGraph
  # 1.시작점을 큐에 삽입한다.
  deq   = deque()
  deq.append(1)
  # 2.시작점을 색칠한다.
  check    = [False]*(n+1)
  check[1] = True
  # --> BFS 시작!
  while deq:
    # 3.큐에서 하나를 뺀다. 여기가 실질적 시작점이다.
    current_v = deq.popleft()
    print(current_v,end=' ')
    # 4.인접한 모든 정점에게 방문했는지 물어보고
    #   방문을 하지 않았다면, 색칠하고 큐에 삽입한다.
    for i in range(len(myGraph[current_v])):
      next_v = myGraph[current_v][i] # current와 next는 연결돼 있다.
      if not check[next_v]:
        check[next_v] = True
        deq.append(next_v)
    # 5.모두 완료했다면 다시 3번으로 돌아간다. 
  
 
if __name__ == "__main__":
  input = sys.stdin.readline
       
  n, m    = map(int, input().split())
  myGraph = [[] for _ in range(n+1)]
  
  for i in range(m):
    a, b = map(int, input().split())
    
    myGraph[a].append(b)
    myGraph[b].append(a)
   
  BFS()
 

입력
9 12
1 2
1 3
2 3
2 4
2 6
3 7
4 5
4 7
4 8
5 6
7 8
8 9

출력
1 2 3 4 6 7 5 8 9