-깊이 우선 탐색(DFS)이란? 그래프의 순회 방식에는 두 가지가 존재한다. 첫 번째는 깊이 우선 탐색(DFS) 두 번째는 너비 우선 탐색(BFS). 이러한 방식들은 기본적으로 그래프를 구성하고 있는 모든 노드들을 한 번씩 반드시 방문하게 되며 이를 그래프의 순회라고 한다. 그중 깊이 우선 탐색은 아래와 같은 순서를 따른다. 시작 정점(V)을 방문한다. V에 인접한 정점들 중 방문하지 않은 정점을 방문하며 스택(Stack)에 삽입한다. 인접한 정점이 없는 정점까지 2번을 반복한다. 이후 인접한 정점이 없는 경우 다시 스택에서 pop() 후 2~3번을 반복한다. 즉 깊이 우선 탐색의 경우에는 인접한 정점이 없는 정점에 도달할 때까지 인접한 정점을 반복해서 방문하며 Stack에 넣는 작업을 한다. 깊이 우선..

-너비 우선 탐색(BFS)란? 그래프의 순회 방식에는 두 가지가 존재한다. 첫 번째는 깊이 우선 탐색(DFS) 두 번째는 너비 우선 탐색(BFS). 이러한 방식들은 기본적으로 그래프를 구성하고 있는 모든 노드들을 한 번씩 반드시 방문하게 되며 이를 그래프의 순회라고 한다. (또한 너비 우선 탐색은 두 정점 사이의 최단 거리를 구하거나 임의의 경로를 구할 때 사용한다고 하는데, 필자도 현재까지는 단순한 구현과 개념의 이해정도 수준에 그치기 때문에 후에 추가적으로 작성할 예정이다.) 그중 너비 우선 탐색은 아래와 같은 순서를 따른다. 시작 정점(V)을 방문한다. V에 인접한 정점들 중 방문하지 않은 정점을 차례로 방문하며 큐(Queue)에 삽입한다. 인접한 정점을 모두 방문했다면, 큐에 삽입했던 정점을 반환..