목록너비 우선 탐색 (1)

미새문지

깊이 우선 탐색(DFS, depth-first search), 너비 우선 탐색(BFS, Breadth-first search)

깊이 우선 탐색(DFS, depth-first search) 깊이 우선 탐색(DFS)은 그래프의 모든 노드를 탐색하는데 사용되는 알고리즘 중 하나이다. 루트 노드에서 시작해 한 방향으로(주로 왼쪽부터) 들어갈 수 있는한 끝까지 탐색하여 더 이상 들어갈 수 없는 경우, 가장 최근의 분기점으로 돌아가 다른 방향의 노드를 탐색하는 방식으로 진행된다. DFS의 구현 // 그래프를 인접 리스트 형태로 표현 const graph = { A: ['B', 'C'], B: ['A', 'D', 'E'], C: ['A', 'F'], D: ['B'], E: ['B', 'F'], F: ['C', 'E'] }; // DFS 함수 정의 function dfs(graph, startNode) { let visited = []; //..
공부 키워드/알고리즘 및 데이터 구조 2024. 4. 2. 21:17
이전 Prev 1 Next 다음