|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
17.01.2010, 02:15 | #1 |
Новичок
Джуниор
Регистрация: 17.01.2010
Сообщений: 7
|
Как проверить граф на связанность? Алгоритм Краскала
ЗАДАЧА О СЕТИ ДОРОГ НАИМЕНЬШЕЙ СТОИМОСТИ.
Задание Написать программу на языке «Си», которая решает задачу о сети дорог наименьшей стоимости. Дан связный неориентированный граф J, причем каждому ребру (i, j) приписан «вес», который можно понимать как стоимость дороги между пунктами i и j. Требуется выбрать из всех ребер графа такую совокупность, что по этим ребрам можно было бы пройти из любого пункта в любой другой, и чтобы общий вес этих ребер был минимальным. Как проверить граф на связанность? Т. е. на то, что из каждой вершины можно попасть в любую другую. Задача решается алгоритмом Краскала. Исходный код программы ниже или в прикрепленном документе Очень жду помощи! буду очень благодарна! Последний раз редактировалось PasSuper; 17.01.2010 в 12:17. |
17.01.2010, 02:18 | #2 |
Новичок
Джуниор
Регистрация: 17.01.2010
Сообщений: 7
|
исходный код программы:
Код:
Последний раз редактировалось PasSuper; 17.01.2010 в 02:43. |
17.01.2010, 02:44 | #3 |
Новичок
Джуниор
Регистрация: 17.01.2010
Сообщений: 7
|
Код:
|
17.01.2010, 13:48 | #4 | |
Eclipse Foundation
Старожил
Регистрация: 19.09.2007
Сообщений: 2,604
|
Цитата:
|
|
17.01.2010, 13:55 | #5 |
Новичок
Джуниор
Регистрация: 17.01.2010
Сообщений: 7
|
Суть мне понятна. Ребра сортируются по возрастанию их веса. Через первое ребро точно есть дорога. Дальше перебором ищется следующее ребро (допустим дорога точно идет через ребро 1-3, тогда следующим будет ребро, у которого есть вершина 1 или 3 с наименьшим весом). В итоге, если после такого перебора не удалось добраться до каких-то вершин - будет ошибка. Допустим, всего 7 вершин, а перебрали мы всего 4 ->до остальных вершин путей нет.
Но я не понимаю, как это реализовать. Знаю, что скорее всего проверка должна быть в фунции SearchTree, там как раз выше описанный алгоритм реализуется. Я просто не понимаю, как именно это сделать. |
17.01.2010, 14:58 | #6 |
Пользователь
Регистрация: 11.01.2010
Сообщений: 24
|
не совсем понимаю, что нужно... можете сделать пару рисунков (хоть в paint-е) и вложить сюда?
|
17.01.2010, 15:41 | #7 |
Новичок
Джуниор
Регистрация: 17.01.2010
Сообщений: 7
|
Во вложении объяснила еще раз алгоритм на конкретном примере. Надо проверить, не является ли граф разорванным.
|
17.01.2010, 15:43 | #8 | |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
Чтоб был именно Краскал, надо после сортировки пройтись по всем ребрам, и для каждого ребра проверять, соеденяет ли оно 2 пока несвязанных подмножества вершин (2 пока определенные разные компоненты связности). Если да - объеденить эти 2 подмножества. Тогда можно не проверять вначале связность, а посмотреть вконце - сколько компонент связности получилось. Если сравнивать с простой проверкой на связность вначале - это работает быстрее, если с "умной" - это кодить меньше надо. |
|
17.01.2010, 15:52 | #9 |
Новичок
Джуниор
Регистрация: 17.01.2010
Сообщений: 7
|
по крайней мере, так объяснил мой преподаватель. Значит нужно так делать...
Помогите с реализацией, пожалуйста! |
17.01.2010, 22:00 | #10 |
Пользователь
Регистрация: 11.01.2010
Сообщений: 24
|
Вот так у меня задаются ребра:
Код:
Вот так я проверяю на связанность: Код:
Затем перебираются все ребра и если в ребре хотябы одна точка уже присоединена к системе, то обоим присваивается значение true. Затем значения всех элементов point логически перемножаются. Если все элементы point равны единице(true), то и результат перемножения равен единице - значит граф связанный. Если же хотя бы один элемент point равен нулю(false) - то результат перемножения всех элементов равен нулю - значит граф не связанный. Этот алгоритм будет работать только в том случае, если в массиве reb все певые элементы строк (первая точка ребра) - будут раполагаться по возрастанию. В противном случае нужно сначала сортировать массив reb. По исходным данным, конечно, граф не связанный. Насчет алгоритма Краскала - спросил у википедии. Встаю на сторону PasSuper. Запрограммировал этот алгоритм и изменил исходные данные для первой точки вот так: ...1,6,2,... , чтобы связать граф. При таких исходных данных он мне подключил следующие ребра (по порядку подключения) №6, №4, №2, №1, №9, №8. Надеюсь, это правильно... |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм преобразования дорожной сети в граф, для поиска пути | motorway | PHP | 7 | 02.10.2009 18:53 |
Алгоритм Краскала | anGeee | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 17.12.2008 18:16 |
как организовать граф(очень специфический) | Kurk_SS | Общие вопросы Delphi | 10 | 09.05.2008 08:06 |