Описание тега kruskals-algorithm
Алгоритм поиска минимального остовного дерева для связного взвешенного графа с помощью жадного поиска.
3
ответа
Как работает этот код для алгоритма MST Крускала?
Ниже приведен код C++ для алгоритма Крускала для нахождения минимального стоимостного дерева графа, заданного моим инструктором. Я плохо понял код. Я хочу точно знать, какая часть кода проверяет формирование цикла в растущем лесу включенных ребер. Я…
16 апр '17 в 20:20
2
ответа
В поисках правильного объединения DST с обратно-аккерманной сложностью
Я говорю о структуре данных union-find-disjoint. В Интернете есть множество ресурсов о том, как это реализовать. До сих пор я узнал о двух методах оптимизации для профсоюзов. Первый - это "балансировка" дерева с помощью переменной Rank, которая гово…
12 апр '15 в 02:13
1
ответ
Как использовать union-find, minheap, Kruskal's и алгоритм сортировки для создания связующего дерева с минимальной стоимостью? (C++)
Я прошу прощения, если этот вопрос является немного широким, но я испытываю затруднения, пытаясь понять, как я создал бы остовное дерево минимальной стоимости. Это в C++, если это вообще имеет значение. Из того, что я понимаю, вы бы использовали Kru…
06 фев '11 в 21:30
1
ответ
Минимальное связующее дерево, которое минимизирует степень определенного узла
Как мы можем найти минимальное остовное дерево, которое минимизирует степень узла v (среди всех минимальных остовных деревьев)? Будет ли модифицировать алгоритм Крускала так, чтобы при наличии нескольких ребер с одинаковым весом мы выбирали тот, кот…
22 фев '17 в 06:18
0
ответов
Алгоритм Крускала с несвязным графом
Я не уверен, как реализовать алгоритм Крускала, когда граф имеет несколько связанных компонентов Из моего понимания алгоритма Крускала, он многократно добавляет минимальное ребро к набору. Затем, когда все ребра проверены, он возвращает набор ребер,…
07 мар '14 в 00:11
1
ответ
Ошибка при поиске минимального остовного дерева по алгоритму Крускала
Я пишу код от добавления вершины в граф и обновляю вес ребра, а затем нахожу минимальное остовное дерево. Я думаю, что я сделал это, но, кажется, в этом есть какая-то ошибка, но я не могу это выяснить. Система использует Valgrind и указывает, что "н…
25 июн '13 в 01:12
2
ответа
Как на производительность алгоритма Крускала влияет несвязанная структура данных набора?
У меня есть общее представление о том, что такое алгоритм Крускала, и вот что я обнаружил: Этот алгоритм в основном строит минимальное остовное дерево путем объединения нескольких деревьев, и он начинает с сортировки ребер по их весам. Начиная с пус…
17 авг '17 в 19:32
1
ответ
Минимальное остовное дерево, какие кромки необходимы / не нужны
В графе для каждого ребра, как вы определяете, присутствует ли он во всех минимальных остовных деревьях, или только в некоторых из них, или ни в одном из них? Предположим, что есть < 1000 вершин и < 100000 ребер, и нам нужно классифицировать все реб…
22 авг '17 в 00:42
1
ответ
C: Значение переменной меняется без переназначения
Я реализую алгоритм Крускала. После того, как я вызову graph() в следующем коде, значение узлов изменится. Я не совсем уверен, почему - если бы кто-нибудь мог это прояснить, я был бы очень признателен. Я не обращаюсь к значению узлов из графа, и оба…
06 ноя '14 в 03:16
0
ответов
Структура данных Union-find - Как использовать make_sets и правильно найти
По сути, я пытаюсь изменить алгоритм Крускала, добавив еще одно условие, помимо проверки, находятся ли вершины u и v в одном и том же компоненте. Я смутно понимаю, как работает структура данных union-find, поэтому я хотел проверить, правильно ли я п…
15 авг '15 в 16:24
2
ответа
Время выполнения алгоритма Крускала путем изменения времени сортировки
Я делал анализ минимальных остовных деревьев и мне было интересно, как время сортировки повлияет на общую сложность алгоритма Крускала? Пример: Если сортировка может быть сделана в O(n log log n) Если сортировка может быть сделана в O(n) Остался бы …
11 ноя '14 в 08:15
3
ответа
Алгоритм Крускала: что такое алгоритм, чтобы проверить, образуют ли ребра графа петлю или нет?
Может ли кто-нибудь предоставить мне информацию о том, как проверить, образуют ли ребра графа петлю или нет? Любая информация будет очень полезна. Спасибо заранее.
21 янв '14 в 10:27
1
ответ
Найти минимальный вес связующего дерева в неориентированном графе, где есть отрицательные ребра
Поэтому мне нужно решить этот график, у меня есть общее представление о том, как его решить, но если я делаю это неправильно, пожалуйста, поправьте меня. Поэтому, чтобы найти MST, мне нужно выполнить алгоритм Крускала на графе. вот мой psuedocode д…
26 апр '15 в 02:38
1
ответ
Составление тура от MST
Я новичок в кодировании Matlab, и я хотел бы знать, как составить план с посещением всех точек в минимальном остовном дереве (да, TSP/TSM). Мне дали набор точек матрицу 20х2, и я смог выяснить MST этих точек, и мне нужна помощь, чтобы выяснить, как …
02 окт '15 в 03:38
3
ответа
Что возвращает (pset[i]==i)? я:(PSET [I]=findSet(PSET [I])); имею в виду?
Я реализую алгоритм Крускала, и я нашел этот код: int findSet(int i) { return (pset[i]==i)? i:(pset[i]=findSet(pset[i])); } и я не знаю, что на самом деле значит любая помощь, пожалуйста?:)
20 апр '15 в 22:54
3
ответа
MST с модификацией
Кто-нибудь может придумать, как изменить алгоритм Крускала для минимального остовного дерева, чтобы оно включало определенное ребро (u,v)?
13 май '12 в 19:10
1
ответ
Вернуть путь между двумя узлами в минимальном остовном дереве
У меня есть минимальное связующее дерево, созданное с использованием алгоритмов Крускала, хранящихся в карте ключ: строка и данные: набор (строка) mst = { "A" : ["B"] "B" : ["A", "C", "D"] "C" : ["B"] "D" : ["B", "E"] "E" : ["D", "F"] } Я пытаюсь на…
12 дек '18 в 17:21
1
ответ
В реализации Java алгоритма Крускала, где именно мы должны выполнить Path Compression?
При реализации алгоритма Крускала в Java с использованием наборов Disjoint следует ли называть сжатие пути отдельной функцией или она должна быть неотъемлемой частью функции find()?
30 дек '18 в 02:58
3
ответа
Разница между Борувкой и Крускалом в нахождении МСТ
Хотелось бы узнать разницу между алгоритмом Борувкаса и алгоритмом Крускала. Что у них общего: оба находят минимальное связующее дерево (MST) в неориентированном графе оба добавляют кратчайший край к существующему дереву, пока не будет найден MST об…
22 апр '18 в 16:11
0
ответов
Алгоритм Крускала минимальный выход связующего дерева
#include <algorithm> #include <iostream> #include <vector> #include <queue> #include<iomanip> using namespace std; typedef pair<int,int> intPair; typedef vector<double> doubleVector; typedef vector<intPai…
16 апр '18 в 19:51