비선형 구조인 그래프 구조는 표현된 모든 자료를 빠짐없이 탐색하는 것이 중요
1. DFS
2. BFS
"내가 다시 돌아올 곳을 저장"
- 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 계속 반복 탐색하여, 모든 정점을 탐색한다.
- 스택의 후입선출 구조 또는 재귀호출을 통해서 구현하게 됩니다
graph = {}
graph['A'] = ['B', 'C']
graph['B'] = ['D', 'F']
A B C D E F
A 0 1 1 0 0 0
B 0 0 0 1 0 1
C 1 0 0 0 0 0
D 0 1 0 0 0 0
E 0 0 0 0 0 0
F 0 1 0 0 0 0
V, E = map(int,input().split()) # 정점 개수, 간선 개수
arr = [[0]*(V+1) for _ in range(V+1)]
visited = [0] * (V+1) # 방문 체크용
for _ in range(E):
n1, n2 = arr[i*2], arr[i*2+1]
arr[n1][n2] = 1 # n1과 n2는 인접하다
def dfs(v):
visited[v] = 1
# 현재 v는 시작 정점, 인접한 정점 중 방문을 안한 곳
for w in range(1,V+1):
if arr[v][w] == 1 and visited[w] == 0:
dfs(w)
dfs(1)
def dfs(v):
stack = [v]
# stack.append(v)
# 스택이 빌 때까지 반복
while len(stack):
v = stack.pop()
# v가 아직 방문 전이라면
visited[v] = 1
for w in range(1, v+1):
if arr[v][w] == 1 and visited[w] == 0 :
stack.append(w)