여기서 우리는 그래프의 DFS 및 BFS 알고리즘의 다른 응용 프로그램이 무엇인지 볼 것입니다.
DFS 또는 깊이 우선 탐색은 여러 곳에서 사용됩니다. 몇 가지 일반적인 용도는 -
- 무가중 그래프에서 DFS를 수행하면 모든 쌍의 최단 경로 트리에 대한 최소 스패닝 트리가 생성됩니다.
- DFS를 사용하여 그래프에서 주기를 감지할 수 있습니다. BFS 동안 하나의 백 에지를 얻는다면 하나의 주기가 있어야 합니다.
- DFS를 사용하여 주어진 두 정점 u와 v 사이의 경로를 찾을 수 있습니다.
- 우리는 작업 간의 주어진 종속성에서 작업을 예약하는 데 사용되는 토폴로지 정렬을 수행할 수 있습니다. 위상 정렬은 DFS 알고리즘을 사용하여 수행할 수 있습니다.
- DFS를 사용하여 그래프의 강하게 연결된 구성 요소를 찾을 수 있습니다. 각 꼭짓점에서 다른 모든 꼭짓점으로 가는 경로가 있다면 그것은 강하게 연결되어 있습니다.
DFS와 마찬가지로 BFS(Breadth First Search)도 다양한 상황에서 사용됩니다. 다음과 같습니다 -
- bit-torrent와 같은 P2P 네트워크에서 BFS는 모든 인접 노드를 찾는 데 사용됩니다.
- 검색 엔진 크롤러는 BFS를 사용하여 색인을 작성합니다. 소스 페이지에서 시작하여 새 페이지를 가져오기 위해 모든 링크를 찾습니다.
- GPS 네비게이션 시스템을 사용하여 BFS는 주변 장소를 찾는 데 사용됩니다.
- 네트워킹에서 일부 패킷을 브로드캐스트하려면 BFS 알고리즘을 사용합니다.
- 경로 찾기 알고리즘은 BFS 또는 DFS를 기반으로 합니다.
- BFS는 네트워크에서 최대 흐름을 찾기 위해 Ford-Fulkerson 알고리즘에서 사용됩니다.