Как найти самый длинный цикл в графе

I have an answer explaining an easy way to find all cycles in a directed graph using Python and networkX in another post. Finding all cycles in a directed graph

The solution will output a list containing all cycles of the directed graph.

You can use this output to find the longest cycle ans it is shown bellow:

import networkx as nx

# Create Directed Graph
G=nx.DiGraph()

# Add a list of nodes:
G.add_nodes_from(["1","2","3","4","5","6","7","9"])

# Add a list of edges:
G.add_edges_from([("7","9"),("1","2"),("2","3"),("3","1"),("3","4"),("4","5"),("5","1"),("5","6"),("6","7"),("7","2")])

#Return a list of cycles described as a list o nodes
all_cycles = list(nx.simple_cycles(G))

#Find longest cycle
answer = []
longest_cycle_len = 0
for cycle in all_cycles:
    cycle_len = len(cycle)
    if cycle_len>longest_cycle_len:
        answer =cycle
        longest_cycle_len = cycle_len

print "Longest Cycle is {} with length {}.".format(answer,longest_cycle_len)

Answer: Longest Cycle is [‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘2’] with length 6.

If you find it interesting upvote up the original answer too. It is an old discussion with many answers and it will help bringing the new solution up.

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 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)

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

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])));

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

А-Б-В-Д-Г-А

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

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

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

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

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

У меня есть ответ, объясняющий простой способ найти все циклы в ориентированном графе с использованием Python и networkX в другом сообщении. Нахождение всех циклов в ориентированном графе

Решение выведет список, содержащий все циклы ориентированного графа.

Вы можете использовать этот вывод, чтобы найти самый длинный цикл, как показано ниже:

import networkx as nx

# Create Directed Graph
G=nx.DiGraph()

# Add a list of nodes:
G.add_nodes_from(["1","2","3","4","5","6","7","9"])

# Add a list of edges:
G.add_edges_from([("7","9"),("1","2"),("2","3"),("3","1"),("3","4"),("4","5"),("5","1"),("5","6"),("6","7"),("7","2")])

#Return a list of cycles described as a list o nodes
all_cycles = list(nx.simple_cycles(G))

#Find longest cycle
answer = []
longest_cycle_len = 0
for cycle in all_cycles:
    cycle_len = len(cycle)
    if cycle_len>longest_cycle_len:
        answer =cycle
        longest_cycle_len = cycle_len

print "Longest Cycle is {} with length {}.".format(answer,longest_cycle_len)

Ответ: Самый длинный цикл – [‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘2’] с длиной 6.

Если вам это интересно, проголосуйте за исходный ответ. Это старое обсуждение с множеством ответов, и оно поможет найти новое решение.