ЬЗВЕШЕННЫЙ ГРАФ
НЕВЗВЕШЕННЫЙ ГРАФ
раф с весами называется взвешенным графом. Граф без весов называется невзвешенным графом.
Для вычисления кратчайшего пути в невзвешенном графе используется поиск в ширину. Кратчайшие пути во взвешенном графе вычисляются по алгоритму Дейкстры. В графах также могут присутствовать циклы:
Ц ИКЛ1 ПУТЬ,
НАЧИНАЮЩИЙСЯ С УЗЛА®,
ААОЖЕТ ВЕРНУТЬСЯ К УЗЛУ®
Э то означает, что вы можете начать с некоторого узла, перемещаться по графу, а потом снова оказаться в том же узле. Предположим, вы ищете кратчайший путь в графе, содержащем цикл.
Е сть ли смысл в перемещении по циклу? Что ж, вы можете использовать путь без прохождения цикла:
А
ОБЩИЙ
ВЕС:
можете пройти по циклу:
В ы в любом случае оказываетесь в узле А, но цикл добавляет лишний вес. Вы даже можете обойти цикл дважды, если вдруг захотите.
Но каждый раз, когда вы проходите по циклу, вы только увеличиваете суммарный вес на 8. Следовательно, путь с обходом цикла никогда не будет кратчайшим.
Н
НАПРАВЛЕННЫЙ
ГРАФ
НЕНАПРАВЛЕННЫЙ
ГРАФ
аконец, вы еще не забыли наше обсуждение направленных и ненаправленных графов из главы 6?
С
Do'stlaringiz bilan baham: |