使用DFS查找迷宫中的所有路径

给定迷宫中的源和目标单元格，我想使用DFS找到迷宫的所有可能解决方案。 0表示我迷宫中的墙。

可视化迷宫

我已经成功编写了一个程序，但这只给了我一条路。 我已经想到了将它扩展到所有路径的所有可能性，但遗憾的是，即使经过数小时（确切地说是2天），我也无法找到解决方案。

我想为每个节点保留一个“访问过的”数组，这样当我回溯时，我不会对前一个节点执行相同的移动。 但是，这样做只会产生一个完全不同的路径（如果有的话），没有相同的节点。

我还想到了一些其他的方式，但即使这也提出了一些问题。

我也检查了类似的问题，但没有一个是针对我的背景。 有一个使用显式递归的解决方案。 但是，我想要的是使用堆栈并找到所有可能的路径。 可悲的是，我找不到任何可信的东西（至少以我能理解的方式）。

这是我的一条路径的代码。

编辑 ：我现在已经实现了“正确的”DFS。 我还添加了一个堆栈来跟踪当前路径。 然后程序还会检查未探测的节点。 但是，它检查其他一些顺序，因此我仍然只能获得一条路径！

#include  #include  #include  typedef struct Point { int x,y; }Point; typedef struct stack { struct Point pt; struct stack* next; void push(int, int); Point pop(); }stack, stack_path; stack*front =NULL; stack_path*front_path =NULL; void push(int x, int y) { if(front==NULL) { front = (stack*)malloc(sizeof(stack)); front -> pt.x = x; front -> pt.y = y; front -> next = NULL; return; } stack* temp = (stack*)malloc(sizeof(stack)); temp -> pt.x = x; temp -> pt.y = y; temp -> next = front; front = temp; } Point pop() { if(front != NULL) { stack* temp = front; Point pt = front -> pt; front = front -> next; free(temp); return pt; } } void push_path(int x, int y) { if(front_path==NULL) { front_path = (stack*)malloc(sizeof(stack_path)); front_path -> pt.x = x; front_path -> pt.y = y; front_path -> next = NULL; return; } stack_path* temp = (stack*)malloc(sizeof(stack_path)); temp -> pt.x = x; temp -> pt.y = y; temp -> next = front_path; front_path = temp; } Point pop_path() { if(front_path != NULL) { stack_path* temp = front_path; Point pt = front_path -> pt; front_path = front_path -> next; free(temp); return pt; } } bool inMaze(Point pt) { return (pt.x>=0 && pt.y>=0 && pt.x<5 && pt.ypt.x, temp->pt.y); temp = temp->next; } printf("\n"); pop_path(); } else { if(!visited[6*pt.x+pt.y]) { visited[6*pt.x+pt.y] = 1; push_path(pt.x,pt.y); } int i; int flag =0; for(i=0; i<4; i++) { pt1.x = dx[i] + pt.x; pt1.y = dy[i] + pt.y; if(inMaze(pt1) && maze[pt1.x][pt1.y]==1 && visited[6*pt1.x+ pt1.y]==0) { push(pt1.x,pt1.y); flag = 1; } } if(flag==0) pop_path(); } } return 0; } 

有人可以指导我修改此代码，以便找到所有路径 。 期待社区的帮助！

PS：SO目前不允许我嵌入图像，因此它自动创建了一个链接。

PS：这个问题已被标记为与其他一些问题有关的重复。 为了您的信息，我在发布问题之前已经完成了这个问题！ 如果有人会在那里看到答案，你会发现它没有被“接受” ！ 它只是说你需要做“所有”排列！ 如果只有一个人会打扰通过另一个答案（在另一个问题中），他们会意识到它只适用于向北，东北或东方方向移动！ 此外，我也明确表示我不想要一个递归解决方案 – 这就是另一个问题所使用的！

