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

The following is a demo implementation in C# (and Java, see end of answer) based on depth first search.

An outer loop scans all nodes of the graph and starts a search from every node. Node neighbours (according to the list of edges) are added to the cycle path. Recursion ends if no more non-visited neighbours can be added. A new cycle is found if the path is longer than two nodes and the next neighbour is the start of the path. To avoid duplicate cycles, the cycles are normalized by rotating the smallest node to the start. Cycles in inverted ordering are also taken into account.

This is just a naive implementation.
The classical paper is: Donald B. Johnson. Finding all the elementary circuits of a directed graph. SIAM J. Comput., 4(1):77–84, 1975.

A recent survey of modern algorithms can be found here

using System;
using System.Collections.Generic;

namespace akCyclesInUndirectedGraphs
{
    class Program
    {
        //  Graph modelled as list of edges
        static int[,] graph =
            {
                {1, 2}, {1, 3}, {1, 4}, {2, 3},
                {3, 4}, {2, 6}, {4, 6}, {7, 8},
                {8, 9}, {9, 7}
            };

        static List<int[]> cycles = new List<int[]>();

        static void Main(string[] args)
        {
            for (int i = 0; i < graph.GetLength(0); i++)
                for (int j = 0; j < graph.GetLength(1); j++)
                {
                    findNewCycles(new int[] {graph[i, j]});
                }

            foreach (int[] cy in cycles)
            {
                string s = "" + cy[0];

                for (int i = 1; i < cy.Length; i++)
                    s += "," + cy[i];

                Console.WriteLine(s);
            }
        }

        static void findNewCycles(int[] path)
        {
                int n = path[0];
                int x;
                int[] sub = new int[path.Length + 1];

                for (int i = 0; i < graph.GetLength(0); i++)
                    for (int y = 0; y <= 1; y++)
                        if (graph[i, y] == n)
                        //  edge referes to our current node
                        {
                            x = graph[i, (y + 1) % 2];
                            if (!visited(x, path))
                            //  neighbor node not on path yet
                            {
                                sub[0] = x;
                                Array.Copy(path, 0, sub, 1, path.Length);
                                //  explore extended path
                                findNewCycles(sub);
                            }
                            else if ((path.Length > 2) && (x == path[path.Length - 1]))
                            //  cycle found
                            {
                                int[] p = normalize(path);
                                int[] inv = invert(p);
                                if (isNew(p) && isNew(inv))
                                    cycles.Add(p);
                            }
                        }
        }

        static bool equals(int[] a, int[] b)
        {
            bool ret = (a[0] == b[0]) && (a.Length == b.Length);

            for (int i = 1; ret && (i < a.Length); i++)
                if (a[i] != b[i])
                {
                    ret = false;
                }

            return ret;
        }

        static int[] invert(int[] path)
        {
            int[] p = new int[path.Length];

            for (int i = 0; i < path.Length; i++)
                p[i] = path[path.Length - 1 - i];

            return normalize(p);
        }

        //  rotate cycle path such that it begins with the smallest node
        static int[] normalize(int[] path)
        {
            int[] p = new int[path.Length];
            int x = smallest(path);
            int n;

            Array.Copy(path, 0, p, 0, path.Length);

            while (p[0] != x)
            {
                n = p[0];
                Array.Copy(p, 1, p, 0, p.Length - 1);
                p[p.Length - 1] = n;
            }

            return p;
        }

        static bool isNew(int[] path)
        {
            bool ret = true;

            foreach(int[] p in cycles)
                if (equals(p, path))
                {
                    ret = false;
                    break;
                }

            return ret;
        }

        static int smallest(int[] path)
        {
            int min = path[0];

            foreach (int p in path)
                if (p < min)
                    min = p;

            return min;
        }

        static bool visited(int n, int[] path)
        {
            bool ret = false;

            foreach (int p in path)
                if (p == n)
                {
                    ret = true;
                    break;
                }

            return ret;
        }
    }
}

The cycles for the demo graph:

1,3,2
1,4,3,2
1,4,6,2
1,3,4,6,2
1,4,6,2,3
1,4,3
2,6,4,3
7,9,8

The algorithm coded in Java:

import java.util.ArrayList;
import java.util.List;

public class GraphCycleFinder {

    //  Graph modeled as list of edges
    static int[][] graph =
        {
            {1, 2}, {1, 3}, {1, 4}, {2, 3},
            {3, 4}, {2, 6}, {4, 6}, {7, 8},
            {8, 9}, {9, 7}
        };

