2. 그래프 순회 | Graph Traversal
- 그래프의 모든 노드를 방문하는 일
- 대표적인 두 가지 방법: BFS, DFS
이미지 출처
2-1. 너비 우선 탐색 | Breadth-First Search(BFS)
- 큐를 이용한 너비우선순위
이미지 출처
BFS 최단경로
- 각 노드에 대해서 최단 경로의 길이를 구할 수 있음(거치는 엣지의 갯수)
- 입력: 방향 혹은 무방향 그래프 G=(V,E), 그리고 출발노드 S
- 출력: 모든 노드 V에 대해서
d[v] = s로 부터 v까지의 치단 경로의 길이(엣지의 개수)
π[v] = s로 부터 v까지의 최단경로상에서 v의 직전 노드(predecessor)
BFS 트리
- 각 노드 v와 π[v]를 연결하는 엣지들로 구성된 트리
- BFS 트리에서 S에서 V까지의 경로는 S에서 V까지 가는 최단경로
- 어떤 엣지도 2개의 layer를 건너가지 않음.
동일 레이어의 노드를 연결하거나, 혹은 1개의 layer를 건너감
2-2. 깊이 우선 탐색 | Depth-First Search(DFS)
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
- 자기 자신을 호출하는 순환 알고리즘의 형태
- 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것(그렇지 않을 경우 무한루프에 빠질 위험이 있음)
👨🏻💻 BFS 문제 풀이
[programmers] Lv3. 단어 변환 Javascript | DFS | protect-me
- 최단 경로를 찾을 때에는 BFS가 적합
👨🏻💻 DFS 문제 풀이
[programmers] Lv2. 타겟 넘버 Javascript | DFS(깊이우선탐색)
[programmers] Lv3. 네트워크 Javascript | DFS(재귀) | protect-me
[programmers] Lv3. 여행경로 Javascript | DFS+재귀+clone | protect-me
📚 참고
Photo by Michael Dziedzic on Unsplash
protect me from what i want