Julie의 Tech 블로그

그래프는 인접행렬(Adjacency Matrix) 또는 인접 리스트(Adjacency List)로 표현된다. 이 그래프들을 주로 input으로 받아 순회하는 알고리즘을 통해 문제를 해결해야하는 경우가 생긴다.오늘은 그래프 순회 알고리즘의 Python 구현 코드와 개념에 대해 간단히 다뤄보려고 한다.그래프 순회는 크게 깊이우선탐색(BFS), 너비우선탐색(DFS)로 나뉜다. 대부분의 알고리즘 문제들은 DFS로 해결이 되는 편이긴 하나 그래프의 최단 경로를 구하는 경우 BFS 알고리즘을 사용할 때도 있다.DFS는 주로 스택을 활용하거나 재귀를 통해 구현되며, BFS는 큐로 구현된다.이 그래프를 예시로 살펴보자.# 그래프는 인접 리스트로 표현graph = [ [], # 0번 노드는 사용하지 ..