Найти максимальный цикл в ориентированном невзвешенном графе

Question

Граф задается матрицей смежности. Заранее количество вершин графа не известно. Граф ориентированный, невзвешенный, без петель. Нужно найти максимальный цикл. Написать надобно на C#.

В теории вроде бы все понятно. Кодом смогла проверить ввод матрицы смежности. Понимаю, что необходимо найти ячейку с значением "1" и далее переключать цикл на строку матрицы с тем же индексом строки, что был в столбце до этого. Но как это записать кодом? Видимо, нужна рекурсия. Как ее записать? Или может, есть какие-то более простые пути?

Ниже мой стыдный кусочек кода...

    for (int i = 0; i < dataGridView1.RowCount; i++)
        {
            for (int j = 0; j < dataGridView1.RowCount; j++)
            {
                if (Convert.ToInt32(dataGridView1.Rows[i].Cells[j].Value) == 1 )
                {
                    int a = i;
                    int b = j;
                    for (int k = j; k < dataGridView1.RowCount; k++)
                    {
                        for (int f = 0; f < dataGridView1.RowCount; f++)
                        {
                            if (Convert.ToInt32(dataGridView1.Rows[k].Cells[f].Value) == 1)
                                // и так до момента, пока a и b не совпадут с текущими значениями в скобках...
                        }
                    }
                }
                else
                {
                    continue;
                }

               ;
            }
        }

Буду очень благодарна любой помощи!

Матрица,например,такая:

        А    Б    В    Г    Д

  А     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

Answer 1

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

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

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

А-Б-В-Д-Г-А

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

БЛОГ НА HUSL

Найти максимальный цикл в ориентированном невзвешенном графе

Ответы (1 шт):