Алгоритм Краскала Опции

[Tan]

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

[Lapp]

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

М

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

[Tan]

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

[Michael_Rybak]

Для ориентированного графа нужно сначала определить понятие остова.

[Tan]

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