Почему на ориентированном графе нельзя использовать алгоритмы Prim или Kruskal?

Ответ 1

Это второстепенное чудо, что эти алгоритмы работают в первую очередь - самые жадные алгоритмы просто ломаются и записываются в некоторых случаях. Предполагая, что вы хотите использовать их для поиска минимального охватывающего arborescence (направленные пути от одной вершины ко всем остальным), тогда один проблематичный граф для Kruskal выглядит следующим образом.

 5
  --> a
 /   / ^
s   1| |2
 \   v /
  --> b
 3

Мы возьмем дугу a- > b стоимости 1, затем застрянем, потому что нам действительно нужно s- > b стоимости 3 и b- > a стоимости 2.

Для Prim этот график является проблематичным.

 5
  --> a
 /   /
s   1|
 \   v
  --> b
 3

Мы возьмем s- > b стоимости 3, но нам действительно нужно s- > a из стоимости 5 и a- > b стоимости 1.

Ответ 2

Алгоритм Prim и Kruskal выводит минимальное связующее дерево для подключенного и "неориентированного" графа. Если он не подключен, мы можем настроить их для вывода минимальных охватывающих лесов.

В алгоритме Prim мы разделим граф на два набора вершин. Один набор исследуемых вершин, которые уже сформировали MST (Set1) и другой набор неисследованных вершин, которые в конечном итоге присоединятся к первому набору для завершения "spanning" (Set2). В каждый момент времени мы выбираем минимальный взвешенный край в разрезе, соединяющий два непересекающихся множества. Если нет ориентированного края от исследуемых узлов MST до оставшегося неисследованного, алгоритм застревает, даже если есть ребра из неизведанных узлов для исследованных узлов в MST.

В алгоритме Крускаля идея состоит в том, чтобы сортировать ребра по возрастанию по их весу и подбирать их по порядку и включать их в исследуемые узлы/ребра MST, если они уже не образуют цикл с исследуемыми узлами. Это делается Union-Find DS. Но обнаружение цикла для ориентированных графов терпит неудачу с этим методом. Для ex: График, содержащий ребра [1- > 2] [2- > 3] [1- > 3], будет содержать цикл с методом Union-Find.

Итак, Prim не работает, потому что он предполагает, что каждый node доступен из каждого node, который хотя и действителен для неориентированных графов, может быть недействительным для орграфов. Kruskal терпит неудачу из-за неспособности обнаружить циклы, и иногда необходимо добавить края, создающие циклы, чтобы удовлетворить "минимальное" взвешенное свойство MST.

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