Как найти цикл максимальной длины

Попробуем написать функцию, которая поиском в глубину найдет все циклы, начиная от заданной вершины

IEnumerable<Stack<int>> FindAllCycles(int[,] edges, int currentV, HashSet<int> alreadyVisited, Stack<int> currentPath)
{
    if (alreadyVisited.Contains(currentV))
    {
        var ret = new Stack<int>();
        ret.Push(currentV);
        foreach (var v in currentPath)
        {
            ret.Push(v);
            // Крутим путь только до начала цикла
            if (v == currentV) break;
        }

        yield return ret;
    }
    else
    {
        alreadyVisited.Add(currentV);
        currentPath.Push(currentV);

        for (int i = 0; i < edges.GetLength(1); i++)
            if (currentV != i && edges[currentV, i] == 1)
                foreach (var cycle in FindAllCycles(edges, i, alreadyVisited, currentPath)) yield return cycle;

        alreadyVisited.Remove(currentV);
        currentPath.Pop();
    }
}

Далее, надо будет запустить эту функцию для каждой вершины и, по сути, получить все циклы, из полученных циклов вернуть цикл максимальной длины.

var vertices = new Dictionary<int, char>() { { 0, 'А' }, { 1, 'Б' }, { 2, 'В' }, { 3, 'Г' }, { 4, 'Д' } };

var edges = new int[,] {
    {0, 1, 1, 0, 0},
    {0, 0, 1, 0, 1},
    {0, 0, 0, 0, 1},
    {1, 1, 0, 0, 0},
    {0, 0, 0, 1, 0},
};

var allCycles = vertices.Keys.SelectMany(x => FindAllCycles(edges, x, new HashSet<int>(), new Stack<int>()));
Stack<int> maxCycle = null;

foreach(var cycle in allCycles){
    if (maxCycle == null || maxCycle.Count < cycle.Count)
        maxCycle = cycle;
}   

if (maxCycle == null)   
    Console.WriteLine("No cycles!");    
else    
    Console.WriteLine(String.Join('-', maxCycle.Select(m => vertices[m])));

Вывод в консоль

А-Б-В-Д-Г-А

Сразу скажу, алгоритм далек от идеала и тут есть что улучшать, но он вроде работает на ваших данных. На большом графе с кучей ребер и кучей циклов со скоростью будет не важно.

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 27 октября 2021 года; проверки требует 1 правка.

Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо (в случае взвешенных графов) суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является NP-трудной и не может быть решена за полиномиальное время для произвольных графов, если только не P = NP. Принадлежность более тяжелому классу сложности также означает, что задачу трудно аппроксимировать. Однако задача решается за линейное время на ориентированных ациклических графах, которые имеют важное применение в задачах нахождения критического пути в задачах планирования.

NP-трудность[править | править код]

NP-трудность невзвешенной задачи поиска самого длинного пути можно показать, сведя задачу к поиску гамильтонова пути^[en] — граф G имеет гамильтонов путь тогда и только тогда, когда самый длинный путь в нём имеет длину n − 1, где n — число вершин графа G. Поскольку задача поиска гамильтонова пути является NP-полной, это сведение показывает, что задачи поиска самого длинного пути в варианте разрешимости также NP-полна. В этой задаче разрешимости входом является граф G и число k. Ожидается выход “да”, если G содержит путь с k и больше дугами, или нет в противном случае^[1].

Если бы задача поиска самого длинного пути могла быть решена за полиномиальное время, она могла бы быть использована для решения этой задачи разрешимости путём нахождения самого длинного пути и сравнения длины полученного пути с числом k. Таким образом, задача поиска самого длинного пути является NP-трудной. Она не является NP-полной, поскольку она не является задачей разрешимости^[2].

Во взвешенных полных графах с неотрицательными весами рёбер задача поиска взвешенного самого длинного пути является той же самой задачей, что и задача коммивояжёра, поскольку самый длинный путь всегда включает все вершины этой задачи^[3].

Ацикличные графы и критические пути[править | править код]

Самый длинный путь A между двумя заданными вершинами s и t во взвешенном графе G — это то же самое, что и кратчайший путь в графе −G, полученном из G путём замены всех весов на веса с обратным знаком. Таким образом, если кратчайший путь можно найти в −G, то можно найти и самый длинный путь в G^[4].

Для большинства графов такое преобразование бесполезно, поскольку создаёт циклы отрицательной длины в −G. Но если G является ориентированным ациклическим графом, невозможно создать отрицательный цикл и самый длинный путь в G может быть найден за линейное время, применив алгоритм поиска кратчайшего пути в −G (тоже ориентированный ациклический граф), который работает за линейное время^[4]. Например, для любой вершины v в ориентированном ациклическом графе длина самого длинного пути, заканчивающегося в v, может быть получена выполнением следующих шагов:

1. Осуществляем топологическую сортировку заданного ориентированного ациклического графа (ОАГ).
2. Для каждой вершины v ОАГ в топологической сортировке вычисляем длину самого длинного пути, завершающегося в вершине v путём просмотра входящих дуг от соседей и добавления единички к максимальной длине в записях этих соседей. Если v не имеет входящих дуг, присваиваем длину самого длинного пути, кончающегося в v, нулю.

