Лучшие minimum-spanning-tree вопросы ИТ разработчиков

  • 12 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Как обновить приоритеты элементов в куче для алгоритма Прима?

Я изучаю алгоритм Прима. В коде есть часть, следующая вершина которой будет проходить через множество вершин, принадлежащихMST, При этом мы также должны «обновить все вершины в другом наборе, которые смежны с уходящей вершиной». Это снимок ...

Задан 12 Jun 2013, 21:15 от SexyBeast
  • 66 голосов
  • 10 ответов
  • 0 просмотров
10 ответов

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

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

Задан 03 Jan 2013, 17:45 от anuj pradhan
  • 0 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Евклидово минимальное остовное дерево без триангуляции

Я просматривал текст о поиске EMST (евклидова MST) с использованием техники триангуляции Делоне, но также где-то читал, что EMST можно найти с помощью алгоритма линии развертки. Так как это будет легче реализовать, я хотел бы реализовать это, а ...

Задан 09 Nov 2012, 19:30 от Aman Gupta
  • 49 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Отдельные товарные мульти-терминальные потоки

ает ли на нем противоположность алгоритма Крускала для минимального связующего дерева? Я имею в виду, выбирая максимальный вес (ребро) каждого шага? Любая другая идея, чтобы найти максимальное связующее дерево?

Задан 14 Feb 2011, 13:26 от user467871
  • 11 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Быстрый алгоритм для минимальных остовных деревьев, когда длина ребер ограничена?

Предположим, что у вас есть ориентированный граф с неотрицательными целочисленными длинами ребер, которые находятся в диапазоне от 0 до U - 1 включительно. Какой самый быстрый алгоритм для вычисления минимального остовного дерева этого графа? Мы ...

Задан 15 Jan 2012, 23:25 от templatetypedef
  • 169 голосов
  • 10 ответов
  • 0 просмотров
10 ответов

Крускал против Прим

Мне было интересно, когда следует использоватьАлгоритм Прима и когдаКрускала & APOS; s найти минимальное остовное дерево? Они оба имеют простую логику, одина...

Задан 06 Jul 2012, 20:20 от templatetypedef
  • 8 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Определить, имеет ли данный взвешенный граф уникальный MST

Я ищу алгоритм (или любой другой способ), чтобы определить, имеет ли данный взвешенный граф уникальный MST (минимальное связующее дерево) в O (ElogV)? Я ничего не знаю о весах (например, вес (e1)! = Вес (e2)), и алгоритм просто возвращает True, ...

Задан 25 Jun 2013, 21:29 от TomerGod
  • 8 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Определить, имеет ли данный взвешенный граф уникальный MST

m ищет алгоритм (или любой другой способ), чтобы определить, имеет ли данный взвешенный граф уникальный MST (минимальное связующее дерево) в O (ElogV)?Я неМы...

Задан 25 Jun 2013, 19:29 от TomerGod
  • 6 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Как найти общее количество минимальных остовных деревьев в графе?

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

Задан 13 Dec 2012, 05:53 от 2147483647
  • 12 голосов
  • 5 ответов
  • 0 просмотров
5 ответов

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

Дейкстры [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm]обычно используется для нахождения кратчайшего расстояния между двумя узлами на графике. Можно ли его использовать, чтобы найти минимумостовное ...

Задан 15 Dec 2009, 18:08 от Nick Heiner
  • 7 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Алгоритм нахождения минимального остовного дерева выбранных вершин

Можно использовать алгоритм Прима или алгоритм Крускала, чтобы найти минимальное остовное дерево / граф совокупности вершин / узлов и ребер / связей. Однако мне нужен алгоритм, который находит минимальный остовный граф этой коллекции, ...

Задан 30 Oct 2012, 19:58 от Tespa42
  • 14 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Нахождение минимального остовного дерева на ориентированном графе

Какой алгоритм я могу использовать, чтобы найти минимальное остовное дерево на ориентированном графе? Я попытался использовать модификацию алгоритма Прима, н...

Задан 24 Feb 2014, 15:24 от user3347255
  • 12 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Как обновить приоритеты элементов в куче для алгоритма Прима?

Я изучаю примАлгоритм с. В коде есть часть, следующая вершина которой будет проходить через множество вершин, принадлежащих

Задан 12 Jun 2013, 19:15 от SexyBeast
  • 12 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

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

Я изучаю теорию графов, и у меня есть вопрос о связи между минимальными связующими деревьями и деревьями кратчайших путей. ПозволятьGбыть неориентированным связным графом, где все ребра взвешеныс разными затратами, ПозволятьTбыть MSTGи разрешиTs ...

Задан 13 Jun 2013, 17:53 от Spartacus