Алгоритмы для идентификации всех оснований цикла в неориентированном графе

я бы начал с рассмотрения любого алгоритма минимального связующего дерева (Prim, Kruskal и т. Д.). Базовых циклов не может быть больше (если я правильно понимаю), чем ребер, которых НЕТ в MST ....

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

Этот подход можно расширить, чтобы записать циклы, найденные таким образом, и двигаться дальше.

Ниже приведен мой реальный непроверенный код C # для поиска всех этих «базовых циклов»:

public HashSet<List<EdgeT>> FindBaseCycles(ICollection<VertexT> connectedComponent)
{
   Dictionary<VertexT, HashSet<List<EdgeT>>> cycles =
       new Dictionary<VertexT, HashSet<List<EdgeT>>>();

   // For each vertex, initialize the dictionary with empty sets of lists of
   // edges
   foreach (VertexT vertex in connectedComponent)
       cycles.Add(vertex, new HashSet<List<EdgeT>>());

   HashSet<EdgeT> spanningTree = FindSpanningTree(connectedComponent);

   foreach (EdgeT edgeNotInMST in
           GetIncidentEdges(connectedComponent).Except(spanningTree)) {
       // Find one cycle to split, the HashSet resulted from the intersection
       // operation will contain just one cycle
       HashSet<List<EdgeT>> cycleToSplitSet =
           cycles[(VertexT)edgeNotInMST.StartPoint]
               .Intersect(cycles[(VertexT)edgeNotInMST.EndPoint]);

       if (cycleToSplitSet.Count == 0) {
           // Find the path between the current edge not in ST enpoints using
           // the spanning tree itself
           List<EdgeT> path =
               FindPath(
                   (VertexT)edgeNotInMST.StartPoint,
                   (VertexT)edgeNotInMST.EndPoint,
                   spanningTree);

           // The found path plus the current edge becomes a cycle
           path.Add(edgeNotInMST);

           foreach (VertexT vertexInCycle in VerticesInPathSet(path))
               cycles[vertexInCycle].Add(path);
       } else {
            // Get the cycle to split from the set produced before
            List<EdgeT> cycleToSplit = cycleToSplitSet.GetEnumerator().Current;
            List<EdgeT> cycle1 = new List<EdgeT>();
            List<EdgeT> cycle2 = new List<EdgeT>();
            SplitCycle(cycleToSplit, edgeNotInMST, cycle1, cycle2);

            // Remove the cycle that has been splitted from the vertices in the
            // same cicle and add the results from the split operation to them 
            foreach (VertexT vertex in VerticesInPathSet(cycleToSplit)) {
                cycles[vertex].Remove(cycleToSplit);
                if (VerticesInPathSet(cycle1).Contains(vertex))
                     cycles[vertex].Add(cycle1);
                     if (VerticesInPathSet(cycle2).Contains(vertex))
                         cycles[vertex].Add(cycle2); ;
            }
       }
   }
   HashSet<List<EdgeT>> ret = new HashSet<List<EdgeT>>();
   // Create the set of cycles, in each vertex should be remained only one
   // incident cycle
       foreach (HashSet<List<EdgeT>> remainingCycle in cycles.Values)
           ret.AddAll(remainingCycle);

       return ret;
}

Код Огги был очень хорош и clear , но я почти уверен, что он содержит ошибку, или это я не понимаю ваш псевдокод Python :)

cycles[v] = []

не может быть индексированным по вершинам словарем списков ребер. На мой взгляд, это должен быть индексированный по вершинам словарь наборов списков ребер.

И, чтобы добавить уточнение:

for vertex on cycle_to_split:

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

Повторяю, это непроверенный и неполный код, но это шаг вперед. Он по-прежнему требует правильной структуры графа (я использую список инцидентов) и многих алгоритмов графов, которые вы можете найти в учебниках, таких как Кормен. Мне не удалось найти FindPath () и SplitCycle () в учебниках, и их очень сложно закодировать за линейное время количества ребер + вершин в графе. Сообщу о них здесь, когда я их протестирую.

Большое спасибо, Огги!