그래프 탐색

[그래프 탐색] DFS와 BFS

그래프 탐색 📌 개념 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종 그래프를 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다. → 모든 노드를 방문하고자 하는 경우에 이 방법을 선택 DFS (Depth First Search) : 깊이 우선 탐색 📌 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. - 스택이나 재귀를 사용하여 구현 📌 그림으로 보기 STEP 1: A를 시작노드로 하겠습니다. STEP 2: A에 인접한 B, C가 스택에 저장됩니다. STEP 3: 스택의 맨 위에 있는 C를 꺼내서 Visited 배열에 넣습니다. ..