반응형 DFS1 알고리즘 BFS 와 DFS 알고리즘 공부 해봤다면 그래프에서 모든 노드를 탐색하기 위한 기법으로 BFS와 DFS 를 들어봤을 것이다. 둘의 공통 목적으로는 다음과 같다.그래프의 탐색의 목적은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이다.그래프의 데이터는 배열처럼 정렬이 되어 있지 않다.그래프에서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 한다.탐색 방법은 아래 그림과 같다.모든 노드를 들려야해서 효율이 떨어질순 있지만 이부분은 백트래킹으로 해결이 가능하고 백트래킹에 대한 내용은 다음포스팅에 이어서 다뤄볼 예정이다. 특징BFS 에 대한 특징BFS 는 재귀적으로 동작하지 않는다.이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한.. 2022. 8. 4. 이전 1 다음 반응형
