Ответ
Взвешенный граф — это граф (набор вершин и рёбер), в котором каждому ребру (а иногда и вершине) присвоено числовое значение, называемое весом.
Для чего нужны веса? Веса могут представлять:
- Стоимость проезда между городами.
- Расстояние.
- Время в пути.
- Пропускную способность сети.
Пример представления взвешенного графа (список рёбер) на Swift:
struct Edge<T> {
let source: T // Исходная вершина
let destination: T // Целевая вершина
let weight: Double // Вес ребра
}
class WeightedGraph<T: Hashable> {
var adjacencyList: [T: [(destination: T, weight: Double)]] = [:]
func addEdge(from source: T, to destination: T, weight: Double) {
adjacencyList[source, default: []].append((destination, weight))
// Для неориентированного графа добавить обратное ребро:
// adjacencyList[destination, default: []].append((source, weight))
}
}
// Использование
let roadGraph = WeightedGraph<String>()
roadGraph.addEdge(from: "Москва", to: "Санкт-Петербург", weight: 705.0)
roadGraph.addEdge(from: "Москва", to: "Казань", weight: 815.0)Ключевые алгоритмы для взвешенных графов:
- Алгоритм Дейкстры: Находит кратчайший путь от одной вершины до всех остальных (не работает с отрицательными весами).
- Алгоритм Беллмана-Форда: Находит кратчайшие пути, допуская отрицательные веса (обнаруживает циклы отрицательного веса).
- Алгоритмы Прима и Крускала: Используются для нахождения минимального остовного дерева (подграфа, соединяющего все вершины с минимальным суммарным весом рёбер).
Почему это важно? Взвешенные графы являются фундаментальной моделью для решения реальных задач оптимизации в навигации, сетевом планировании, логистике и анализе социальных сетей.