Tag: 深度优先搜索

使用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) { […]

图C实现 – 深度优先搜索

我正在尝试使用图的邻接列表表示来实现深度优先搜索算法。 这是我的代码： #include #include struct edge { int vertexIndex; struct edge *edgePtr; }edge; struct vertex { int vertexKey; int visited; struct edge *edgePtr; }vertex; void insertVertex(struct vertex *g, int vertexKey, int *vertexCount) { g[*vertexCount].vertexKey=vertexKey; g[*vertexCount].edgePtr=NULL; g[*vertexCount].visited=0; (*vertexCount)++; } void insertEdge(struct vertex *g,int vertex1, int vertex2) { struct edge *e,*e1,*e2; e=g[vertex1].edgePtr; while(e&& e->edgePtr) { e=e->edgePtr; } […]