그래프

 

그래프 관련 주요 용어와 그래프의 대표 순회 알고리즘인 DFS. BFS에 대해서 간단히 정리해보자.

 그래프 순회 알고리즘

• DFS
  • 깊이 우선 탐색 ( Depth First Search )
  • 스택 혹은 재귀로 구현하며 대부분의 그래프 순회 문제에서 사용한다.
• BFS
  • 너비 우선 탐색 ( Breadth First Search )
  • 큐를 이용하여 구현하며, 특정 Vertex로부터의 최단 거리를 구하는 문제에서 사용한다.

 

그래프 표현 방법

• 인접 행렬 혹은 인접 리스트를 이용하여 표현하며 하기 코드는 인접 리스트를 Python 딕셔너리를 통해 표현한 예시이다.

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

 

그래프 순회 알고리즘 구현

각 구현에서 방문 확인 & 추가를 하는 위치가 알고리즘상 굉장히 중요하니 유의하자.

 

▶ DFS ( 재귀- 사전순 방문 )

# DFS - Recursive
def rec_dfs(v, visit):
    # Visit Add
    visit.append(v)
    for w in graph[v]:
    	# Visit Check
        # not in Visit -> Recursive 
        if w not in visit:
            rec_dfs(w,visit)
    return visit

 

 

▶ DFS ( 스택 - 사전 역순 )

# DFS - Stack
def rec_stk_dfs(v):
    visit = []
    stk = [v]
    while stk:
        now_v = stk.pop()
        # Visit Check
        # not in Visit -> Visit Add
        if now_v not in visit:
            visit.append(now_v)
            # Add Stack ( DFS Recursive 부분 )
            for w in graph[now_v]:
                stk.append(w)
    return visit

 

▶ BFS ( 큐 )

# BFS - Queue
def iter_bfs(start_v):
    # Visit Add & Queue Add
    visit = [start_v]
    queue = [start_v]
    while queue:
        now_v = queue.pop(0)
        # Not in Visit -> Visit Add & Queue Add
        for w in graph[now_v]:
            if w not in visit:
                visit.append(w)
                queue.append(w)
    return visit