가중 그래프 및 애플리케이션

그래프는 각 모서리에 가중치가 할당된 가중치 그래프입니다. 가중치 그래프에는 실용적인 응용 분야가 많습니다.

위 그림은 그래프가 도시 간 항공편 횟수를 나타내는 것으로 가정합니다. BFS를 적용하여 두 도시 간 가장 적은 항공편 수를 찾을 수 있습니다. 아래 그림과 같이 모서리가 도시 간 주행 거리를 나타낸다고 가정합니다. 모든 도시를 연결하기 위한 최소 총 거리는 어떻게 구합니까? 두 도시 사이의 최단 경로를 어떻게 찾나요? 이 장에서는 이러한 질문을 다룰 것입니다. 전자를 최소 스패닝 트리(MST) 문제라고 하고, 후자를 최단 경로 문제라고 합니다.

이전 장에서는 그래프의 개념을 소개했습니다. 모서리 배열, 모서리 목록, 인접 행렬, 인접 목록을 사용하여 모서리를 표현하는 방법과 Graph 인터페이스, AbstractGraph 클래스 및 무가중 그래프 클래스. 이전 장에서는 또한 그래프 탐색을 위한 두 가지 중요한 기술인 깊이 우선 탐색과 너비 우선 탐색을 소개하고 실제 문제를 해결하기 위해 탐색을 적용했습니다. 다음 게시물에서는 가중치 그래프를 소개합니다. Post에서 최소 스패닝 트리를 찾는 알고리즘과 Post에서 최단 경로를 찾는 알고리즘을 배우게 됩니다.

위 내용은 가중 그래프 및 애플리케이션의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!