Какие из этих алгоритмов обхода графа чаще всего используются на практике?

Question

[MegaMufa]

Добрый день.

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

Подскажите, кто в теме, какие из этих алгоритмов встречаются чаще всего?

- Поиск в глубину [DFS] (https://ru.wikipedia.org/wiki/Поиск_в_глубину)
- Поиск в глубину с метками времени (https://goo.gl/d06ZIv)
- Поиск с ограничением глубины [DLS] (https://goo.gl/skcOuD)
- Поиск в глубину с итеративным углублением [IDDFS, DFID] (https://goo.gl/KTQF8q)
- Поиск в ширину [BFS] (https://ru.wikipedia.org/wiki/Поиск_в_ширину)
- Поиск по критерию стоимости [UCS] (https://goo.gl/pwKw3Z)
- Алгоритм Дейкстры (https://ru.wikipedia.org/wiki/Алгоритм_Дейкстры)
- Алгоритм Ли/Алгоритм волновой трассировки (https://ru.wikipedia.org/wiki/Алгоритм_Ли)
- Двунаправленный поиск (https://ru.wikipedia.org/wiki/Двунаправленный_поиск)
- Алгоритм Беллмана — Форда (https://ru.wikipedia.org/wiki/Алгоритм_Беллмана_—_...
- Алгоритм Левита (https://ru.wikipedia.org/wiki/Алгоритм_Левита)
- Алгоритм Флойда — Уоршелла (https://ru.wikipedia.org/wiki/Алгоритм_Флойда_—_Уо...
- Алгоритм Джонсона (https://ru.wikipedia.org/wiki/Алгоритм_Джонсона)
- Поиск по первому наилучшему совпадению (https://ru.wikipedia.org/wiki/Поиск_по_первому_наи...
- Поиск A*(https://ru.wikipedia.org/wiki/Алгоритм_поиска_A*)
- Алгоритм A* с итеративным углублением [IDA*] (https://ru.wikipedia.org/wiki/Информированный_мето...

Answer 1

[uvelichitel]

Обход делают или в глубину или в ширину, одинаково часто. Когда обходят в глубину можно применять или не применять стек для сохранения и восстановления пути.
Остальные приведенные ссылки - это алгоритмы поиска в которых применяется один из указанных двух методов обхода.

Comments

[MegaMufa]

Разве A* или Дейкстры является подвидом одного из них?

[uvelichitel]

Дейкстра обходит в ширину, А* в глубину со стеком. Обход в ширину или в глубину не есть алгоритм поиска, а только метод обхода.