Как преобразовать итеративную функцию, которая проверяет циклы в матрице смежности, в более простую рекурсивную функцию в C?

Question

Мне трудно понять рекурсивное мышление, и многое из того, что я видел в переполнении стека, я не понимаю.

Я пытаюсь обнаружить цикл в ориентированном графе, учитывая матрицу смежности двумерных массивов, где значение true для графа [i] [j] указывает ребро от i до j.

Создана функция check_cycles, которая проверяет путь от j до i, заданный граф [i] [j] и жестко запрограммировала размер графа, чтобы упростить проблему.

Я получаю возвращаемое значение true, как и ожидалось с этим кодом, но, как вы можете видеть, теперь я жестко закодировал много циклов for, и это было бы нецелесообразно, если бы размер или значения передавались функция будет изменена.

Как мне найти рекурсивное решение для этого? В каком случае функция должна перестать работать?

Прямо сейчас я использую библиотеку, которая позволяет возвращать bool возвращаемое значение для функций, но она также может возвращать void.

#include <stdio.h>
#include <cs50.h>


//hard coding the size of the graph
int size = 5;

//set up an adjecency matrix
bool graph[5][5];

//functions
bool check_cycles(int index1, int index2);

int main(void)
{

  //setting the graph values to false
  for (int i = 0; i < size; i++)
  {
    for (int j = 0; j < size; j++)
    {
      graph[i][j] = false;
    }
  }

  //hard coding a cycle into the graph
  graph[0][1] = true;
  graph[1][2] = true;
  graph[2][3] = true;
  graph[3][0] = true;

//check for cycles
  printf(check_cycles(2,3)? "Cycle detected\n" : "No cycles\n");

}



bool check_cycles(int index1, int index2)
{  
  for (int i = 0; i < size; i++)
  { 
    //check for adjacent edge
    if (graph[index2][i] == true)
    {
      //check if edge points to initial node
      if (graph[i][index1] == true)
      {
        return true;
      }
      else 
      {
        for (int j = 0; j < size; j++)
        {
          if (graph[i][j] == true)
          {
            if (graph[j][index1] == true)
            {
              return true;
            }
            else  
            {
              for (int k = 0; k < size; k++)
              {
                if (graph[j][k] == true)
                {
                  if (graph[k][index1] == true)
                  {
                    return true;
                  }
                }
              }
            }
          }
        }
      }
    }
  }
return false;
}

Answer 1

Спасибо! Я понял это в конце концов - я усложнил проблему. Моя функция цикла, в сущности, ищет путь от узла a к b, учитывая, что ребро b к a уже установлено в true.

Затем я смог использовать рекурсию следующим образом, размер был глобальной переменной -

bool check_path(int index2, int index1)
{
    if (index1 == index2)
    {
        return true;
    }
    for (int i = 0; i < size; i++)
    {
            if (graph[index2][i] == true)
        {
            if (check_path(i, index1))
            {
                return true;
            }
        }
    }
    return false;
}

Answer 2

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

Обнаружение цикла может быть выполнено наивно поиск в глубину , начиная с каждого узла. Перед началом создайте пустой набор для отслеживания посещенных узлов. Когда вы посещаете узел, сначала посмотрите его в наборе. Если он уже там, вы нашли цикл; в противном случае отметьте посещение и выполните поиск всех соседних соседей. Если вы не нашли циклов для узла, отметьте его как непосещенный перед выходом из его кадра вызова, чтобы избежать ложных срабатываний, если к нему имеется несколько путей.

Вы можете сделать это итеративно, используя стек и все oop. вставьте стек, чтобы посетить узел, и поместите его sh его соседей в стек. Фундаментальный подход тот же, что вы используете поиск по посещенному набору для обнаружения циклов.

Если у вас есть базовая реализация c, вы можете от sh до оптимизировать .

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

bool is_cyclic_(int curr, int n, bool **graph, bool **visited) {
    if ((*visited)[curr]) {
        return true;
    }

    (*visited)[curr] = true;

    for (int i = 0; i < n; i++) {
        if (graph[curr][i] && is_cyclic_(i, n, graph, visited)) {
            return true;
        }
    }

    (*visited)[curr] = false;
    return false;
}

bool is_cyclic(int n, bool **graph) {
    bool *visited = calloc(n, sizeof(*visited));

    for (int i = 0; i < n; i++) {        
        if (is_cyclic_(i, n, graph, &visited)) {
            free(visited);
            return true;
        }
    }

    free(visited);
    return false;
}

int main() {
    int n = 5;
    bool graph[][5] = {
        {0,0,0,1,0},
        {0,0,0,0,0},
        {0,0,0,0,1},
        {0,0,1,0,0},
        {1,0,0,0,0},
    };
    bool **pgraph = malloc(sizeof(*pgraph) * n);

    for (int i = 0; i < n; i++) {
        pgraph[i] = malloc(sizeof(pgraph[i]) * n);

        for (int j = 0; j < n; j++) {
            pgraph[i][j] = graph[i][j];
        }
    }

    printf("%d\n", is_cyclic(n, pgraph));

    for (int i = 0; i < n; i++) {
        free(pgraph[i]);
    }

    free(pgraph);
    return 0;
}