如何在迷宫中打印从源到目标的BFS路径

我正在尝试实现BFS，以便找到迷宫中从源到目标的最短路径。

我遇到的问题是我无法打印路径，它在迷宫中打印了’*’，但是如何在不打印所有被访问节点的情况下从BFS的前辈中提取路径？

这是我编译的代码：

#include  #include  #include  struct coord{ //This is a struct I'll use to store coordinates int row; int col; }; //---------QUEUE.C-------// struct TQueue{ struct coord *A; int QUEUE_MAX; }; typedef struct TQueue *Queue; Queue initQueue(int size){ // Initialize the queue Queue Q = malloc(sizeof(struct TQueue)); Q->A = malloc(size*sizeof(struct coord)); Q->QUEUE_MAX = size+1; Q->A[0].row = 0; //I'll use only the row value for first and last element Q->A[Q->QUEUE_MAX].row = 1; return Q; } int emptyQueue(Queue Q){ return Q->A[0].row == 0; } int fullQueue(Queue Q){ return Q->A[0].row == Q->A[Q->QUEUE_MAX].row; } void enqueue(Queue Q, struct coord value){ if(!fullQueue(Q)){ Q->A[Q->A[Q->QUEUE_MAX].row] = value; // Insert in tail if(emptyQueue(Q)){ Q->A[0].row = 1; // If is empty, the head will be in the first position } Q->A[Q->QUEUE_MAX].row = (Q->A[Q->QUEUE_MAX].row%(Q->QUEUE_MAX - 1)) + 1; } else{ puts("Coda piena"); } } struct coord dequeue(Queue Q){ struct coord value; if(!emptyQueue(Q)){ value = Q->A[Q->A[0].row]; // I take the "head" value Q->A[0].row = (Q->A[0].row%(Q->QUEUE_MAX - 1)) + 1; if(fullQueue(Q)){ Q->A[0].row = 0; Q->A[Q->QUEUE_MAX].row = 1; } } else{ puts("Coda piena"); } return value; } //------------GRAPH.C-------- struct TGraph{ char **nodes; int rows; int cols; struct coord S; struct coord T; }; typedef struct TGraph *Graph; enum color{ WHITE, GREY, BLACK // I will use these for undiscovered, unvisited and visited nodes }; int BFSPathMatrix(Graph G, struct coord *pred){ int i, j; struct coord neighbor, source = G->S; //I use "source" in order to move in the maze and neighbor for visiting the adiacents enum color visited[G->rows][G->cols]; for(i = 0; i rows; i++) for(j = 0; j cols; j++) visited[i][j] = WHITE; //Undiscovered Queue coda = initQueue(G->rows*G->cols); visited[G->S.row][G->S.col] = GREY; //Discovered enqueue(coda, source); i = 0; while(!emptyQueue(coda)){ source = dequeue(coda); int moves[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; //I can move right, left, down and up for(j = 0; j < 4; j++){ neighbor.row = source.row + moves[j][0]; neighbor.col = source.col + moves[j][1]; if(neighbor.row = G->rows || neighbor.col = G->cols) continue; if(neighbor.row == G->T.row && neighbor.col == G->T.col){ pred[i++] = G->T; //G->nodes[source.row][source.col] = '*'; free(coda); return 1; } if(visited[neighbor.row][neighbor.col] == WHITE && G->nodes[neighbor.row][neighbor.col] == ' '){ //If it's undiscovered, we put it in the queue pred[i++] = source; //G->nodes[source.row][source.col] = '*'; visited[neighbor.row][neighbor.col] = GREY; enqueue(coda, neighbor); } } } free(coda); return -1; } Graph initGraphMatrix(int rows, int cols){ int i; Graph G = malloc(sizeof(struct TGraph)); G->nodes = malloc(rows*sizeof(char *)); for(i = 0; i nodes[i] = malloc(cols*sizeof(char)); G->rows = rows; G->cols = cols; return G; } void printGraphMatrix(Graph G){ if(G != NULL){ int i, j; for(i = 0; i rows; i++){ for(j = 0; j cols; j++) putchar(G->nodes[i][j]); putchar('\n'); } } } int main(){ Graph G = initGraphMatrix(11, 21); G->S.row = 1; G->S.col = 1; G->T.row = 9; G->T.col = 7; strcpy(G->nodes[0], "|-------------------|"); strcpy(G->nodes[1], "|S | | |"); strcpy(G->nodes[2], "| |-| |-| |---| | | |"); strcpy(G->nodes[3], "| | | | | | |"); strcpy(G->nodes[4], "| | |---| | |---| | |"); strcpy(G->nodes[5], "| | | | | | | | |"); strcpy(G->nodes[6], "| | | | |-| | | | | |"); strcpy(G->nodes[7], "| | | | | | | |"); strcpy(G->nodes[8], "| | | |-| |-------| |"); strcpy(G->nodes[9], "| | T| |"); strcpy(G->nodes[10], "|-------------------|"); struct coord pred[(G->rows*G->cols)]; printGraphMatrix(G); system("PAUSE"); if(BFSPathMatrix(G, pred) != -1){ int i; for(i = 0; i rows*G->cols; i++){ if(pred[i].row == G->S.row && pred[i].col == G->S.col) continue; if(pred[i].row == G->T.row && pred[i].col == G->T.col) break; G->nodes[pred[i].row][pred[i].col] = '*'; } printGraphMatrix(G); }else puts("Target unreachable"); system("PAUSE"); return 0; } 

