Почему алгоритм MST Прима и Крускала не работает для ориентированного графа?

Предварительные условия:

• Граф и его представления
• Жадные алгоритмы | Набор 5 (Минимальное связующее дерево Прим (MST))
• Алгоритм минимального связующего дерева Краскала | Жадный Алго-2

Для ориентированного графа D = <V, E> задача состоит в том, чтобы найти минимальное остовное дерево для данного ориентированного графа.

Пример:

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

Почему алгоритм Прима не работает для ориентированного графа?

Алгоритм Прима предполагает, что все вершины связаны. Но в ориентированном графе каждый узел недоступен из любого другого узла. Итак, алгоритм Прима не работает по этой причине.
Например:

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

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

Сообщается, что этот график содержит цикл с методом объединения-поиска, но этот график не имеет цикла.

Эквивалент минимального остовного дерева в ориентированных графах: «Минимальное остовное древообразование» (также известное как оптимальное ветвление) может быть решено алгоритмом Эдмондса за время работы O (EV). Этот алгоритм является направленным аналогом задачи о минимальном остовном дереве.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.