1

难以掌握递归思维，到目前为止我在 Stack Overflow 上看到的很多内容我都不明白。

我试图在有向图中检测一个循环，给定一个二维数组邻接矩阵，其中 graph[i][j] 的值为 true 表示从 i 到 j 的边。

已经创建了一个 check_cycles 函数，它检查从 j 到 i 的路径，给定 graph[i][j] 并硬编码了图的大小以简化问题。

使用此代码，我得到了预期的 true 返回值，但是正如您所看到的，现在我已经硬编码了很多 for 循环，如果更改传递给函数的大小或值，这将是不切实际的。

我将如何找到一个递归解决方案？函数应该停止运行的情况是什么？

现在我正在使用一个允许函数返回布尔值的库，但它也可以返回 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;
}
4

2 回答 2

0

这种硬编码的想法似乎是一个不错的开始方式，但正如您所注意到的，解决此类问题需要一种根本不同的策略。

循环检测可以天真地从每个节点开始运行深度优先搜索。在开始之前，创建一个空集来跟踪访问过的节点。当你访问一个节点时，首先在集合中查找它。如果它已经存在，那么你已经找到了一个循环；否则，将其标记为已访问并搜索其所有相邻邻居。如果您没有找到节点的任何循环，请在退出其调用框架之前将其标记为未访问，以避免在有多个路径时出现误报。

您可以使用堆栈和循环迭代地执行此操作。弹出堆栈以访问一个节点并将其邻居推入堆栈。基本方法是相同的，因为您使用已访问集上的查找来检测周期。

一旦你有了基本的实现，你可能希望优化.

#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;
}
于 2020-04-21T03:58:59.970 回答
0

谢谢！我最终明白了这一点——我把问题复杂化了。我的循环函数实际上是在搜索从节点 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;
}
于 2020-04-22T05:22:36.250 回答