5
ответов
Двумя путями связующее дерево минимума ориентированного графа
Учитывая ориентированного графа со взвешенными краями, что алгоритм может использоваться для предоставления подграфа, который имеет минимальный вес, но позволяет перемещение от любой вершины до любой другой вершины в графике (под...
вопрос задан: 11 May 2010 08:13
4
ответа
Существует ли минимальное связующее дерево, которое не содержит минуту взвешенный край / макс. взвешенный край?
Если у нас есть (произвольный) связанный неориентированный граф G, чьи края имеют отличные веса, каждый MST G содержит минимальный взвешенный край? есть ли MST G, который не содержит...
вопрос задан: 18 October 2012 20:30
3
ответа
Обновление Минимального связующего дерева, когда новый край вставляется
Я был представлен следующая проблема в Университете: Позвольте G = (V, E) быть (неориентированным) графиком с затратами ce> = 0 на краях e ∈ E. Предположите предоставление стоившего за минимум связующего дерева T в G...
вопрос задан: 16 September 2012 15:31
3
ответа
Использовать Dijkstra для нахождения Минимального Связующего дерева?
Dijkstra обычно используется для нахождения кратчайшего расстояния между двумя узлами в графике. Это может использоваться для нахождения минимального связующего дерева? Если так, как?Править: Это не домашняя работа, но я пытаюсь...
вопрос задан: 15 December 2009 20:00
2
ответа
Когда я должен использовать Kruskal в противоположность Чопорному (и наоборот)?
Я задавался вопросом, когда нужно использовать алгоритм Prim и когда Kruskal для нахождения минимального связующего дерева? У них обоих есть легкие логики, те же худшие случаи, и единственной разницей является реализация который...
вопрос задан: 20 March 2019 05:41
2
ответа
MST Prim: вопрос узла запуска?
Я интуитивно чувствую, что, если Вы используете алгоритм Prim для нахождения минимального связующего дерева графика, он не имеет значения, какой корневой узел выбран - результирующий MST будет иметь тот же вес независимо...
вопрос задан: 24 November 2009 00:59
1
ответ
MST в unDirected графе с удаленным краем [duplicate]
У меня есть нескрываемый граф G = (V, E) и весовая функция w: E-> R +. также, у меня есть MST T G. Мне нужно построить алгоритм, который выполняет следующее: если мы удалим ребро e 'из E., предложим алгоритм ...
вопрос задан: 24 August 2015 22:01
1
ответ
Как найти максимальное связующее дерево?
Работает ли для него противоположность алгоритма Краскала для минимального связующего дерева? Я имею в виду, выбирая максимальный вес (край) на каждом шаге? Есть ли другая идея найти максимальное остовное дерево?
вопрос задан: 20 January 2014 22:34
1
ответ
Минимальное Связующее дерево: Каково точно Свойство Сокращения?
Я проводил много времени, читая онлайн-презентации и учебники о свойстве сокращения минимального связующего дерева. Я действительно не получаю то, что это, предполагают для иллюстрирования или даже почему это...
вопрос задан: 25 July 2010 02:09
1
ответ
Существует ли Динамическое программирование способ вычислить k минимальные связующие деревья?
Мой учитель попросил, чтобы мы реализовали решение для Динамического программирования той проблемы, но я думаю, что каждый не существует, так как я не мог найти это Google использования. Так или иначе, учитывая график и k, скажите 3, Вы...
вопрос задан: 10 July 2010 09:51
1
ответ
Вся минимальная реализация связующих деревьев
Я искал реализацию (я пользуюсь networkx библиотекой.), который найдет все минимальные связующие деревья (MST) неориентированного взвешенного графика. Я могу только найти реализации для Kruskal'...
вопрос задан: 29 May 2010 17:52
0
ответов
В реализации Java алгоритма Крускала, где именно мы должны выполнить Path Compression?
При реализации алгоритма Крускала в Java с использованием наборов Disjoint следует ли называть сжатие пути отдельной функцией или она должна быть неотъемлемой частью функции find ()?
вопрос задан: 30 December 2018 03:56
0
ответов
Боится ли минимальное остовное дерево отрицательных весов?
Это дополнительный вопрос о том, почему большинство графовых алгоритмов не так легко адаптируются к отрицательным числам? Я думаю, что у кратчайшего пути (SP) есть проблема с отрицательными весами, потому что он суммирует все веса...
вопрос задан: 23 May 2017 11:54
0
ответов
Алгоритм, чтобы увидеть, есть ли точно два MST в графе?
У меня есть ненаправленный связный граф G. Я хочу найти алгоритм, который возвращает true, если есть хотя бы 2 MST. Что делать, если я хочу посмотреть, есть ли точно 2 MST?
вопрос задан: 8 December 2012 01:33
0
ответов
Нахождение минимального связующего дерева из списка смежности, где список смежности находится в строковом массиве с использованием алгоритма Prims
Поэтому мне нужна помощь, чтобы найти способ найти Минимальное остовное дерево.
Предположим, у меня есть свой график в виде списка смежности: A 2 B 12 I 25
В 3 В 10 Ч 40 I 8
С 2 Д 18 Г 55
D 1 E 44
E 2 F 60 G ...
вопрос задан: 5 October 2012 18:38
0
ответов
Общее время выполнения алгоритма Примса!
«Таким образом, общее время для алгоритма Прима составляет O (V lg V + E lg V) = O (E lg V), что асимптотически такое же, как и для нашей реализации. алгоритма Крускала ". Из http://serverbob.3x.ro/IA/...
вопрос задан: 6 July 2012 20:24
0
ответов
Как я могу написать алгоритм MST (Prim или Kruskal) на Haskell?
Я могу написать алгоритмы Prim и Kruskal для поиска минимального остовного дерева на C ++ или Java, но я хочу чтобы знать, как реализовать их в Haskell с помощью O (mlogm) или O (mlogn) (чисто функциональные программы ...
вопрос задан: 6 July 2012 20:22
0
ответов
Реализация алгоритма Краскала на Аде, не знаю, с чего начать
Что касается алгоритма Крускала на Аде, я не уверен, с чего начать. Я пытаюсь обдумать все, прежде чем напишу программу, но я совершенно не понимаю, какие структуры данных я ...
вопрос задан: 6 July 2012 20:21
0
ответов
Нахождение минимального разреза в графе с помощью алгоритма Крускала?
Мы уже видели, что остовные деревья и разрезы тесно связаны. Вот еще одна связь. Удалим последнее ребро, которое алгоритм Крускала добавляет к остовному дереву; это ломает...
вопрос задан: 6 July 2012 20:16
0
ответов
Различия между минимальным остовным деревом и деревом кратчайшего пути
Вот акциз :Либо докажите следующее, либо приведите контрпример:(а )Является ли путь между а пара вершин в минимальном остовном дереве неориентированного графа обязательно кратчайшая...
вопрос задан: 4 May 2012 11:56
0
ответов
Обновить минимальное остовное дерево с модификацией ребра
Граф (ребра с положительным весом )с MST Если какое-то ребро e изменено на новое значение, как лучше всего обновить MST, не переделывая его полностью. Я думаю, что это можно сделать за линейное время....
вопрос задан: 30 March 2012 07:51
0
ответов
Быстрый алгоритм для минимальных остовных деревьев, когда длина ребер ограничена?
Предположим, у вас есть ориентированный граф с неотрицательные целые длины ребер в диапазоне от 0 до U - 1 включительно. Какой алгоритм является наиболее быстрым для вычисления минимального остовного дерева этого ...
вопрос задан: 15 January 2012 23:45
0
ответов
Найти, содержит ли минимальное охваченное дерево в линейном времени?
У меня есть следующая проблема на моей домашней работе: дайте алгоритму O (N + M), чтобы найти, что край E будет частью MST графика (нам разрешено получать помощь от других на этом ...
вопрос задан: 2 September 2011 20:59
0
ответов
Размер класса Java в пространстве PermGen
Существует множество вопросов и ответов о размере объекта Java, которые довольно легко понять. Но меня интересует размер Java-класса в пространстве PermGen. Причина, по которой мне интересно ...
вопрос задан: 2 May 2011 18:25
0
ответов
Самый быстрый алгоритм минимального связующего дерева
http://en.wikipedia.org/wiki/Minimum_spanning_tree Я хочу сравнить свой алгоритм минимального связующего дерева с лучшими из лучший.
Кто-нибудь знает, где я могу найти C ++ реализацию ...
вопрос задан: 7 February 2011 17:16
0
ответов
Эффективное минимальное остовное дерево в метрическом пространстве
У меня большой набор точек (n> 10000 в количестве ) в некотором метрическом пространстве (например, снабженном расстоянием Жаккара). Я хочу связать их с минимальным остовным деревом, используя метрику в качестве веса на ...
вопрос задан: 17 January 2011 18:19