알고리즘/그래프
2020. 4. 29.
최단 경로
그래프에서 두 정점 사이의 최단 경로를 구하는 알고리즘에 대해 알아봅시다. BFS 간선의 가중치가 모두 1이라면(같다면), BFS를 이용해 한 정점에서 다른 정점들 사이의 최단 거리를 알 수 있습니다. 자세한 설명은 https://anz1217.tistory.com/21 그래프 탐색 (DFS, BFS) 그래프는 정점과 정점들을 잇는 간선들의 집합으로 이루어진 자료구조입니다. 이 글에서는 그래프를 저장하는 방법과, 그래프를 탐색하는 방법에 대해 알아보도록 합시다. 다음과 같은 그래프를 저장한다고 생각해.. anz1217.tistory.com 에서 볼 수 있습니다. 시간 복잡도는 \(O(|V|+|E|)\)입니다. 0-1 BFS 문제를 조금 확장해 봅시다. 간선의 가중치가 모두 0또는 1이라면 어떻게 최단 거..
