그래프가 하나의 비선형 데이터 구조라는 것을 알고 있습니다. 이 데이터 구조에서 우리는 일부 값을 노드에 입력하고 노드는 다른 가장자리를 통해 연결됩니다. 데이터를 그래프 구조에 저장할 수 있으므로 그래프에서 요소를 검색하여 사용할 수도 있습니다.
그래프 검색에는 두 가지 방법이 있습니다. 너비 우선 탐색과 깊이 우선 탐색 기법.
너비 우선 검색(BFS)
BFS(Breadth First Search) 탐색은 주어진 그래프의 모든 노드를 방문하는 데 사용되는 알고리즘입니다. 이 탐색 알고리즘에서는 하나의 노드를 선택한 다음 모든 인접 노드를 하나씩 방문합니다. 인접 정점을 모두 완성한 후, 다른 정점을 확인하기 위해 더 이동하고, 인접 정점을 다시 확인한다. 이 알고리즘을 구현하려면 Queue 데이터 구조를 사용해야 합니다. 인접한 모든 정점이 완료되면 모든 인접 정점이 대기열에 추가되고, 한 항목이 대기열에서 제거되고 해당 정점을 다시 통과하기 시작합니다.
깊이 우선 탐색(DFS)
DFS(깊이 우선 탐색)는 그래프 탐색 알고리즘입니다. 이 알고리즘은 하나의 시작 정점이 주어지고 인접 정점이 발견되면 그 인접 정점으로 먼저 이동하고 같은 방식으로 순회를 시도한다. 가능한 한 전체 깊이를 이동한 다음 역추적하여 이전 정점에 도달하여 새 경로를 찾습니다.
반복적인 방식으로 DFS를 구현하려면 스택 데이터 구조를 사용해야 합니다. 재귀적으로 수행하려면 외부 스택이 필요하지 않으며 재귀 호출에 대해 내부 스택을 수행할 수 있습니다.