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

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

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

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

Для Прима этот график проблематичен.

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

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

Алгоритмы Прима и Краскала выводят минимальное остовное дерево для связанных и неориентированных графов. Если граф не связан, мы можем настроить алгоритмы для вывода минимальных остовных лесов.

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

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

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

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