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

 
 Ответить  Открыть новую тему 
> Алгоритм Краскала
сообщение
Сообщение #1


Профи
****

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

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


Всем привет! В данный момент занимаюсь реализацией алгоритма Краскала (построение минимального каркаса). Возникли следующий вопросы : Этот алгоритм действует только для неориентированного графа? Если существует несколько дуг с минимальным весом, предпочтительнее брать ту, которая была раньше введена? Спасибо.


--------------------
Цитата
Imagination is more important than knowledge.
Albert Einstein
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Tan, ну ты-то должен уметь ориентироваться на Форуме..
Раздел Теор.Вопросы - только по теории Паскаля! Для абстрактных вопросов, связанных с программированием, есть раздел Разработка ПО, алгоритмы, общие вопросы с его подразделами Алгоритмы и Общие Вопросы.. Твой вопрос ведь прямо тяготеет к Алгоритмам!

М
Тема переносится в Алгоритмы



--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Профи
****

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

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


Я думал изначально поместить тему в алгоритмы, но почему - то подумал, что речь идёт как бы о предпроцессе алгоритмизации, но с вашими аргументами я полностью солидарен. Извиняюсь. Сегодня я получил ответы на свои вопросы в этой теме. Ответы :1. да, для неорентированного. 2. Всё равно какую дугу брать первой при равном минимальном весе.


--------------------
Цитата
Imagination is more important than knowledge.
Albert Einstein
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

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


Для ориентированного графа нужно сначала определить понятие остова.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Сейчас приступил к реализации, появился вопрос. С сортировкой графа по весу всё понятно. Осталось отобрать дуги и составить каркас, для этого мне необходимо знать как програмно проверять граф на наличие цикла. Смотрел алгоритм virt, который предоставлен в FAQ, не особо улавливаю мысль.
 К началу страницы 
+ Ответить 

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

 





- Текстовая версия 28.03.2024 22:16
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name