Depth-First Search
DFS는 깊이 우선 탐색 방법입니다. 하나의 경로를 끝까지 탐색한 후 원하는 값이 없을 경우 다음 경로로 넘어가 탐색을 시작합니다. 탐색 시간이 오래 걸리지만 모든 노드를 탐색할 수 있습니다. 만약 원하는 값이 시작하는 정점의 반대쪽에 있다면 시간이 오래 걸릴 수 있습니다. 원하는 값의 위치가 깊이가 깊을 경우 사용하는 게 좋을 것 같습니다.
정점들과 이어진 간선들이 인자로 주어지고 연결된 정점의 컴포넌트의 수를 숫자로 반환하는 함수의 DFS 로직으로 인접행렬을 활용하여 만들었습니다.
- 정점의 개수를 구합니다.(인접행렬을 만들기 위해)
- 인접 행렬을 만든다. 이차원배열로 만들어진 인접 행렬에 정점끼리 이어진 간선을 1로 표시합니다.
- 인접 행렬 전체를 도는 for문을 만들어서 간선이 존재하고, 해당 정점을 방문한 적이 없으면 DFS함수를 돌고 끝까지 다돌고 나온다면 간선이 끝난 것이기 때문에 간선으로 연결된 하나의 컴포넌트가 끝났다고 봐도 무방합니다. 그러므로 카운트를 세어줍니다.
- 해당 정점을 방문한 적이 없으면 DFS함수를 실행합니다.
4-1. DFS함수 로직으로 방문한 적이있다는 의미로 따로 객체를 생성하여 true값을 줍니다.
4-2. 그리고 다시 간선으로 연결된 정점이 있는지 확인하고, 방문한 적이 없다면 다시 DFS함수를 실행하는 재귀함수의 형태로 만듭니다.
Breadth-First Search
BFS는 너비 우선 탐색 방법입니다. BFS는 얕게 탐색하는 방법으로 시작하는 정점으로부터 가까운 정점 부터 탐색합니다. 깊은 트리에서 BFS를 사용하게 된다면 굉장히 비효율적인 탐색방법이 될 수도 있습니다. 트리의 깊이가 얕다고 판단될 때 사용하는게 좋을 것 같습니다.
[2021/3/13_로직 추가]
1-3번까지는 DFS와 동일합니다
4. 해당 정점을 방문한 적이 없으면 BFS함수를 실행합니다.
4-1. 해당 정점을 방문하고 객체를 생성하여 true값을 할당합니다. 그리고 해당 정점에서부터 이어진 간선이 있는지 확인합니다. 인접 리스트는 길이를 측정하면 간선의 개수를 측정가능하고, 인접 행렬은 만약 정점 1의 간선개수를 알고싶다면 obj[1][i]에서 i의 개수를 구하면 간선의 수를 알 수 있습니다.
4-2. A로부터 간선으로 이어진 정점들을 반복문으로 방문하면서 이전에 방문한 적이 없다면 true값을 할당하고 여러 정점들의 값을 저장합니다. 하나의 정점(A)으로 부터 이어진 정점들의 방문이 끝났다면
같은층의 정점들을 다 들렀다는 의미입니다. 이제 하위노드 들이있다면 다시 반복문으로 하나씩 들러서 반복하면서 값을 찾아가면 됩니다.
1
2 3
4 5 6 7이런 형태라면 BFS는 1-2-3-4-5-6-7 순서대로 탐색을 하고, DFS는 1-2-4-5-3-6-7 순서로 탐색을 합니다.
아직 정확한 이해는 하지 못했지만 반복해서 확인하면서 글을 수정하겠습니다.
