탐색: 원하는 데이터를 찾는 과정
그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식
크게 DFS, BFS가 존재
DFS(Depth First Search)
깊이 우선 탐색, 일반적으로 BFS에 비해 더 많이 쓰인다.
주로 스택 OR 재귀로 구현한다.
BFS(Breadth First Search)
너비 우선 탐색 우선 탐색
DFS에 비해 잘 안쓰이지만 최단 경로를 찾는 다익스트라 알고리즘 등에 매우 유용
graph = {
1: [2,3,4],
2: [5],
3: [5],
4: [],
5: [6,7],
6: [],
7: [3],
}
# 수도코드
DFS(G, v)
label v as discovered
for all directed edges from v to w that are in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G, w)
# 파이썬 코드
def recursive_dfs(v, discovered=[]):
discovered.append(v)
for w in graph[v]:
if not w in discovered:
discovered = recursive_dfs(w, discovered)
# 방문했던 정점을 누적한다.
return discovered
# 수도 코드
DFS-iterative(G, v)
let S be a stack
S.push(v)
while S is not empty do
v = S.pop()
if v is not labeled as discovered then
label v as discovered
for all edges from v to w in G.adjacentEdgeds(v) do
S.push(w)
# 파이썬 코드
def iterative_dfs(start_v):
discovered = []
stack = [start_v]
while stack:
v = stack.pop()
if v not in discovered:
discovered.append(v)
# 스택을 이용해 모든 인접 간선 추출
for w in graph[v]:
stack.append(w)
return discovered
# 수도 코드
# 모든 인접 간선을 추출하고 도착점인 정점을 큐에 삽입
BFS(G, start_v):
let Q be a queue
label start_v as discovered
Q.enqueue(start_v)
while Q is not empty do
v := Q.dequeue()
if v is the goal then
return v
for all edges from v to w in G.adjacentEdges(v) do
if w is not labeled as discovered then
label w as discovered
w.parent := v
Q.enqueue(w)
# 파이썬 코드
def iterative_bfs(start_v):
discovered = [start_v]
queue = [start_v]
while queue:
v = queue.pop(0)
for w in graph[v]:
if w not in discovered:
discovered.append(w)
queue.append(w)
return discovered