Помогите с сортировкой Опции

[RussoTuristo]

Задача состоит в нахождении минимального остова графа ... Задаю матрицу смежности ( элементу матрицы a[i,j]:=w, где w - вес ребра)
Мне нужно отсортировать рёбра по весу, задача вроде лёгкая, но либо я туплю, либо всё не так просто ...

For i:=1 to n do
   For j:=1 to n do
   if Pred a[i,j]< a[i,j] then .....

Хотел использовать пузырьковую сортировку ...
Проблема состоит в том что я не знаю как записать предыдущий элемент...
Или может как-то по-другому надо поступать?

Сообщение отредактировано: RussoTuristo - 18.12.2008 21:29

[volvo]

Переписали в массив

Ты ничего в массив не переписал:

k:=0;
for i:=1 to n do
   for j:=1 to n do
   inc(k); { <--- В цикле у тебя выполняется только этот оператор }
   a[i,j]:=b[k];
   p:=k;

, то есть все, чего ты добился - это изменение в цикле K, и присваивания непонятно чему (после цикла в переменных I, J может храниться все, что угодно) значения b[ K ]...

P.S. Нахождение мин. остова алгоритмами Прима и Краскала есть здесь: графы

Будет проще из твоей матрицы смежности сделать список ребер, и прогнать алгоритм Краскала, чем изобретать велосипед...

[RussoTuristo]

спасибо, насчет массива понял, забыл begin end

А насчет алгоритмов, не мог бы кто-нибудь пояснить алгоритмы, приведенные в ссылках ..

Мне надо решить жадным алгоритмом, т.е найти ребро минимального веса, окрасить вершины, инцидентные этому ребру. Затем найти ребро минимального веса, смежное найденному и т.д.
Просто сложновато разобраться в алгоритмах, они там без пояснений. По-моему алгоритм Прима похож на нужный мне (Насколько я понимаю их отличие в том, что алгоритм прима в качестве начальной берет первую попавшуюся вершину, а жадный - нужный мне, для начала берет ребро минимального веса, вроде правильно понял и если там представлена реализация этого алгоритма Прима) ...