    static List<int[]> cycles = new ArrayList<int[]>();

    /**
     * @param args
     */
    public static void main(String[] args) {

        for (int i = 0; i < graph.length; i++)
            for (int j = 0; j < graph[i].length; j++)
            {
                findNewCycles(new int[] {graph[i][j]});
            }

        for (int[] cy : cycles)
        {
            String s = "" + cy[0];

            for (int i = 1; i < cy.length; i++)
            {
                s += "," + cy[i];
            }

            o(s);
        }

    }

    static void findNewCycles(int[] path)
    {
            int n = path[0];
            int x;
            int[] sub = new int[path.length + 1];

            for (int i = 0; i < graph.length; i++)
                for (int y = 0; y <= 1; y++)
                    if (graph[i][y] == n)
                    //  edge refers to our current node
                    {
                        x = graph[i][(y + 1) % 2];
                        if (!visited(x, path))
                        //  neighbor node not on path yet
                        {
                            sub[0] = x;
                            System.arraycopy(path, 0, sub, 1, path.length);
                            //  explore extended path
                            findNewCycles(sub);
                        }
                        else if ((path.length > 2) && (x == path[path.length - 1]))
                        //  cycle found
                        {
                            int[] p = normalize(path);
                            int[] inv = invert(p);
                            if (isNew(p) && isNew(inv))
                            {
                                cycles.add(p);
                            }
                        }
                    }
    }

    //  check of both arrays have same lengths and contents
    static Boolean equals(int[] a, int[] b)
    {
        Boolean ret = (a[0] == b[0]) && (a.length == b.length);

        for (int i = 1; ret && (i < a.length); i++)
        {
            if (a[i] != b[i])
            {
                ret = false;
            }
        }

        return ret;
    }

    //  create a path array with reversed order
    static int[] invert(int[] path)
    {
        int[] p = new int[path.length];

        for (int i = 0; i < path.length; i++)
        {
            p[i] = path[path.length - 1 - i];
        }

        return normalize(p);
    }

    //  rotate cycle path such that it begins with the smallest node
    static int[] normalize(int[] path)
    {
        int[] p = new int[path.length];
        int x = smallest(path);
        int n;

        System.arraycopy(path, 0, p, 0, path.length);

        while (p[0] != x)
        {
            n = p[0];
            System.arraycopy(p, 1, p, 0, p.length - 1);
            p[p.length - 1] = n;
        }

        return p;
    }

    //  compare path against known cycles
    //  return true, iff path is not a known cycle
    static Boolean isNew(int[] path)
    {
        Boolean ret = true;

        for(int[] p : cycles)
        {
            if (equals(p, path))
            {
                ret = false;
                break;
            }
        }

        return ret;
    }

    static void o(String s)
    {
        System.out.println(s);
    }

    //  return the int of the array which is the smallest
    static int smallest(int[] path)
    {
        int min = path[0];

        for (int p : path)
        {
            if (p < min)
            {
                min = p;
            }
        }

        return min;
    }

    //  check if vertex n is contained in path
    static Boolean visited(int n, int[] path)
    {
        Boolean ret = false;

        for (int p : path)
        {
            if (p == n)
            {
                ret = true;
                break;
            }
        }

        return ret;
    }

}

Обходите граф в глубину. Стеком вершин назовем маршрут от начальной вершины до текущей вершины, по которому мы до неё добрались. Заведите множество вершин V, которые вы уже посетили. Для каждой вершины помните, из какой вершины вы в неё пришли (словарь P) при обходе. Если при обходе вы видите в числе соседей вершины уже посещённую вершину K, которая не входит в текущий стек вершин, то “разматывайте” путь от K до изначальной вершины, используя информацию из словаря P, это в совокупности со стеком вершин даст цикл. А если K входит в стек вершин, то циклом будет часть стека от K до вершины стека.

Дополнение не совсем в тему. Есть элегантный алгоритм, который для числа n определяет, входит ли вершина в цикл с повторами длины n. Но так как цикл с повторами, а граф неориентированный, то циклы вида A-B-A-B-A-… тожу будут учитываться. Видимо, можно придумать способ вычесть их количество из полученного числа циклов. Так я и собирался делать, но потом понял, что ничего этого не нужно и задача решается простым обходом в глубину.

UPD. Оказалось, что мой ответ неправильный. Правильные мысли описаны в научной статье.