Depth-First Search

DFS는 깊이 우선 탐색 방법입니다. 하나의 경로를 끝까지 탐색한 후 원하는 값이 없을 경우 다음 경로로 넘어가 탐색을 시작합니다. 탐색 시간이 오래 걸리지만 모든 노드를 탐색할 수 있습니다. 만약 원하는 값이 시작하는 정점의 반대쪽에 있다면 시간이 오래 걸릴 수 있습니다. 원하는 값의 위치가 깊이가 깊을 경우 사용하는 게 좋을 것 같습니다.

정점들과 이어진 간선들이 인자로 주어지고 연결된 정점의 컴포넌트의 수를 숫자로 반환하는 함수의 DFS 로직으로 인접행렬을 활용하여 만들었습니다.

1. 정점의 개수를 구합니다.(인접행렬을 만들기 위해)
2. 인접 행렬을 만든다. 이차원배열로 만들어진 인접 행렬에 정점끼리 이어진 간선을 1로 표시합니다.
3. 인접 행렬 전체를 도는 for문을 만들어서 간선이 존재하고, 해당 정점을 방문한 적이 없으면 DFS함수를 돌고 끝까지 다돌고 나온다면 간선이 끝난 것이기 때문에 간선으로 연결된 하나의 컴포넌트가 끝났다고 봐도 무방합니다. 그러므로 카운트를 세어줍니다.
4. 해당 정점을 방문한 적이 없으면 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 순서로 탐색을 합니다.

아직 정확한 이해는 하지 못했지만 반복해서 확인하면서 글을 수정하겠습니다.