Алгоритмы на графах

[wataru]

Текст надо перечитать, и вообще создается ощущение, что опубликовали черновик. Все секции "применение" какие-то обрезанные.

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

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

Начинать объяснение Дейкстры с очереди с приоритетом - это плохо и непонятно. Надо рассказать про Дейкстру, где просто берется минимальная вершина из необработанного множества и фиксируется. Надо показать пример, как в той же википедии. Уже потом можно делать анализ сложности и оптимизировать его через очередь с приоритетами.

Еще, у вас в Дейкстре неправильная оценка сложности. ваша реализация работает за O((V+E)Log E), потому что вершины в очереди дублируются.

В разнабой идут алгоритмы обхода и поиска кратчайшего пути. Никакой систематизации задач.

И вообще, вы определитесь - кто целевая аудитория вашего текста. На одном конце спектра есть олимпиадники и PhD по Computer Science, на другом - новички, вообще не знакомые с алгоритмами. Судя по набору базовых вещей, вы ориентируетесь на новичков. Но для них надо писать статьи совсем по-другому! Надо объяснять как, почему и откуда, а не что. Вот вы в секции "принцип работы" вместо объяснения принципа работы Дейксты приводите тупо алгоритм дейкстры, только записанный на русском языке вместо псевдокода или на C++. Это новичкам ничем не поможет ни в понимании, ни в запоминании алгоритма. Это бесполезное дублирование смысла.

И вообще, в чем смысл в очередной раз перепечатывать растиражированную по интернету тысячу раз подборку?

[GHOST966]

Спасибо за такой подробный комментарий. Действительно были неточности в топосортировке и Дейкстре. Я их исправил и заодно чуть подправил структуру статьи, чтобы текст стал понятнее и ровнее.

[Jijiki]

Суть ответа почему так, тоесть "почему" надо или придётся понимать рекурсию таится в мотивации, если мы пишем примеры, по подобию как на бумаге, то это одно, раздел изучили? изучили. Но сами мотивации не в примерах на бумаге, а на боевом примере. И тогда надо будет после некоторых вводных, мотивируясь большой целью, понять почему там очередь с приоритетом. И точно так же с деревьями. Наивно же думать, что пример, который останется на бумаге, будет иметь полную имплементацию, тоесть придётся определиться. Какие структуры, или как удобно(как хотелось бы решить и так далее), какая мотивация решения задачки, будут ли нпцшки ходить и прочее, и там уже мотивация, чтобы не лагало хотябы это...

[Lukerman]

И вообще, в чем смысл в очередной раз перепечатывать растиражированную по интернету тысячу раз подборку?

Карьера.

[ArtemKonkin]

Спасибо за интересную и полезную статью!)

И за цветные изображения