Вопросы по теме 'minimum-spanning-tree'

Алгоритм Прима для минимальных остовных деревьев - путаница в алгоритме
Я изучал книгу Кормена и др., и я немного запутался в алгоритме, который они предоставили. Я понял, как работает концепция алгоритма Прима из Википедии, но я не могу имитировать эту работу, используя алгоритм, представленный в моей книге....
2614 просмотров
algorithm prims-algorithm minimum-spanning-tree
schedule 08.12.2022
Как найти максимальное остовное дерево?
Работает ли для него противоположность алгоритму Крускала минимального остовного дерева? Я имею в виду, выбирая максимальный вес (край) на каждом шаге? Есть ли другая идея найти максимальное остовное дерево?
103605 просмотров
algorithm greedy minimum-spanning-tree kruskals-algorithm
schedule 06.11.2022
Минимальное количество связующего дерева с учетом ребра, которое должно быть включено
Меня смущает общая форма минимального остовного дерева, которая включает ребро e , которое не является частью минимального остовного дерева. У меня вопрос: Пусть G будет взвешенным графом, у которого вес всех ребер равен 1. MST графа G не...
1146 просмотров
algorithm graph-theory minimum-spanning-tree
schedule 12.07.2022
Найдите родительский узел дерева, чтобы создать максимально короткую высоту дерева
У меня есть неориентированный граф, представленный в виде матрицы смежности евклидовых весов. Я использую это для представления минимального остовного дерева для большего полного графа. Что я хочу найти, так это единственный узел в графе, который...
1753 просмотров
graph tree traversal depth-first-search minimum-spanning-tree
schedule 01.07.2022
Как реализовать шаг сокращения в алгоритме Christofides?
Я реализую алгоритм Кристофидеса для получения 3/2-аппроксимации TSP в графах, которые подчиняются неравенство треугольника. У меня уже есть код для вычисления минимального остовного дерева с использованием алгоритма Крускала и матрицы смежности....
1624 просмотров
c algorithm traveling-salesman minimum-spanning-tree kruskals-algorithm
schedule 08.03.2023
Боится ли Minimum Spanning Tree отрицательных весов?
Это дополнительный вопрос для Почему большинство алгоритмов на основе графиков не так легко адаптируются к отрицательным числам? . Я думаю, что у кратчайшего пути (SP) есть проблема с отрицательными весами, потому что он складывает все веса вдоль...
42826 просмотров
graph algorithm data-structures minimum-spanning-tree
schedule 15.02.2023
Пожалуйста, объясните связь между операциями Decrease-Key и Extract-Min в приоритетных очередях.
Какая связь между операцией EXTRACT-MIN и операциями DECREASE-KEY в приоритетной очереди? Я столкнулся с этим в лекции по проблеме минимального охвата с использованием алгоритма Прима. Профессор из Массачусетского технологического института...
9355 просмотров
algorithm data-structures prims-algorithm minimum-spanning-tree priority-queue
schedule 17.11.2022
Как запустить алгоритм Дейкестры, чтобы сделать его похожим на Prim и сгенерировать MST?
Предположим, я запускаю алгоритм Дейкстры для посещения всех узлов (вместо исходного начального узла и узла назначения), т.е. я проверяю, все ли узлы посещены или нет, вместо узла назначения. Будет ли этот алгоритм генерировать MST (минимальное...
161 просмотров
algorithm dijkstra minimum-spanning-tree
schedule 04.03.2023
Отзыв об алгоритме дерева Штейнера с ограничениями
Для задания мне нужно создать Дерево Штейнера . Однако это не типичное дерево Штейнера, поскольку структура графа, которую мы должны использовать, не позволяет вставлять новые вершины. Скорее, тестовые примеры определяют структуру графа из N вершин...
697 просмотров
dijkstra graph-algorithm minimum-spanning-tree
schedule 08.01.2023
Алгоритм поиска остовного дерева только с весами 1 и 2
Для данного взвешенного связного простого неориентированного графа G с весами только 1 и 2 на каждом ребре найдите MST графа G за O(V+E). Есть идеи? Извините за формулировку вопроса, я старался перевести как мог.
2730 просмотров
graph algorithm graph-algorithm minimum-spanning-tree
schedule 17.05.2022
Алгоритм Прима, когда известен диапазон весов ребер
Предположим, что все веса ребер в графе являются целыми числами в диапазоне от 1 до |V|. Как быстро вы сможете заставить работать алгоритм Прима? Что, если веса ребер представляют собой целые числа в диапазоне от 1 до W для некоторой константы W?...
4140 просмотров
graph algorithm graph-theory minimum-spanning-tree
schedule 31.03.2022
Увеличение минимального остовного дерева с включением/исключением некоторых ребер
Я пытаюсь реализовать список всех возможных остовных деревьев графа в порядке увеличения стоимости. Я использую алгоритм Sorensen and Janssens (2005) . Граф инициализируется следующим образом: typedef property<edge_weight_t, int>...
253 просмотров
boost graph minimum-spanning-tree kruskals-algorithm boost-graph
schedule 30.05.2022
Минимальное остовное дерево. уникальное минимальное ребро против неуникального доказательства
Итак, у меня есть упражнение, которое я должен доказать или опровергнуть: 1) если e - ребро минимального веса в связном графе G такое, что не все ребра обязательно различны, то каждое минимальное остовное дерево графа G содержит e 2) То же, что...
1547 просмотров
graph algorithm tree minimum-spanning-tree proof
schedule 12.11.2022
Минимальное связующее дерево отличается от другого
Предположим, нам даны неориентированный граф g , где каждый узел i, 1 ‹= i‹ n связан со всеми j, i ‹j‹ = n и источник s . Мы хотим найти общие затраты (определяемые как сумма весов всех ребер) самого дешевого минимального остовного...
459 просмотров
graph algorithm minimum-spanning-tree
schedule 17.10.2022
Нахождение MST такого, что конкретная вершина имеет минимальную степень
Учитывая неориентированный связный граф G={V,E}, вершину в V(G), обозначим ее v и весовую функцию f:E->R+(положительные действительные числа), мне нужно найти MST такое, что v степень минимальна. Я уже заметил, что если все ребра имеют уникальный...
916 просмотров
graph algorithm minimum-spanning-tree kruskals-algorithm degrees
schedule 10.02.2023
новое ребро вставляется в минимальное остовное дерево
Я пытаюсь найти алгоритм ответа на следующий вопрос с одним отличием: края нечеткие. Приведите эффективный алгоритм, чтобы проверить, остается ли T остовным деревом с минимальной стоимостью с новым ребром, добавленным к G. в этой ссылке - есть...
2065 просмотров
graph-algorithm minimum-spanning-tree
schedule 15.03.2022
Зачем получать минимальную вершину в алгоритме Prim MST?
Насколько я понимаю, алгоритм Prim MST будет проходить по всем вершинам графа, выбирая ОДНО лучшее ребро для перехода к каждой вершине. Следовательно, каждая итерация будет выбирать оптимальную стоимость для каждой соседней вершины. Следовательно,...
577 просмотров
c++ prims-algorithm minimum-spanning-tree
schedule 17.01.2023
java - Как найти наибольшее взвешенное ребро в MST?
Вопрос довольно простой, судя по заголовку. У меня есть существующий MST, неориентированный с взвешенными ребрами, с вершинами V. Имея начальный и конечный узлы, существует ли эффективный алгоритм, который работает за O(V) времени и возвращает...
212 просмотров
java minimum-spanning-tree
schedule 17.05.2023
Минимальное остовное дерево с использованием алгоритма Крускала
Я использую алгоритм Крускала для выполнения задания по определению минимального остовного дерева следующей задачи: У меня есть города, которые все должны быть связаны. Я могу соединить их, проложив между ними дороги или построив аэропорт. Когда...
673 просмотров
algorithm minimum-spanning-tree kruskals-algorithm
schedule 02.05.2023
как куча Фибоначчи повышает эффективность алгоритма Прима
Я знаю алгоритм Прима и кучу Фибоначчи, но мой вопрос: как куча Фибоначчи повышает эффективность алгоритма по сравнению с реализацией очереди с минимальным приоритетом на основе списка массивов
330 просмотров
algorithm prims-algorithm minimum-spanning-tree priority-queue fibonacci-heap
schedule 12.05.2022