Алгоритм Прима (Уже не знаю куда бежать :))

[shulik]

Проблема следующая. Задали нам СРС (самост.раб.студента)
Мне по счастливой случайности достался алгоритм Прима (поиска минимального остовного дерева). И даже сказали где брать информацию по теме - книга Хезфилда. Но вот не задача - в этой книге есть расплывчатое описание самого алгоритма, а далее код программы. Я уже перерыл пол рунета - так и не смог найти нормального словесного описания этого алгоритма.
Буду очень благодарен, если кто-то поделится либо описанием тут, либо файликом с описанием. А то сроки уже поджимают, а воз и ныне там

[flook]

Я на память знаю только "жадный" алгоритм посика. Может это он?

[JaGoTerr]

А может попробуем попроще?
Запости-ка сюда то описание алгоритма, что есть в книге (именно то, которое в виде текста программы, хотя и словесное не помешает, если это возможно). А общими усилиями расшифруем и доведём до ума. имхо это куда реальнее, полезнее, интереснее и надёжнее.

ЗЫ: Просто в своё время тоже писал реализацию какого-то алгоритма. Посмотрел на псевдо-код сначала: нифига не понял. Посидел, поковырял, подумал - разобрался.

[t.t]

А может попробуем попроще?
Запости-ка сюда то описание алгоритма, что есть в книге (именно то, которое в виде текста программы, хотя и словесное не помешает, если это возможно). А общими усилиями расшифруем и доведём до ума. имхо это куда реальнее, полезнее, интереснее и надёжнее.

↑

Поддерживаю. :thumbsup:

[shulik]

Да в том то и дело - времени нет на глубокие вдумки

Описание:
Алгоритм Прима создает минимальное остовное дерево путем добавления единственного ребра (а также вершин) в дерево после определенного количества итераций. Вершины в графе разделяются на два набора: один, являющийся частью дерева, а другой нет. Во время каждой итерации ребро с минимальными затратами связывает любую вершину, являющуюся частью решения, с любой вершиной, которая еще не добавлена в это решение. Это происходит до тех пор пока в решение не будут добавлены все вершины, другими словами пока не будет выбрано V-1 ребер.
Шаги:
1. Выбрать корневую вершину V
2. Пометить V как посещенную
3. Для каждой смежной с V вершины установить затраты кратчайшего ребра
4. Выбрать непосещенную вершину с наименьшими затратами ребра в качестве текущей вершины V и добавить связывающее ребро в остовное дерево.
5. Повторить все шаги со второго, пока не будут посещены все вершины.


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

ЗЫ: Листинг пока не привожу - он длинный и написан в общем виде.... на сях

[flook]

Это оно! Описываю:

1. Берешь любую вершину.
2. Среди всех ребер исходящих из выбраных тобою вершин выбираешь самое короткое
note: каждое ребро имеет числовую хар-ку - вес или длину. Нужно выбирать минимальную.
3. Добавляешь к списку выбраных тобою вершин ту, к которой ведет это самое короткое ребро.
4. goto 2 пока не перебеорешь всех вершин.
note: ты гарантированно переберешь все, если граф односвязный.
note: пофиг до стартовой вершины - дерево все-равно выйдет одно и то же.

[t.t]

2. Среди всех ребер исходящих из выбраных тобою вершин выбираешь самое короткое

↑

Поправка: забыли написать "среди ведущих в непосещённые вершины", а то так можно и зациклиться.

[flook]

Согласен

[shulik]

2. Среди всех ребер исходящих из выбраных тобою вершин выбираешь самое короткое

↑

Поправка: забыли написать "среди ведущих в непосещённые вершины", а то так можно и зациклиться.

↑

Значит так:
как я понял исходный граф взвешенный???
и еще - а если граф не связный что делать?
или если например получили граф в виде звезды и изначально стояли в центре??

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

[t.t]

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

↑

Зависит от того, что имеется ввиду делать, если нельзя наложить связный маршрут. Если перейти к набору связных маршрутов, то так.

[shulik]

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

↑

Зависит от того, что имеется ввиду делать, если нельзя наложить связный маршрут. Если перейти к набору связных маршрутов, то так.

↑

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

[t.t]

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

↑

На каждом шаге выбирается кратчайшее ребро не из текущей вершины, а из всех посещённых. Так что связный граф (или каждую связную компоненту в случае несвязного графа) мы в итоге обойдём целиком всегда.

[shulik]

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

↑

На каждом шаге выбирается кратчайшее ребро не из текущей вершины, а из всех посещённых. Так что связный граф (или каждую связную компоненту в случае несвязного графа) мы в итоге обойдём целиком всегда.

↑

Ясно. Спасибо за помощь. Как будет что-нибудь готово постараюсь не забыть запостить сюда результат