VPF::[pascal] Алгоритм "ближайшего соседа"

Hely

Дата 25.5.2008, 07:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 41
Регистрация: 20.11.2006
Где: Россия

Репутация: нет
Всего: нет

Необходимо реализовать на Паскале построение минимального остовного дерева графа с помощью алгоритма Прима (т.н. алгоритм "ближайшего соседа").
О самом алгоритме: не требует сортировки и проверки на цикличность на каждом шаге.
Шаг 1) Построение остовного дерева графа начинается с произвольной вершины x1.
Шаг 2) Среди ребер, соседних (инцидентных) x1выбирается ребро (x1,x2) с наименьшим весом, и включается в остовное дерево.
Шаг 3) Повторяя процесс, выполняем поиск наименьшего по весу ребра, соединяющего вершины (x1,x2) с нек-й другой вершиной х3.
Шаг 4) Процесс включения ребер продолжается до тех пор, пока все вершины исходного графа не будут включены в остовное дерево.
Также см. описание алгоритма.
Программа должна брать входные данные из файла in.txt, к-й выглядит примерно так:
7
0 20 0 0 0 23 1
20 0 15 0 0 0 4
0 15 0 3 0 0 9
0 0 3 0 17 0 16
0 0 0 17 0 28 25
23 0 0 0 28 0 36
1 4 9 16 25 36 0
Это матрица весов графа, а 7 в первой строке - размерность матрицы.
Выводить ответ необходимо также в текстовый файл out.txt, в виде:
Остовное дерево
1-7
7-2
7-3
3-4
и т.д.

Я написала программу, но он выводит неправильный ответ. В чем ошибка?

Код


program poisk_sosed;
uses crt;
var matrix:array[1..50,1..50] of integer;
der:array[1..100,1..2] of byte;
n,i,j,x,y,ves,k:byte;
f_in,f_out:text;

begin
assign(f_in,'in.txt');
reset(f_in);
assign(f_out,'out.txt');
rewrite(f_out);
readln(f_in,n);
for i:=1 to n do
    begin
        for j:=1 to n do
        read(f_in,matrix[i,j]);
        readln(f_in);
    end;
for i:=1 to n do
    begin
        for j:=1 to n do    
        write(f_out,matrix[i,j]);
        writeln(f_out);
    end;

x:=1; y:=1; i:=1;
ves:=matrix[1,1];
while k<>n do
begin 
    for j:=1 to n do
    if (matrix[i,j]<ves) and (matrix[i,j]<>0) then 
    begin
        ves:=matrix[i,j];
        der[x,y]:=i; der[x,y+1]:=j;
        inc(x);
        i:=j; 
    end;
k:=k+1;
end;            

writeln(f_out,'Остовное дерево');
for x:=1 to n do for y:=1 to n do
writeln(f_out,der[x,1]:3,der[x,2]:3);
close(f_out);
close(f_in);
end.

Помогите, пожалуйста, это последняя задача smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »