Алгоритмы решения задач на графах.

Поиск в ширину: метод обхода и разметки вершин графа.

Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д. 

Поиск в глубину: один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.

Поиск по первому наилучшему совпадению: это алгоритм поиска, который исследует граф путём расширения наиболее перспективных узлов, выбираемых в соответствии с указанным правилом. Некоторые авторы использовали поиск «Лучший — первый» специально для описания поиска с эвристикой, чтобы попытаться предсказать, насколько близко находимся к финальному состоянию, так что пути, которые имеют лучшую эвристическую оценку, рассматриваются первыми. Этот специфический тип поиска называется жадным поиском «Лучший — первый».

Ещё существуют алгоритмы поиска A*, Беллмана–Форда, Дейкстры, Джонсона, Флойда - Уоршелла, двунаправленный поиск.

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.