그래프의 인접 리스트 방식에서의 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)이다.
일단 bfs의 경우 queue
dfs의 경우 stack을 꼭 기억하기로 했다.
우선 bfs부터 보겠다.
function DFS(graph, nowNode){
let visitedNode = [];
let needVisiteNode = [];
needVisiteNode.push(nowNode);
while(needVisiteNode.length !== 0){
let checkNode = needVisiteNode.pop();
if(!visitedNode.includes(checkNode)){
visitedNode.push(checkNode);
needVisiteNode = [...needVisiteNode, ...graph[checkNode]];
}
}
return visitedNode
}- 그래프와 시작할 노드 위치를 지정하여 DFS 함수 실행
- needVisiteNode에 시작 노드를 push
- while문을 돌면서 pop()를 통해 checkNode에 할당한다.
- 만약 visitedNode안에 checkNode값이 없을 경우, checkNode값을 visiteNode에 집어 넣고, neeVistieNode에 아직 체크하지 못했던 needVisiteNode값과 checkNode에 해당하는 그래프 내의 값들을 집어넣어준다.
해당 과정을 needVisiteNode가 전부 사라질 때 까지 반복한다.
const graph = {
A: ["B","D","C"],
B: ["A","D"],
C: ["A", "D"],
D: ["B","A","C"],
};이러한 그래프를 예시로 들면 과정은 다음과 같다.
B노드에서 시작을 한다고 가정했을 때,
첫 번째 순회: checkNode에 needVisteNode값을 푸쉬해준다(첫 바퀴에는 nowNode와 같다.) visitedNode는 아직 빈 배열이므로 visitedNode에 'B'를 push해준다. 이후 needVisiteNode에 'B'와 graph[checkNode]값인 'A,D'를 추가해준다.
두 번째 순회: checkNode에 needVisiteNode의 pop()값인 D를 넣고
위 과정을 반복하면 visitedNode에는 [ 'B', 'D' ], needVisiteNode에는 [ 'A', 'B', 'A', 'C' ]이 들어가게 된다.
세 번째 순회: 다음 차례인 C가 visitedNode에 들어가게 되고
visitedNode엔 [ 'B', 'D', 'C' ], needVisiteNode엔 [ 'A', 'B', 'A', 'A', 'D' ]
값이 들어가게 된다.
네 번째 순회: visitedNode [ 'B', 'D', 'C', 'A' ], needVisiteNode [ 'A', 'B', 'A', 'B', 'D', 'C' ]
다섯 번째 순회: needVisiteNode에 [ 'A', 'B', 'A', 'B', 'D', 'C' ]값이 존재하지만
!visitedNode.includes(checkNode) 구문에서 이미 모두 방문했던 노드이므로 과정이 생략되고 visitedNode값인 ['B','D','C','A'] 부분만 남게되며 dfs가 종료된다.
bfs는 dfs 구현과 매우 흡사하지만 딱 하나 차이점이 있었다. pop 대신 shift를 사용한다는 점...
function BFS(graph, nowNode){
let visitedNode = [];
let needVisiteNode = [];
needVisiteNode.push(nowNode);
while(needVisiteNode.length !== 0){
let checkNode = needVisiteNode.shift();
if(!visitedNode.includes(checkNode)){
visitedNode.push(checkNode);
needVisiteNode = [...needVisiteNode, ...graph[checkNode]];
}
}
return visitedNode
}기본적인 골자는 같지만 visitedNode안에 checkNode를 push할 때 배열의 가장 뒷 부분에서가 아닌 가장 앞 부분에서 가져오게 된다.shift()
bfs의 경우 각 노드들의 레벨 단계마다 확인을 하며 확장해나간다.
따라서 특정 노드에서 다른 특정 노드까지의 최단 거리를 확인하는데 유리하다.
반면 dfs의 경우 연결된 노드 말단까지 찍고 다음 노드를 확인하기 때문에, 내가 도착한 마지막 노드까지의 경로가 반드시 최단거리가 되지는 않는다.
다만 bfs의 경우 각 노드들을 거치면서 해당 경로들을 따로 저장해야할 소요가 존재하지만,
dfs는 해당 경로를 쭉 진행하면서 해당하는 경로의 노드 들만 기억하면 되므로 메모리의 필요가 덜하다는 장점이 존재한다.
그리고 만약에... 정말 만약에 내가 찾고자하는 노드가 가장 말단에 위치 할 경우(또한 탐색 방향과 방향이 일치할 경우) bfs에 비해서 찾는 속도가 빠를 수도 있다.(조건이 많이 붙긴 합니다만...)
아래 주소는
해당 로직을 참고했던 블로그이다!
덕분에 이해가 잘 되었습니다. 감사합니다 잘 봤어요 최고
