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