FasterHarder: В общем, немого полазив по зарубежным материалам (самую малость) сделал такие выводы (возможно, что ошибочные, но это и не важно) ) - на данный момент НЕ существует оптимального решения с тз кодирования (структур данных) алгоритма Прима...
Как только не делают: и через весовую матрицу, и через список смежности (тут вообще масса подвидов), и через КЧД (red-black tree, это ведь они), и через кучи, и даже вроде что-то на хешировании есть и пр. пр.
Оценка сложности различная и типа, если есть что-то O(n^2 + n*m), то, задействовав что-то, могут получить O(n^2 + nlog(m)) и это считается прогрессом и пр. Как делается оценка сложности - без понятия...
Я реализовал 2 дополнительных программы через список смежности:
1. получая отсортированные списки по весу
2. произвольные списки весов
Оба случая по скорости работы проиграли весовой матрице) + для поддержки отсортированности пришлось еще кучу всего доразбирать и додумывать. Понятно, что проблем в коде масса, поэтому эти программы "мусорные"...По скорости уж точно не должны были проиграть весовой матрице, хотя
Еще сложилось такое впечатление, что, типа, если ты можешь закодировать Прима через весовую матрицу, то можешь поставить галочку - знаешь этот алгоритм, ну, ок)
Возможно, что, если углубиться в исследовании структур данных, которые можно применить при кодировании алг.Прима, то можно писать и кандидатскую, и даже диссертацию.
В общем, я вроде хорошо понял, как работать с алгоритмом Прима через весовую матрицу (это считается самым тупым и медленным способом), буду считать, что знаю, что такое алгоритм Прима. И так сойдет (с) 8-)
Скрытый текст
На мой дилетантский взгляд: работать с графами через матрицу смежности/весов гораздо приятнее, чем через список смежности. Используя обращение m[i][j] моментально получаешь доступ к нужной тебе информации. Когда список смежности, то, например, на элементарный вопрос: "А существует ли связь между вершина №3 и №11?" моментально ответ хрен дашь - надо что-то там сканировать, проверять и пр. пр. (речь про язык Си). Конечно, если юзать стл-ские контейнеры, то значительно упрощается процесс кодирования всего этого (vector - вообще сказка) ), но это не отменяет того факта, что понимать при этом алгоритм все равно нужно максимально...
2. Мне не попался на глаза (возможно, плохо искал) ни один материал, который бы всеобъемлюще исследовал Прима, рассказывая об алгоритмах, а также об используемых структурах данных(!!), проводил замеры скорости работы в зависимости от выбранного подхода, от конфигурации графа и пр. пр. Даже близко не встречал ни одного материала, который бы закрывал все нюансы на 10% хотя бы...Одни отрывки + реализация на С++...
https://forum.sources.ru/index.php?showtopic=421519&view=findpost&p=3848193
