Это псевдокод, который я использовал для алгоритма Крускала. Структура данных, которую я здесь использовал, представляет собой матрицу смежности. Получил порядок роста как n^2 . Я хочу знать, правильно это или нет. Kruskal’s Pseudo code 1....

Пусть G = (V, E) — взвешенный, связный и неориентированный граф, а e — любое ребро в E. Покажите линейный алгоритм, определяющий, существует ли минимальное остовное дерево, содержащее ребро e. Мне удалось найти странное «решение» вопроса 1, и оно,...

Пусть G = (V, E) — взвешенный, связный и неориентированный граф. Пусть T1 и T2 будут двумя разными MST. Предположим, что мы можем написать E = (A1 U B U A2) таким образом, что: B является пересечением ребер T1 и T2, и A1 = T1 - B A2 = T2 - B...

Я не уверен, как реализовать алгоритм Крускала, когда граф имеет несколько связанных компонентов. Насколько я понимаю алгоритм Крускала, он постоянно добавляет к набору минимальное ребро. Затем, когда все ребра проверены, он возвращает набор...

У меня есть задание, в котором мне нужно создать лабиринт из сетки ячеек. Я успешно сделал это, используя Рандомизированный алгоритм Крускала , как описано на странице Wiki, с использованием непересекающихся установить структуру данных . Теперь...

Мне сложно найти противоречащий пример следующей вариации задачи TSP. Входные данные: G = (V, E) неориентированный полный граф, удовлетворяющий неравенству треугольника, w: E- ›R + весовая функция и исходная вершина s. Выход: простой цикл...

Эта версия алгоритма Крускала представляет ребра со списком смежности. Как мне изменить псевдокод, чтобы вместо этого использовать матрицу смежности? Я думал, что нам нужно будет использовать, например, вес ребер (i, j), если он не равен...

Резюме: я ищу оптимальный алгоритм для обеспечения связи через двумерную сетку двоичных значений. У меня есть довольно сложный алгоритм, который делает это за линейное время, но только при выполнении определенных шагов предварительной обработки....

Пусть G = (V, E) - взвешенный неориентированный связный граф, в котором веса всех ребер различны. Пусть T обозначает минимальное остовное дерево. Предположим, что G имеет m ≤ n + 157 ребер. Для этого особого случая дайте алгоритм MST, который...

У меня есть MST и мне нужно удалить узел. Я знаю, что для этого есть алгоритм в O(log^4(n)), но поскольку MST содержит менее 50 узлов и 2500 ребер, а ребра уже отсортированы, я хотел найти более простое решение: я создаю union для каждого...

Я прохожу курс Эндрю Нг по машинному обучению на Coursera. Обсуждая кластеризацию, он говорит нам, что алгоритм кластеризации K-средних является наиболее широко используемым. Ранее я также использовал алгоритм Крускала для кластеризации, который был...