Комментарии 3
Несколько замечаний по тексту:
(Алгоритм Прима) Сначала берется произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшей стоимостью.
Нет, на самом деле берется одна любая вершина и считается остовным деревом в подграфе из нее одной (граф из одной вершины и без ребер - тоже дерево). Потом уже, да, обходятся все ребра из дерева вне его и выбирается минимальное. Также стоит указать, что алгоритм Прима практически идентичен алгоритму Дейкстры. Только в дейкстре мы для каждой вершины минимизируем сумму ребер, а в Приме - последнее ребро в пути. МОДом тут получается дерево кратчайших путей из любой вершины до всех остальных.
Про алгоритмы топологической сортировки и поиска точек сочленения хорошо бы еще и написать, как оно работает. В первом случае мы пользуемся тем фактом, что DFS не может выйти из вершины, пока не обработает все вершины, куда ведут ребра. Поэтому, если выдавать в ответ вершины в порядке выхода, то мы будем делать это с последних в топологической сортировке. Еще, надо перебирать все вершины в цикле, потому что запустившись от какой-то вершины мы не факт, что обойдем весь граф. Но все не обойденные вершины можно будет выдать в ответ перед всеми обойденными, иначе бы в них было ребро и DFS обошел бы и их.
Для алгоритма поиска шарниров стоит сначала указать важное свойство DFS: если рассмотреть дерево из ребер, по которым DFS прошел, то все оставшиеся ребра в графе будут "возвратными" - они будут идти от вершины к какому-то предку в дереве. И никогда между ветками. Алгоритм поиска шарниров для каждой вершины считает самую высокую в дереве вершину, в которую можно попасть, если идти вниз, а потом возможно по одному возвратному ребру. Если есть точка сочленения, то из какого-то ее ребенка нельзя попасть выше нее. Если есть мост, то это точно ребро в дереве обхода и из ребенка нельзя попасть выше него.
Для задачи коммивояжора стоит указать что есть точное решение через динамическое программирование за O(N^2 2^N), что гораздо быстрее O(N!) brute force.
Спасибо за дополнения, нет желания поконтрибьютить в раздел: https://github.com/harryheman/my-js/tree/master/docs/algorithms ?
JavaScript: структуры данных и алгоритмы. Часть 10