Оригинальный DVD-ROM: eXeL@B DVD !
eXeL@B ВИДЕОКУРС !

ВИДЕОКУРС ВЗЛОМ
выпущен 2 сентября!


УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

ПРОГРАММИРОВАНИЕ НА C и С++



Слушай, дружище, зачем так мучиться с этим языком С++, ты ведь не Билл Гейтс. Возьми тот же Python и программируй, он кроссплатформенный, под Windows тоже работает. Я сам давно заметил: то что на Си пишешь в страницу кода, на питоне решается в одну-две строки. При том, питон намного проще, я его сам недавно изучил по видеокурсу вот этому. Кстати, автор отлично там объясняет. Буквально день-два и уже будешь писать на нём, чего не скажешь про сложный С++.

Построение остова минимального веса. Метод Прима-Краскала

Пусть n - это количество вершин графа. Тогда в цикле n-1 выбирается самое короткое еще не выбранное ребро при условии, что оно не образует цикла с уже выбранным. Для проверки того, что новое ребро не образует цикла с уже выбранными, каждую вершину i окрашивают в отличный от других цвет i. При выборе очередного ребра, скажем (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т. е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом после выбора n-1 ребер все вершины получают один цвет.

Алгоритм Прима-Краскала:

1. (ввод). Ввести матрицу расстояний D={dij}, i,j=1,…,n.

2. (инициализация). Приписать разные цвета всем вершинам: coli:=i; длина дерева L:=0.

3. (общий шаг). В цикле по k:=1 to n-1 do найти ребро минимальной длины между вершинами разного цвета: пусть это ребро (i,j).
Запомнить результат: res1[k]:=i; res2[k]:=j;
Перекрасить вершины: I1:=col[i]; j1:=col[j].
В цикле по m:=1 to n do
If col[m]=j1 then col[m]:=i1;
Нарастить длину дерева: L:=L+d[i,j].
Конец цикла по k.
4.(вывод). Вывести res1, res2.

Код программы записан на языке Object Pascal в среде Delphi 4.0, однако представляет определенный интерес, так что выставлена здесь вопреки тематике архива. Процедура решения задачи получает в качестве параметров количество вершин и матрицу расстояний. Результатом является массив ребер графа, построенного на этих вершинах и имеющего минимальный вес.

Скачать исходники и исполняемый модуль: kraskal.zip (258 Кб)


<< ВЕРНУТЬСЯ В ПОДРАЗДЕЛ

<< ВЕРНУТЬСЯ В ОГЛАВЛЕНИЕ




Материалы находятся на сайте https://exelab.ru/pro/



Оригинальный DVD-ROM: eXeL@B DVD !


Вы находитесь на EXELAB.rU
Проект ReactOS