Алгоритм Краскала |
Алгоритм Краскала |
Tan |
22.10.2007 17:07
Сообщение
#1
|
Профи Группа: Пользователи Сообщений: 559 Пол: Мужской Реальное имя: Бруно Репутация: 10 |
Всем привет! В данный момент занимаюсь реализацией алгоритма Краскала (построение минимального каркаса). Возникли следующий вопросы : Этот алгоритм действует только для неориентированного графа? Если существует несколько дуг с минимальным весом, предпочтительнее брать ту, которая была раньше введена? Спасибо.
-------------------- Цитата Imagination is more important than knowledge. Albert Einstein |
Lapp |
23.10.2007 1:44
Сообщение
#2
|
|||
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Tan, ну ты-то должен уметь ориентироваться на Форуме..
Раздел Теор.Вопросы - только по теории Паскаля! Для абстрактных вопросов, связанных с программированием, есть раздел Разработка ПО, алгоритмы, общие вопросы с его подразделами Алгоритмы и Общие Вопросы.. Твой вопрос ведь прямо тяготеет к Алгоритмам!
-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
|||
Tan |
23.10.2007 14:39
Сообщение
#3
|
Профи Группа: Пользователи Сообщений: 559 Пол: Мужской Реальное имя: Бруно Репутация: 10 |
Я думал изначально поместить тему в алгоритмы, но почему - то подумал, что речь идёт как бы о предпроцессе алгоритмизации, но с вашими аргументами я полностью солидарен. Извиняюсь. Сегодня я получил ответы на свои вопросы в этой теме. Ответы :1. да, для неорентированного. 2. Всё равно какую дугу брать первой при равном минимальном весе.
-------------------- Цитата Imagination is more important than knowledge. Albert Einstein |
Michael_Rybak |
24.10.2007 6:44
Сообщение
#4
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Для ориентированного графа нужно сначала определить понятие остова.
|
Tan |
24.10.2007 14:51
Сообщение
#5
|
Гость |
Сейчас приступил к реализации, появился вопрос. С сортировкой графа по весу всё понятно. Осталось отобрать дуги и составить каркас, для этого мне необходимо знать как програмно проверять граф на наличие цикла. Смотрел алгоритм virt, который предоставлен в FAQ, не особо улавливаю мысль.
|
Текстовая версия | 23.05.2024 20:28 |