Song 컴퓨터공학

너비 우선 탐색, BFS 이란? BFS 란 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. BFS는 큐를 사용해 구현하며 DFS와 마찬가지로 인접 행렬로 표현된 그래프와 인접 리스트로 표현된 그래프의 경우 조금 달라집니다. 오늘 포스팅에서는 BFS 의 동작을 단계별로 이해해보고 인접 행렬로 표현된 그래프에 적용할 수 있는 BFS 코드를 구현해보겠습니다. BFS 도 DFS와 마찬가지로 시간 복잡도는 인접 행렬인지 인접 그래프로 표현되었는지에 따라 달라지게 되는데 인접 행렬의 경우 O(n^2), 인접 그래프의 경우 O(n+e) 가 됩니다. BFS의 구현에 있어서 큐는 반드시 알아야 하기 때문에 큐의 개념이 헷갈리신다면 아래의 포스팅을 참고해주세요. [..

깊이 우선 탐색, DFS 이란? DFS 란 트리에서 생각해보면 트리를 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 매우 유사합니다. 즉 DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법입니다. DFS 는 스택을 사용해 구현합니다. 아래의 동작과 구현에서 확인하겠지만, 깊이 우선 탐색을 통해 그래프를 탐색하게 되면 모든 간선을 조사하므로 정점의 수가 n 이고 간선의 수가 e인 그래프인 경우, 그래프가 인접 행렬로 표시되어 있다면 O(n^2), 인접 리스트로 표현되어 있는 경우는 O(n+e) 가 됩니다. 따라서 희소 그래프인 경우는 DFS는 인접 리스트의 사..