DFS 구현하기

위와 같은 그래프를 DFS로 구현해보자.

 

인접행렬로 풀기

matrix = [
  [0,1,1,0,0,0,0,1],
  [1,0,0,0,0,0,1,0],
  [1,0,0,1,1,0,0,0],
  [0,0,1,0,1,0,0,0],
  [0,0,1,1,0,0,0,0],
  [0,0,0,0,0,0,1,0],
  [0,1,0,0,0,1,0,1],
  [1,0,0,0,0,0,1,0]
]
path = []
visit = [0]*20

def DFS(now):
  path.append(now+1)

  for i in range(8):
    if matrix[now][i] == 1 and visit[i] == 0:
      visit[i] = 1
      DFS(i)

visit[0] = 1
DFS(0)
print(path)

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