编辑2：工作解决方案

 #include  #include  #include  typedef struct Point { int x,y; }Point; typedef struct stack { struct Point pt; struct stack* next; int dir_count; }stack; stack*front =NULL; void push(int x, int y) { stack* temp = (stack*)malloc(sizeof(stack)); temp -> pt.x = x; temp -> pt.y = y; temp -> next = front; front = temp; } Point pop() { if(front != NULL) { stack* temp = front; Point pt = front -> pt; front = front -> next; free(temp); return pt; } } bool inMaze(Point pt) { return (pt.x>=0 && pt.y>=0 && pt.x<5 && pt.ydir_count = 0; struct Point dest = {3,4}; int maze[5][6] = {{1,0,1,1,1,1},{1,0,1,0,1,1},{1,1,1,0,1,1},{0,0,0,0,1,0},{1,1,1,0,1,1}}; int dx[4]={-1, 0, 0, 1}; int dy[4]={0,-1, 1, 0}; int flag_pop = 0; while(front != NULL) { if(front->pt.x==dest.x && front->pt.y==dest.y) { stack* temp = front; while(temp != NULL) { printf("%d%d ", temp->pt.x, temp->pt.y); temp = temp->next; } printf("\n"); pt = pop(); } else { int i,k; int flag_push =0, count = 0, moves=0; for(k=0;kpt.x; pt2.y = dy[k] + front->pt.y; if(maze[pt2.x][pt2.y]==0 || !inMaze(pt2) || !(pt.x != pt2.x || pt.y != pt2.y)) count++; } // count of possible moves for each node moves = 4-count; for(i=0; ipt.x; pt1.y = dy[i] + front->pt.y; // if moves are exhausted if(!(front->dir_countpt.x == pt1.x && temp->pt.y == pt1.y) { flag = 1; break; } temp = temp->next; } // if node is not there in the path if(flag==0) { front->dir_count++; push(pt1.x, pt1.y); front -> dir_count = 0; flag_push = 1; break; } } } // if no move was done if(flag_push==0) { pt = pop(); } } } return 0; } 

Answer 1

我认为您需要清除访问中的相应字段，从堆栈中删除该点。

编辑 ：另一个问题是，当你达到目标时需要回溯。 在您的堆栈上，可能并不明显未开发的替代方案是什么以及当前路径是什么（您可能能够使用被访问的数组来跟踪它，但它似乎比使用递归或添加相应信息的“仅仅”更复杂。你的Stack stuct）

此外，后续节点应在实际调查时标记为已访问，而不是在它们被推入堆栈时。

一些评论

• 我认为代码使用递归而不是显式堆栈更具可读性

• 你真的不需要访问，你可以暂时将路径上的迷宫字段更改为1（可能不会在迷宫应该是不可变的“真实”代码中执行此操作）。 否则，我只是像迷宫一样构造它。

• 我会改变推动以获得对称性。

• 避免冗余膨胀代码。 例如， push的front == NULL分支在默认情况下是多余的 – 默认情况下在NULL情况下将完全相同。

编辑2 ：

如果你真的想避免递归，我会将数据结构更改为：

 typedef struct PathElement { int x; int y; int direction_to_next; struct PathElement* next; struct PathElement* prev; } path; 

这将允许您轻松地向任何方向前进（例如，当您想要打印时，您将位于路径的末尾）。 当您回溯到PathElement时，递增direction_to_next并继续，直到您已经用完所有4个可能的方向。 不要提前“推”替代品。

Answer 2

• 对于搜索中的每个点，请保留对前一点的引用。 操作后，始终将物品从堆叠中弹出。 请注意，如果没有解决方案，您的代码将无限循环 。 当你走到最后，你可以使用前辈来回溯并找到完整的路径。

• 摆脱访问过的数组，并防止在DFS期间循环，检查以确保添加到路径的点当前不在路径中。 由于迷宫中只有30个可能的点，您可以使用位域来表示给定点是否在路径中。

• 此外，不要过早地突破循环（在找到第一个可用的移动时）。