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

[kappa937]

Здравствуйте.
Задача найти кол-во циклов в неориентированном графе с указанием их длин.
Есть ли у кого-то примеры решенной задачи либо несложный алгоритм? Заранее спасибо.

[Sibedir]

Качаем пример с интернета. А уж если чего не получилось - тогда сюда.

[kappa937]

Sibedir, примеров для неориентированных я не нашел

Вот моя попытка:

public void solution(int current_vertex) 
{
      for (int j = 0; j < edge_count; j++) 
      {
           if (new_graph[current_vertex, j] == 1)
           {
               new_graph[current_vertex, j] = -1;
               new_graph[j, current_vertex] = -1; 
               Console.WriteLine((current_vertex + 1) + "->" + (j + 1)); // просто вывод для наглядности
               if (j == start) amount++;
               solution(j);                    
           }
      }
}

new_graph изначально равен матрице смежности, в последствии после каждого прохода я вот этой строкой:
new_graph[current_vertex, j] = -1;
new_graph[j, current_vertex] = -1;
отмечаю что это ребро было пройдено
в start находится вершина, из которой мы на этом этапе ведем поиск
и если она равна вершине, в которую хотим прийти (j) то увеличиваем счетчик.
в мейн-функции в цикле вызываю solution() для каждой вершины, и делаю new_graph снова равным матрице смежности (убираю отметки о пройденных вершинах)

Проблема в том, что у меня, к примеру, 1-2-4-3-1, 1-3-4-2-1 это разные пути, но при этом условие (j == start) выполняется.
Соответственно если, к примеру, ребра такие:
1 2
1 3
2 4
4 3
То кол-во циклов будет 4 (равно кол-ву вершин), а должно быть по идее 1.
И второй вопрос в том, как проще всего считать их длины, но мне бы для начала с кол-вом циклов разобраться.

[Sibedir]

1. https://ru.wikipedia.org/wiki/Поиск_в_глубину
2. http://neerc.ifmo.ru/wiki/index.php?...88%D0%B8%D0%BD
3. Мне кажется помечать нужно не ребра, а вершины.

[kappa937]

Попытался написать с учетом теории.

public void DFS(int st)
{
      int r;
      color[st] = "GRAY";
      for (r = 0; r < vertex_count; r++)
      {
           if (graph[st, r] == 1)
           {
                if (color[r] == "WHITE") DFS(r);
                if (color[r] == "GRAY")
                {
                    amount++;
                    break; 
                }                      
           }
      }
      color[st] = "BLACK";
}

В мейне вызываю так:

for (int i = 0; i < vertex_count; i++)
     if (color[i] == "WHITE")  
           DFS(i);

Сам граф:


Находит в данном случае 8 циклов. Хотя их 3. Как я понял, в условии if(color[r]==GRAY) не учитывается, что это та вершина, из которой пришли (например 3-1 и 2-1 считает за циклы)

Подскажите, как исправить?

[kappa937]

может кто помочь?

[Poma][a]

Почему 3?
Их тут дофига
Граф неориентированный (у нас не дуги, а ребра.. и движемся в обе стороны)
Поэтому 1-2-1 уже цикл

[kappa937]

Poma][a, просто по заданию нужно учитывать только вот такие циклы:

[Sibedir]

М-дя. Я если честно в Си не очень, да и логика не очень ясна. Каждый вложеный вызов у тебя перекрашивает по своему и при выходе на уровень выше в ячейках уже не то, что нужно было в текущей итерации.
Или я вообще ни чё не понял...

// Добавлено ---------------------------------------------------
Блин. Интересно, но времени мало. Вчера перед сном посмотрел. Короче
Пост #5 - это как в вики, обход в глубину. Он не ищет кол-во циклов, а определяет их наличие впринципе. Здесь в amount оказывается что-то типа - кол-во ячеек входящих в цикл.
На делфе накида вот такое:

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  TColor = (WHITE, GRAY, BLACK);

const
  _COUNT = 16;
  _LOW   = 1;
  _HIGH  = _COUNT + _LOW - 1;

var
  Colors: array [_LOW.._HIGH] of TColor;
  Graph: array [_LOW.._HIGH, _LOW.._HIGH] of Boolean;
  Amount: Integer;

// Создаёт ребро
procedure SetEdge (aVertex1, aVertex2: Word);
begin
  if    (aVertex1 = aVertex2)
     or (aVertex1 > _HIGH) or (aVertex2 > _HIGH)
     or (aVertex1 < _LOW ) or (aVertex2 < _LOW )
     then Exit;

  Graph [aVertex1, aVertex2] := True;
  Graph [aVertex2, aVertex1] := True;
end;

// Обход
procedure DFS (cur, prev: Integer);
var
  i: Integer;
begin
  Colors[cur] := GRAY;
  for i := _LOW to _HIGH do
    if Graph[cur,i] then
      case Colors[i] of
        WHITE: DFS(i, cur);
        GRAY : if i <> prev then begin
                 Inc (Amount);
               end;
      end;
  Colors[cur] := BLACK;
end;

// -----------------------------------------------------------------------------
var
  i, j: Integer;
begin
  // Обнуляем
  for i := _LOW to _HIGH do begin
    for j := _LOW to _HIGH do Graph[i,j] := False;
    Colors[i] := WHITE;
  end;

  // Заполняем
  SetEdge ( 1,  2); //  1
  SetEdge ( 1,  3); //  2
  SetEdge ( 1,  4); //  3
  SetEdge ( 4,  5); //  4
  SetEdge ( 4,  6); //  5
  SetEdge ( 5,  7); //  6
  SetEdge ( 5,  9); //  7
  SetEdge ( 6,  7); //  8
  SetEdge ( 6, 15); //  9
  SetEdge ( 6, 16); // 10
  SetEdge ( 7, 11); // 11
  SetEdge ( 9, 10); // 12
  SetEdge (11, 13); // 13
  SetEdge (12, 13); // 14
  SetEdge (13, 14); // 15
  SetEdge (14, 15); // 16

//  SetEdge ( 2, 8);
//  SetEdge ( 8, 9);

  // MAIN
  Amount := 0;
  for i := _LOW to _HIGH do
    if Colors[i] = WHITE then DFS(i, _LOW-1);

  // Выводим
  Writeln (Amount);
  Readln;
end.

Но оно считает только циклы №1 и №2 (пост #8). Только колличествово непересекающихся циклов.

Доделать не успел. Но вроде нужно так: Пройтись по всем не "Исследованным" ячейкам и найти для них все пути обратно (из ячейки U в U если путь длиннее чем 2) помечая их после как "Исследованные".

[Poma][a]

Могу предложить только такой вариант : сделать еще одним параметром bfs'a массив, который будет хранить наименьший путь до вершин. Если мы на некотором этапе получаем, что мы уже были в вершине K. То смотрим в наш массив, и если там число 6 или 8, или 4, то увеличиваем счетчик.

Но такое счастье нужно сделать для всех вершин..
Сложность O(N^3)