c - 实现 BFS 返回从顶点 s 到 t 的最小长度路径

Question

我正在尝试实现广度优先搜索，其中有四个函数:int move1(int)、int move2(int)、int move3(int)、int move4(int) 均从给定顶点生成一个新顶点，如果该移动不可能，则返回 -1。我必须编写函数:

struct listnode * bfspath(int s, int t)

其中struct listnode { int v, struct listnode *next };

该函数应返回从顶点 s 开始到顶点 t 结束的顶点列表，并且是从 s 到 t 的最小长度路径。如果不存在路径，则返回 NULL。

为了存储所有当前到达的顶点，我使用高度平衡树。队列应该是一个链表。在搜索树中，我需要存储每个已知状态以及到达它的状态。存储该移动不是必需的，因为它可以通过尝试三种可能的移动来重建。有了这些信息，就可以按照相反的顺序重建从起始状态到目标状态的路径。

我知道我不应该在没有尝试/错误的情况下寻求帮助，但我真的很难过。我不知道如何处理这个问题以及如何开始。如果有人能给我一个先机或给我解释该怎么做，我将不胜感激。我知道这不是一个值得深入研究的智力问题，也不值得在 stackoverflow 上询问，但我真的很感激任何帮助。

四个移动函数如下:

int move1(int i)
{  int x, y, z, newx, newy, newz;
   z = i/100000;
   x = i %1000;
   y = (i/1000)%100;
   {  newx = (x+1)%1000; newy = y; newz = z;}
   return(newz*100000 +newy*1000 + newx );
}

int move2(int i)
{  int x, y, z, newx, newy, newz;
   z = i/100000;
   x = i %1000;
   y = (i/1000)%100;
   {  newx = (x+999)%1000; newy = y; newz = z;}
   return(newz*100000 +newy*1000 + newx );
}

int move3(int i)
{  int x, y, z, newx, newy, newz;
   z = i/100000;
   x = i %1000;
   y = (i/1000)%100;
   if( (x!=0) || (y!=0))
   {  newx = x; newy = (y+1)%100; newz = z;}
   else /* (x==0) && (y==0))*/
   {newx = x; newy = y; newz = (z + 1)%4;} 
   return(newz*100000 +newy*1000 + newx );
}

int move4(int i)
{  int x, y, z, newx, newy, newz;
   z = i/100000;
   x = i %1000;
   y = (i/1000)%100;
   if( (x!=0) || (y!=0))
   {  newx = x; newy = (y+99)%100; newz = z;}
   else /* ((x==0) && (y=0)) */
   {newx = x; newy = y; newz = (z+3)%4;} 
   return(newz*100000 +newy*1000 + newx );
}

测试代码:

int main()
{  int i, j, k;
    struct listnode * path;
   for( k=0; k<10; k++ )  
   {  i = rand()%400000; j = rand()%400000;
      printf("Test %d: from %d to %d:", k, i, j);
      path = bfspath(i,j);
      if(path == NULL)
      { printf("Failed: no path found.\n"); fflush(stdout); exit(0);}
      if( path->v != i)
      {  printf("Failed.\n wrong startvertex. Should go from %d to %d; starts at %d\n",
        i,j, path->v); fflush(stdout); exit(0);
      }
      else
      {  while( path->v != j && path->next != NULL)
    {  if( path->next->v == move1(path->v)
              || path->next->v == move2(path->v)
              || path->next->v == move3(path->v)
           || path->next->v == move4(path->v) )
          path = path-> next;
       else
       {  printf("Failed.\n wrong next vertex on path: %d is not neighbor of %d\n",
            path->next->v, path->v );
          fflush(stdout); exit(0);
           } 
        }
        if( path->v != j )         
    {  printf("Failed.\n wrong final vertex; should be %d, is %d\n", j, path->v);
       fflush(stdout); exit(0);
        }
      }
      printf("Passed.\n");
   }
   printf("Tested 10 random paths\n");
   return(0);
}

Answer 1

我建议有一个辅助结构，也许一个数组可以做到这一点，这样你就可以存储每个节点的“父节点”。将 BFS 遍历视为生成有根生成树的一种方法。就 BFS 而言，每次将顶点 v 的未访问邻居 u 添加到队列中时，就表明 v 是 u 的父级，也就是说，您需要找到 v 才能找到 u。然后，一旦找到目标顶点，就可以在这棵树上“回溯”来构建路径。我的意思是，您可以查看目标顶点的“父级”，然后获取父级的父级，直到到达根，即源顶点。

如果您的边有权重，那么您也可以修改 Dijkstra 的边以执行相同的操作。

在找到目的地之前先找到路径是非常麻烦的，因为你必须跟踪很多可能的路径，因为你事先不知道命运会从哪条路径出现。使用父引用是一种隐式方式来存储从源到所有顶点的所有最短路径，而不会增加 BFS 的复杂性。您不必构建所有路径，但这样您就可以检索从源顶点开始的任何所需路径。

你也可以构建整个BFS树，然后找到从命运到根的路径，在某种意义上它是相同的，但也许更直观的方式。