Описание тега prims-algorithm

Описание тега Вопросы с тегом
Prim's algorithm is a fast algorithm for computing minimum spanning trees.
1 ответ

Поддержание инварианта в алгоритме Прима

Тим Раугарден в курсе Алгоритмы 2 учит следующему подходу для обновления смежных вершин в куче min (после извлечения min из кучи): When a vertice v is added to the MST: For each edge (v,w) in the unexplored tree: 1. Delete w from the min heap. 2. Re…
25 мар '16 в 04:56
1 ответ

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

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

Как уменьшить ключ для определенного ребра в priority_queue<PI, vector <PI>, больше<PI>>, пытаясь реализовать алгоритм prim?

#include &lt;bits/stdc++.h&gt; using namespace std; #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define LL long long int #define pb push_back #define mp make_pair #define PI pair&lt;int,int&gt; #define PL pair&lt;LL,LL&gt; #def…
17 июл '16 в 14:43
2 ответа

Алгоритм Прима C# Unity

В настоящее время я генерирую случайный лабиринт в Unity, используя алгоритм prim. Вот как выглядит лабиринт, если я запускаю игру. Это то, что я хочу, чтобы лабиринт был похож. Разница заключается в том, что у первого касаются углов белых квадратов…
10 июл '14 в 16:51
4 ответа

Временная сложность алгоритма простых чисел?

Временную сложность алгоритма Примса я нашел повсюду в виде O ((V + E) log V) = E log V. Но как мы можем видеть алгоритм: Похоже, сложность по времени равна O (V (log V + E log V)). Но если его сложность по времени равна O ((V + E) log V). Тогда вло…
06 дек '13 в 18:11
4 ответа

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

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

Как реализовать алгоритм Прима с кучей Фибоначчи?

Я знаю алгоритм Прима и знаю его реализацию, но всегда пропускаю часть, которую хочу сейчас спросить. Было написано, что реализация алгоритма Прима с кучей Фибоначчи O(E + V log(V)) и мой вопрос: что такое куча Фибоначчи? Как это реализовано? А такж…
28 янв '11 в 06:30
3 ответа

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

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

Алгоритм Прима не будет вычислять

Я сделал алгоритм прима, но всякий раз, когда я пытаюсь использовать код, он возвращает мне ту же матрицу. В общем, это не минимизирует. Может кто-нибудь проверить код и сообщить мне, почему он не минимизирует мою матрицу #include &lt;iostream&gt; #…
24 апр '16 в 16:51
1 ответ

Может кто-нибудь объяснить, как std:: большее используется для реализации priority_queue

std::priority_queue&lt;int, vector&lt;int&gt;, std::greater&lt;int&gt; &gt; pq; Я не могу понять работу std:: большее в очереди приоритетов. Я заменяю minheap приоритетной очередью. этот код взят из geeksForGeeks реализации алгоритма Prims с использ…
04 окт '17 в 17:36
13 ответов

Разница между алгоритмами Прима и Дейкстры?

В чем точная разница между алгоритмами Дейкстры и Прима? Я знаю, что Prim даст MST, но дерево, сгенерированное Dijkstra, также будет MST. Тогда какая точная разница?
03 янв '13 в 17:45
1 ответ

Могу ли я использовать алгоритм Прима вместо Дейкстры, чтобы найти кратчайший путь?

Я целый день боролся за понимание алгоритма Дейкстры и его реализацию без существенных результатов. У меня есть матрица городов и их расстояний. То, что я хочу сделать, это дать точку отправления и пункт назначения, чтобы найти кратчайший путь между…
20 мар '11 в 17:24
1 ответ

Алгоритм Прима с Трепами

Может ли алгоритм Прима быть реализован с помощью трэпов, чтобы ускорить выполнение, потому что нормальная куча создаст проблему при обновлении значения ключей при сохранении вершин в кучах, что в противном случае потребовало бы пространства O(V) дл…
13 апр '14 в 06:31
1 ответ

Алгоритм 1 функции прим

Я попытался сделать алгоритм 1 функции prims в Python, но он не работает def prim(edges): inGraph = ['A'] discovered = [] results = [] counter = 0 while True: tmplist = [] for i in edges: if inGraph[counter] in i: discovered.append(i) tmplist.append…
21 фев '17 в 15:48
1 ответ

Geotools минимальное остовное дерево

Есть ли реализация алгоритма Прима или любого другого алгоритма в пакете геоинструментов для решения задачи о минимальном остовном дереве?
18 окт '16 в 12:11
1 ответ

Сложность простых чисел с использованием массива

Сложность алгоритма Prims с использованием массива и списка смежности: V^2 + V + 2E + E = O(V^2) Но я не могу вспомнить, почему E,
14 окт '16 в 18:37
1 ответ

Как реализовать уменьшение ключа в куче Фибоначчи для запуска в O(1) амортизированное время?

Как можно получить амортизированную сложность O(1) в операции уменьшения ключа в куче Фибоначчи? Простое нахождение узла в куче Фибоначчи, содержащей элемент, занимает O(n) времени с использованием BFS, что делает невозможным получение O(1) амортизи…
22 окт '13 в 07:23
1 ответ

Создание "жесткого" лабиринта с использованием алгоритма Прима

Я использую алгоритм Прима для создания лабиринта. Я успешно сделал это, но теперь я пытаюсь сделать это "сложнее", изменив способ выбора потенциальных клеток для добавления в лабиринт. На мой взгляд, "жесткий" лежит между двумя крайностями: Экстрим…
21 дек '18 в 16:21
1 ответ

Очистить массив данных в C (алгоритм Прима)

Я пишу код о реализации алгоритма Прима и строю минимальное остовное дерево, начиная с вершины 1. Вот формат ввода: Первая строка будет количество случаев. Каждый случай начинается с количества вершин. Предположим, я ввожу так: 2 4 0,1,0,4 1,0,3,2 0…
26 дек '18 в 01:56
1 ответ

Примы MST из Википедии 3с не имеют смысла

Работа с примером Wiki Prims с https://en.wikipedia.org/wiki/Prim%27s_algorithm Добраться до пункта 3с - Зациклите ребра vw, соединяя v с другими вершинами w. Для каждого такого ребра, если w все еще принадлежит Q и vw имеет меньший вес, чем C[w], в…
20 фев '19 в 12:29