IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Нахождение минимального остового дерева(алгоритм Краскала)
nblazhko
сообщение 16.05.2008 22:46
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 42
Пол: Мужской

Репутация: -  0  +


Вот что я смог сделать но она выводит вершины не правельно, подскажите плиз


Program Algorithm_PrimaKrascala;
Uses Crt;
Const MaxSize =100;
Infinity =1000;
Var Matrix: array[1..MaxSize, 1..MaxSize] of integer;
Color: array[1..MaxSize] of integer;
Ribs: array[1..MaxSize] of record
a, b: integer;
end;
n, a, b, k, col, i, len: integer;

Procedure Init;
Var f: text;
i, j: integer;
Begin
Assign(f, 'INPUT.MTR');
Reset(f);
Readln(f, n);
For i:=1 to n do
Begin
For j:=1 to n do read(f, matrix[i, j]);
Readln(f)
End;
For i:=1 to n do color[i]:=i;
len:=0
End;

Procedure Findmin(var a, b: integer);
Var min, i, j: integer;
Begin
min:=infinity;
For i:=1 to n-1 do
For j:=i+1 to n do
If (Matrix[i, j]<>color[j]) then
Begin
min:=Matrix[i, j];
a:=i;
b:=j
End;
len:=len+min
end;

Begin
Clrscr;
Init;
For k:=1 to n-1 do
Begin
Findmin(a, b);
Ribs[k].a:=a;
Ribs[k].b:=b;
col:=Color[b];
For i:=1 to n do
If color[i]=col then color[i]:=color[a];
End;
For i:=1 to n-1 do
Writeln(ribs[i].a, ' -', ribs[i].b);
Writeln('Length= ', len);
Readkey
End.



Matrix - матрица расстояний, значение пересечении i-ой строки и j-го столбца равно расстоянию между i-ой и j-ой вершинами. Если такого ребра нет то значение равно Infinity - просто большому числу
Color - массив цветов вершин;
Ribs - в этом массиве запоминаются найденные ребра;
a, b - вершины, соединяемые очередным минимальным ребром
len - длина дерева.
Матрицу расстояний будем хранить в текстовом файле INPUT.MTR, где число на первой строке - количество вершин n, а остальные n строк по n чисел в каждой - матрица расстояний. Если расстояние равно 1000 (Infinity), то такого ребра нет.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 18.07.2025 13:54
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"