공부와 취미 사이 그 어딘가

깊이 우선 탐색(DFS)와 넓이 우선 탐색(BFS)에 대해 알아보려한다. 이 두가지 방법은 그래프를 탐색하는 방법에서 많이 사용한다. 그래프란? *그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문 하는 것을 말한다. ex) 특정 도시에서 다른 고시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 cf) 그래프와 트리의 차이를 알아보자! 더보기 대표적은 특징으로는, 그래프 중에서 방향성이 있는 비순환 그래프를 트리라고 한다. 1. 깊이 우선 탐색(DFS, Depth-First Search) : 루트 노드(혹은 다른 임의의 노드)에서 ..