помогите придумать ход решения

[Petruha-nsk]

Добрый вечер!
у меня по курсовику задача: "Найти длину кратчайшего цикла в графе". кто-нибудь подскажите пожалуйста, как можно представить подобное решение? заранее спасибо!

[Sazary]

Цикл охватывает все вершины?
Например:
решаете рекурсией. Берете одну из вершин. Вызываете рекурсивную функцию, где берете вторую вершину. Как аргумент функции должны передаваться последняя взятая вершина и "текущая сумма", а также счетчик (порядковый номер текущей вершины).
Если этот счетчик = количеству вершин, то считаем длину ребра между текущей и первой вершинами. Прибавляем к текущей сумме и сравниваем с "минимальной суммой" - глобальной переменной. Если эта сумма меньше минимальной, то пишем в "минимальный путь" текущий путь (который тянем от самого начала).

В общем, думаю, идея ясна.
После перебора всех комбинаций имеем цикл с минимальной длиной.

[Petruha-nsk]

а что если в качестве входного файла использовать так сказать матрицу,состоящюю из списка всех вершин и всех смежных с ней других вершин? например:
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
то реально ли вообще таким способом решить эту задачу?

[Sazary]

А, так у вас соединены конкретные вершины. Ну тогда по-другому надо делать.

Можно делать так, как вам удобно.
Еще есть такая штука, как матрица смежности. Довольно удобна для представления графов. Советую использовать ее.

То есть, циклы уже есть? Их не надо строить? Просто найти самый короткий?

Тогда решать можно также рекурсией. Выбираете вершину. Дальше идете к той, которая с ней соединена. И так пока не вернемся в начальную. Тогда сравниваем с "минимальной длиной".

[Petruha-nsk]

..........

[Petruha-nsk]

матрица смежности из 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
но представленная в динамической памяти это как раз то что надо. это и будет входными данными.
граф определен вершинами и смежными этой вершине вершинами. и вот нужно обходом (поиском) в глубину графа найти этот самый кратчайший цикл. как это сделать я ума не приложу

[MaTBeu]

Тема Литература. Там есть книга по алгоритмам на графах.