그래프 탐색

탐색: 원하는 데이터를 찾는 과정
그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식
크게 DFS, BFS가 존재

• DFS(Depth First Search)
  깊이 우선 탐색, 일반적으로 BFS에 비해 더 많이 쓰인다.
  주로 스택 OR 재귀로 구현한다.

• BFS(Breadth First Search)
  너비 우선 탐색 우선 탐색
  DFS에 비해 잘 안쓰이지만 최단 경로를 찾는 다익스트라 알고리즘 등에 매우 유용

그래프를 표현하는 방법

1. 인접 행렬
2. 인접 리스트: 파이썬 딕셔너리(출발 노드를 키, 도착 노드를 값으로 표현, 도착 노드는 여러 개가 될 수 있으므로 리스트 형태)

graph = {
    1: [2,3,4],
    2: [5],
    3: [5],
    4: [],
    5: [6,7],
    6: [],
    7: [3],
}

DFS(Depth First Search)

• 재귀

# 수도코드
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(Breadth First Search)

• 큐를 이용한 반복 구조

# 수도 코드
# 모든 인접 간선을 추출하고 도착점인 정점을 큐에 삽입
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

• BFS는 재귀 사용 불가

reference

파이썬 알고리즘 인터뷰