Описание тега minimum-spanning-tree

Описание тега Вопросы с тегом
Минимальное остовное дерево (MST) или остовное дерево с минимальным весом - это остовное дерево связного неориентированного графа с наименьшим возможным весом.
1 ответ

Jgraph: общий обход и обход леса

Доброе утро / день / вечер. Итак, наш курс по структурам данных дал нам задание сегментировать изображение в градациях серого в Java с использованием следующего алгоритма: Вход: серое изображение с P пикселями и номером R Вывод: изображение, сегмент…
24 апр '18 в 19:37
1 ответ

Почему я получил тот же график?

Я использую networkx в ipython для анализа своего графа или сети, когда я сгенерировал максимальное связующее дерево и минимальное связующее дерево, я получил очень странный результат, что эти два графа одинаковы! Это мой код ниже: a=nx.maximum_span…
19 мар '18 в 16:27
1 ответ

Вариант минимального связующего дерева коммивояжера

Я пытаюсь решить следующее графическое упражнение: В неориентированном взвешенном графе есть V вершин и E ребер. Найдите минимальный вес, необходимый для посещения T(T<=V) вершин, начиная с вершины, помеченной как 0. Кроме того, если между двумя пос…
26 мар '15 в 20:48
3 ответа

Как работает этот код для алгоритма MST Крускала?

Ниже приведен код C++ для алгоритма Крускала для нахождения минимального стоимостного дерева графа, заданного моим инструктором. Я плохо понял код. Я хочу точно знать, какая часть кода проверяет формирование цикла в растущем лесу включенных ребер. Я…
16 апр '17 в 20:20
1 ответ

Как использовать union-find, minheap, Kruskal's и алгоритм сортировки для создания связующего дерева с минимальной стоимостью? (C++)

Я прошу прощения, если этот вопрос является немного широким, но я испытываю затруднения, пытаясь понять, как я создал бы остовное дерево минимальной стоимости. Это в C++, если это вообще имеет значение. Из того, что я понимаю, вы бы использовали Kru…
06 фев '11 в 21:30
2 ответа

Перевод кода с ++ на Java безуспешно

Я делаю программу для расчета маршрутов с минимальной стоимостью, используя минимальные остовные деревья. Я сделал свою реализацию в C++, но я не мог сделать графический интерфейс для чтения входного файла, поэтому я решил передать его на язык Java …
03 май '12 в 21:48
1 ответ

Ищет похожие известные проблемы

Я пытаюсь доказать компьютерную сложность этой задачи оптимизации:Для заданного связного графа G = (V, E) и множества S ⊊ V. Найдите связный подграф G'= (V', E '), который: Min f(G') Min |V'| Подчинить: S ⊊ V’ V’ ⊆ V Это выглядит как обобщение задач…
15 ноя '12 в 17:15
1 ответ

Доказательство оптимальности для нового алгоритма, который находит минимальное остовное дерево

Ниже приведен алгоритм, который находит минимальное остовное дерево: MSTNew(G, w) Z ← empty array for each edge e in E, taken in random order do Z ← Z ∪ e if Z has a cycle c then let e be a maximum-weight edge on c Z ← Z − e return (Z) Всегда ли это…
25 ноя '14 в 05:54
4 ответа

Как вычислить минимальное связующее дерево узкого места за линейное время?

Мы можем найти минимальное остовное дерево узкого места в O(E log*V) в худшем случае, используя алгоритм Крускала. Это связано с тем, что каждое минимальное остовное дерево является минимальным остовным деревом. Но я застрял на этом вопросе собеседо…
05 апр '14 в 02:17
1 ответ

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

У меня есть граф, представленный списками смежности, а его MST представлен родительским массивом. Моя проблема в том, что мне нужно удалить ребро из графика и обновить родительский массив. Мне уже удается делать случаи, когда: край не существует; ре…
01 дек '12 в 11:53
1 ответ

Минимальное связующее дерево, которое минимизирует степень определенного узла

Как мы можем найти минимальное остовное дерево, которое минимизирует степень узла v (среди всех минимальных остовных деревьев)? Будет ли модифицировать алгоритм Крускала так, чтобы при наличии нескольких ребер с одинаковым весом мы выбирали тот, кот…
22 фев '17 в 06:18
4 ответа

Альтернатива этому коду Python?

У меня есть строка кода из класса, которую я не понимаю полностью и хочу более легкую альтернативу. Для этого используется weightList, представляющий собой список ребер, связанных друг с другом, и возвращает списки ребер с наименьшим соответствующим…
22 авг '16 в 19:07
2 ответа

Есть ли способ быстро найти все ребра, которые являются частью цикла (задние ребра) в неориентированном / ориентированном графе?

У меня есть минимальное остовное дерево. Я добавляю к этому преимущество. Конечно, цикл сформирован. Мне нужно найти все ребра, которые являются частью этого цикла, т. Е. Все задние ребра. Как быстро это можно сделать? Мое решение - например, если э…
09 дек '13 в 13:10
0 ответов

Алгоритм Крускала с несвязным графом

Я не уверен, как реализовать алгоритм Крускала, когда граф имеет несколько связанных компонентов Из моего понимания алгоритма Крускала, он многократно добавляет минимальное ребро к набору. Затем, когда все ребра проверены, он возвращает набор ребер,…
07 мар '14 в 00:11
1 ответ

Как работает Минимальное связующее дерево в neo4j

Я играю с некоторыми алгоритмами теории графов в neo4j. Я пытаюсь найти минимальное связующее дерево (MST) в моей сети. Я синтетически создал сеть из 10 000 человек. У каждого человека есть 12 типов отношений, каждый из которых связывает его с други…
06 дек '17 в 11:38
1 ответ

Как получить подмножество минимального веса?

Вот акциз: Рассмотрим задачу нахождения связного подмножества T с минимальным весом из взвешенного связного графа G. Вес T является суммой всех весов ребер в T. Приведите эффективный алгоритм для вычисления подмножества T с минимальным весом. Вот чт…
02 май '12 в 22:20
2 ответа

Алгоритм Прима для динамических локаций

Предположим, у вас есть входной файл: &lt;total vertices&gt; &lt;x-coordinate 1st location&gt;&lt;y-coordinate 1st location&gt; &lt;x-coordinate 2nd location&gt;&lt;y-coordinate 2nd location&gt; &lt;x-coordinate 3rd location&gt;&lt;y-coordinate 3rd …
14 апр '13 в 06:12
3 ответа

Java: Как выглядит мой Prim?

Я пытаюсь реализовать алгоритм минимального связующего дерева Prim с JGraphT. Как это выглядит? Одна проблема, с которой я столкнулся, заключалась в том, что JGraphT обрабатывал все так, как он направлен. Поэтому иногда необходимо сделать несколько …
24 ноя '09 в 00:02
2 ответа

Как на производительность алгоритма Крускала влияет несвязанная структура данных набора?

У меня есть общее представление о том, что такое алгоритм Крускала, и вот что я обнаружил: Этот алгоритм в основном строит минимальное остовное дерево путем объединения нескольких деревьев, и он начинает с сортировки ребер по их весам. Начиная с пус…
17 авг '17 в 19:32
1 ответ

Какую структуру данных мне нужно использовать для построения минимального связующего дерева в Java?

У меня есть класс Node похож на класс Java Point с x а также y координаты, которые я рисую на JPanel, Я пытаюсь создать минимальное остовное дерево для набора таких узлов на евклидовом графе, которое я бы затем нарисовал на панели. Но я не могу поня…
03 мар '14 в 17:26