Расстояние между вершинами
Расстояние между двумя вершинами невзвешенного графа — это минимальное число рёбер, которые нужно пройти по пути из одной вершины в другую. Если пути между вершинами нет, расстояние считают бесконечным или говорят, что оно не определено.
Граф называют невзвешенным, если все его рёбра считаются одинаковыми: переход по любому ребру увеличивает длину пути на 1. Поэтому расстояние измеряется не в километрах и не в условных единицах, а в рёбрах.
Пусть из вершины \(A\) можно попасть в \(B\) по маршрутам \(A-C-B\) и \(A-D-E-B\). Первый маршрут содержит 2 ребра, второй — 3. Значит, \(d(A,B)=2\). Если между \(A\) и \(B\) есть ещё прямое ребро, расстояние станет равным 1.
Расстояние — это длина самого короткого пути, а не число всех возможных путей. Кратчайший путь является маршрутом, на котором это расстояние достигается. Также расстояние между вершинами не следует путать с диаметром графа: диаметр — наибольшее расстояние среди всех пар вершин.
Для поиска расстояний в невзвешенном графе обычно используют обход в ширину (BFS). Сначала посещают исходную вершину, затем все вершины на расстоянии 1, потом на расстоянии 2 и так далее. Поэтому первый найденный путь до вершины имеет минимальную длину.
В графе есть путь \(A-B-C-D\) и путь \(A-E-D\). Чему равно расстояние между \(A\) и \(D\)?
Главное
- Расстояние между вершинами — минимальное число рёбер на пути между ними.
- В невзвешенном графе каждое ребро имеет длину 1.
- Для нахождения расстояний от одной вершины используют обход в ширину; наибольшее из расстояний связано с диаметром графа.