c - 如何将检查邻接矩阵中循环的迭代函数转换为 C 中更简单的递归函数?
问题描述
难以掌握递归思维,到目前为止我在 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;
}
解决方案
这种硬编码的想法似乎是一个不错的开始方式,但正如您所注意到的,解决此类问题需要一种根本不同的策略。
循环检测可以天真地从每个节点开始运行深度优先搜索。在开始之前,创建一个空集来跟踪访问过的节点。当你访问一个节点时,首先在集合中查找它。如果它已经存在,那么你已经找到了一个循环;否则,将其标记为已访问并搜索其所有相邻邻居。如果您没有找到节点的任何循环,请在退出其调用框架之前将其标记为未访问,以避免在有多个路径时出现误报。
您可以使用堆栈和循环迭代地执行此操作。弹出堆栈以访问一个节点并将其邻居推入堆栈。基本方法是相同的,因为您使用已访问集上的查找来检测周期。
一旦你有了基本的实现,你可能希望优化.
#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;
}
推荐阅读
- react-native - 如何从 createBottomTabNavigator 隐藏特定选项卡
- java - 将角 4 与支柱 2 集成
- flutter - 颤振打开列表查看特殊页面上的项目
- reactjs - 是什么导致 React 子组件重新渲染?
- amazon-web-services - 用于移动推送通知的 AWS SNS
- eclipse - 尽管命令行运行成功,但在 Eclipse 中启动 Tomcat Server 9 时出错
- xamarin - Xamarin:桥接 C# 与原生 Android 库
- c++ - 如何使用设置和获取扩展属性
? - jquery - 响应式菜单项 css 不堆叠在一起
- vba - 在变量中分组值?