Являются ли алгоритмы MST неориентированного графа (Прима или Крускала) общей формой алгоритма ориентированного MST (Эдмонд / Чиу)? Почему так сложно найти исходный код MST для указанного случая? Можем ли мы использовать неориентированное решение для получения MST в ориентированном графе?
Это связано со следующим: Почему нельзя ли использовать алгоритмы Прима или Крускала на ориентированном графе?
Суть вашего вопроса, по-видимому, заключается в том, что отличает поиск MST (технически называемого оптимальным ветвлением или древовидностью с минимальными затратами) в ориентированном графе и, следовательно, труднее, чем поиск MST в неориентированном графе.
И алгоритмы Прима, и Крускала работают благодаря свойству cut. Если G = (V, E) - граф, то для любого разреза (S, V - S) в G, если есть ребро {u, v} с наименьшей стоимостью, пересекающее этот разрез, это ребро должно принадлежать всем MST of G. К сожалению, в направленном случае это свойство неверно. Вот контрпример:
2
A ----> B
| | ^
1 | -99 | | 1
| v |
+-----> C
Здесь дерево с минимальными затратами, основанное на точке A, выглядит следующим образом:
2
A ----> B
|
-99 |
v
C
Однако посмотрите на разрез ({A}, {B, C}). Ребро с наименьшей стоимостью, пересекающее этот разрез, - это ребро (A, C), но это ребро не появляется ни в одной древовидной структуре с минимальной стоимостью, основанной на A .
Без свойства cut оба алгоритма Прима и Крускала терпят неудачу. Попробуйте запустить алгоритм Прима на приведенном здесь графе, начиная с узла A в качестве включенного узла. Вы добавите ребро (A, C), затем ребро (C, B), что даст субоптимальную древесину. Теперь попробуйте запустить здесь алгоритм Краскала. Сначала вы добавите край (B, C), затем добавьте край (A, C). К сожалению, на самом деле это не древовидное растение, потому что у него нет корневого узла.
Стандартный алгоритм поиска древовидных растений с минимальными затратами (Эдмондс-Чу) на самом деле, вероятно, ближе по духу к алгоритм Борувки. Алгоритм Борувки работает путем одновременного выбора для каждого узла ребра с наименьшей стоимостью, подключенного к этому узлу, и добавления его к MST-кандидату. Затем вы сжимаете все сформированные таким образом CC в отдельные узлы и повторяете этот процесс, пока не получите свое дерево.
В неориентированном случае, пока веса ребер различны, этот алгоритм никогда не будет вводить цикл (это хорошее упражнение, чтобы доказать это), но это не так в направленных алгоритмах. Приведенный выше график является хорошим примером этого - если вы попробуете это, вы выберете (A, C) из A, (C, B) из C и (B, C) из B, образуя цикл (B, C , Б). Исправление, которое использует алгоритм Эдмондса-Чу, работает путем сжатия одного из этих циклов в один узел, затем повторения этого процесса в сокращенном графе и разрыва циклов на основе результата. В этом смысле он похож на алгоритм Борувки, но с соответствующими модификациями.
Надеюсь это поможет!
Я нашел несколько хороших слайдов с хорошим, четким объяснение разницы с четкими цифрами и примерами
