MONG 기술블로그

그래프 관련 주요 용어와 그래프의 대표 순회 알고리즘인 DFS. BFS에 대해서 간단히 정리해보자. 그래프 순회 알고리즘 DFS 깊이 우선 탐색 ( Depth First Search ) 스택 혹은 재귀로 구현하며 대부분의 그래프 순회 문제에서 사용한다. BFS 너비 우선 탐색 ( Breadth First Search ) 큐를 이용하여 구현하며, 특정 Vertex로부터의 최단 거리를 구하는 문제에서 사용한다. 그래프 표현 방법 인접 행렬 혹은 인접 리스트를 이용하여 표현하며 하기 코드는 인접 리스트를 Python 딕셔너리를 통해 표현한 예시이다. graph = { 1: [2,3,4], 2: [5], 3: [4,5,6] } 그래프 순회 알고리즘 구현 각 구현에서 방문 확인 & 추가를 하는 위치가 알고리즘상 ..