这就是BFS之前和之后迷宫的样子：

如何只打印最短路径？ 为什么’T’之前的空格中没有’*’？ 提前感谢您的所有时间。

Answer 1

UPD。

我纠正了我的代码和你的代码。 您需要pred array不作为数组，而是作为[G->rows][G->col]矩阵大小。 这个矩阵的每个细胞都显示出你来自哪个细胞！ 我认为你错误地理解了这个想法，你以线性方式填充pred数组，这是毫无意义的。 但是我不想更改你的接口，所以我使用pred作为线性数组，但实际上它是矩阵。

BFSPathMatrix函数中的更正：

  if(neighbor.row == G->T.row && neighbor.col == G->T.col){ pred[neighbor.row*G->cols + neighbor.col] = source; free(coda); return 1; } if(visited[neighbor.row][neighbor.col] == WHITE && G->nodes[neighbor.row][neighbor.col] == ' '){ //If it's undiscovered, we put it in the queue pred[neighbor.row*G->cols + neighbor.col] = source; visited[neighbor.row][neighbor.col] = GREY; enqueue(coda, neighbor); } 

主要function的更正：

 if(BFSPathMatrix(G, pred) != -1){ struct coord T = G->T; int predInd = T.row*G->cols + T.col; while (pred[predInd].row != G->S.row || pred[predInd].col != G->S.col) { predInd = T.row*G->cols + T.col; T = pred[predInd]; if( G->nodes[T.row][T.col] == ' ') G->nodes[T.row][T.col] = '*'; } printGraphMatrix(G); }else puts("Target unreachable"); 

结果：

 |-------------------| |S | | | | |-| |-| |---| | | | | | | | | | | | | |---| | |---| | | | | | | | | | | | | | | | |-| | | | | | | | | | | | | | | | | |-| |-------| | | | T| | |-------------------| Press any key to continue . . . |-------------------| |S**** |*******|***| | |-|*|-|*|---|*|*|*| | | |*****|*****|*|*| | | |---| |*|---|*|*| | | |***| |***| |*|*| | | |*|*|-| |*| |*|*| | | |*|***| |*****|*| | | |*|-|*|-------|*| | |**T|***********| |-------------------| 

主要思想是你应该使用你的pred数组从tar目标单元格到源单元格，并用’*’标记填充此路径上的单元格