Когда это будет сделано, самый длинный путь во всём графе можно получить, начав с вершины v с самым большим записанным значением и проходя в обратном порядке, выбирая входящую дугу, у которой запись в начальной вершине имеет наибольшее значение.

Метод критического пути для планирования набора работ использует построение ориентированного ацикличного графа, в котором вершины представляют узловые события проекта, а дуги представляют работы, которые должны быть выполнены до узлового события и после него. Каждой дуге присваивается вес, равный оценочному времени выполнения работы. В таком графе самый длинный путь от первого узлового события до последнего является критическим путём, который определяет полное время завершения проекта^[4].

Самый длинный путь ориентированных ацикличных графов можно применить также для послойного рисования графов — располагаем каждую вершину v ориентированного ацикличного графа G на уровне, номер которого соответствует длине самого длинного пути, заканчивающегося в v. В результате получим расположение вершин по уровням, при котором число уровней будет минимальным^[5].

Приближение[править | править код]

Бьёрклунд, Хасфелдт и Канна писали, что задача поиска самого длинного пути в невзвешенном неориентированном графе является «печально известной по сложности понимания её трудности аппроксимации»^[6].
Лучший известный алгоритм аппроксимации полиномиального времени выполнения даёт лишь очень слабую аппроксимацию, ^[7]. Для любого невозможно аппроксимировать самый длинный путь со множителем, меньшим , если только NP не принадлежит задачам квазиполиномиального детерминированного времени. Однако существует большой разрыв между этим результатом аппроксимируемости и известными алгоритмами аппроксимации для этой задачи^[8].

В случае невзвешенных, но ориентированных графов известные сильные результаты аппроксимируемости. Для любого задача не может быть аппроксимирована в пределах , если только не P = NP, и, при сильных теоретических предположениях, задачу нельзя аппроксимировать в пределах ^[6]. Можно использовать технику цветовой кодировки^[en] для поиска пути логарифмической длины, если он существует, но эта техника даёт аппроксимационный коэффициент лишь ^[9].

Параметризованная сложность[править | править код]

Задача поиска самого длинного пути является фиксированно-параметрически разрешимой^[en], если параметризовать её по длине пути. Например, задача может быть решена за время, линейно зависящее от размера входного графа (но за экспоненциальное время по длине пути), с помощью алгоритма, делающего следующие шаги:

1. Осуществляем поиск в глубину по графу. Пусть — глубина результирующего дерева поиска вглубь.
2. Используем пути от корня к листам поиска дерева вглубь в порядке, в котором они просматриваются при поиске, в отличие от путевой декомпозиции графа с путевой шириной .
3. Используем динамическое программирование к этому разложению на пути для нахождения самого длинного пути за время , где — число вершин графа.

Поскольку выходной путь имеет длину по меньшей мере , время работы также будет ограничено значением , где — длина самого длинного пути^[10]. Используя цветовую кодировку, зависимость от длины пути может быть сведена к одиночно экспоненциальной^[11][12][13]. Похожая техника динамического программирования показывает, что задача нахождения самого длинного пути является также фиксированно-параметрически разрешимой по древесной ширине графа.

Для графов с ограниченной кликовой шириной задачу о самом длинном пути можно решить за полиномиальное время с помощью алгоритма динамического программирования. Однако степень полинома зависит от кликовой ширины графа, так что эти алгоритмы не являются фиксированно-параметрически разрешимыми. Задача нахождения самого длинного пути, параметризованная по ширине клик, является трудной для класса парметризованной сложности^[en] , что говорит о том, что вряд ли существует фиксированно-параметрически разрешимый алгоритм^[14].

Специальные случаи графов[править | править код]

Задачу о самом длинном пути можно решить за полиномиальное время на дополнениях графов сравнимости^[15]. Её можно решить также за полиномиальное время на любом классе графов с ограниченной древесной шириной или ограниченной кликовой шириной, таком как дистанционно-наследуемые графы. Однако задача является NP-трудной, даже если ограничимся расщепляемыми графами, круговыми графами или планарными графами^[16].

См. также[править | править код]

• Теорема Галлаи – Хассе – Роя – Витавера, двойственность самого длинного пути и раскраски графов
• Задача о ходе коня
• Задача о змее в коробке, самый длинный порождённый путь в графе гиперкуба

Примечания[править | править код]

Литература[править | править код]

Ссылки[править | править код]

• “Find the Longest Path”, песня Дана Барретта (Dan Barrett)

Максимальный цикл в графе

shadeofgray	Сообщ. #4 , 25.04.06, 12:29
Moderator Рейтинг (т): 30	Расшифровывая сказанное выше: перебор, перебор и только полный перебор всех циклов. Приведенная ссылка позволяет оптимизировать перебор, но ценой того, что находятся не самые длинные циклы, а просто “немного длинные”

0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)

0 пользователей: