|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
12.04.2009, 20:39 | #1 |
Пользователь
Регистрация: 10.04.2009
Сообщений: 69
|
помогите придумать ход решения
Добрый вечер!
у меня по курсовику задача: "Найти длину кратчайшего цикла в графе". кто-нибудь подскажите пожалуйста, как можно представить подобное решение? заранее спасибо! |
12.04.2009, 21:11 | #2 |
В тени
Старожил
Регистрация: 19.12.2008
Сообщений: 5,788
|
Цикл охватывает все вершины?
Например: решаете рекурсией. Берете одну из вершин. Вызываете рекурсивную функцию, где берете вторую вершину. Как аргумент функции должны передаваться последняя взятая вершина и "текущая сумма", а также счетчик (порядковый номер текущей вершины). Если этот счетчик = количеству вершин, то считаем длину ребра между текущей и первой вершинами. Прибавляем к текущей сумме и сравниваем с "минимальной суммой" - глобальной переменной. Если эта сумма меньше минимальной, то пишем в "минимальный путь" текущий путь (который тянем от самого начала). В общем, думаю, идея ясна. После перебора всех комбинаций имеем цикл с минимальной длиной.
Вполне очевидно, чтобы что-то понять, необходимо книги читать.
Не нужно плодить бессмысленных тем. Вас Поиск избавит от многих проблем. ___________________________________ ___________________________________ _______ [=Правила форума=]_____[Поиск]_____[Литература по С++]____[Литература. Паскаль] |
12.04.2009, 21:20 | #3 |
Пользователь
Регистрация: 10.04.2009
Сообщений: 69
|
а что если в качестве входного файла использовать так сказать матрицу,состоящюю из списка всех вершин и всех смежных с ней других вершин? например:
1 2 5 // вершина №1, смежные ей 2 и 5 2 1 3 4 // вершина №2,смежные ей 1,3 и 4 3 2 4 // и т.д. 4 2 3 5 5 1 4 в итоге редставить в оперативной памяти в виде двумерного массива следующую матрицу: 1 2 3 4 5 2 1 2 2 1 5 3 4 3 4 0 4 0 5 0 0 0 0 0 0 то реально ли вообще таким способом решить эту задачу? |
12.04.2009, 21:38 | #4 |
В тени
Старожил
Регистрация: 19.12.2008
Сообщений: 5,788
|
А, так у вас соединены конкретные вершины. Ну тогда по-другому надо делать.
Можно делать так, как вам удобно. Еще есть такая штука, как матрица смежности. Довольно удобна для представления графов. Советую использовать ее. То есть, циклы уже есть? Их не надо строить? Просто найти самый короткий? Тогда решать можно также рекурсией. Выбираете вершину. Дальше идете к той, которая с ней соединена. И так пока не вернемся в начальную. Тогда сравниваем с "минимальной длиной".
Вполне очевидно, чтобы что-то понять, необходимо книги читать.
Не нужно плодить бессмысленных тем. Вас Поиск избавит от многих проблем. ___________________________________ ___________________________________ _______ [=Правила форума=]_____[Поиск]_____[Литература по С++]____[Литература. Паскаль] |
13.04.2009, 13:03 | #5 |
Пользователь
Регистрация: 10.04.2009
Сообщений: 69
|
..........
Последний раз редактировалось Petruha-nsk; 13.04.2009 в 16:02. |
13.04.2009, 16:02 | #6 |
Пользователь
Регистрация: 10.04.2009
Сообщений: 69
|
матрица смежности из 1 и 0 не совсем удобна. а вот та таблица:
1 2 5 // вершина №1, смежные ей 2 и 5 2 1 3 4 // вершина №2,смежные ей 1,3 и 4 3 2 4 // и т.д. 4 2 3 5 5 1 4 но представленная в динамической памяти это как раз то что надо. это и будет входными данными. граф определен вершинами и смежными этой вершине вершинами. и вот нужно обходом (поиском) в глубину графа найти этот самый кратчайший цикл. как это сделать я ума не приложу |
13.04.2009, 18:31 | #7 |
Eclipse Foundation
Старожил
Регистрация: 19.09.2007
Сообщений: 2,604
|
Тема Литература. Там есть книга по алгоритмам на графах.
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Помогите... Нужно придумать тему для... | tilekus | Свободное общение | 5 | 15.02.2009 10:46 |
Помогите придумать тему курсовой | lastochka | Свободное общение | 5 | 22.12.2008 19:58 |
Помогите придумать алгоритм | Raz0r | Помощь студентам | 2 | 12.10.2008 10:49 |
Не могу придумать или подобрать формулу! Помогите! | Gnom70 | Microsoft Office Excel | 4 | 30.01.2008 11:01 |
помогите придумать тему для дипломного проекта. | createru | Помощь студентам | 2 | 26.09.2007 17:15 |