广度优先遍历算法求无权图的单源最短路径思路辨析
原代码是这样程序代码:
/*-----------------广度优先搜索求单源最短路径-------------------*/ int d[Maxsize]; //d数组记录从起始顶点v到各个顶点最短路径 int path[Maxsize]; //path数组记录最短路径从哪个顶点过来 int visited[Maxsize]; //访问标记数组 void BFS_MIN_Distance(Graph G,int v) { for(int i=0;i<G.vexnum;i++) { d[i]=∞; //初始化路径长度 path[i]=-1; //初始化路径 } d[v]=0; //起始顶点路径长度为0 visited[v]=1; //标记起始顶点已访问 EnQueue(Q,v); //起始顶点入队 while(!isEmpty(Q)) { DelQueue(Q,v); //队头元素出队 for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) if(!visited[w]) { d[w]=d[v]+1; //路径长度+1 path[w]=v; //最短路径从顶点v到顶点w visited[w]=1; //标记已访问 EnQueue(Q,w); //将顶点w入队 } } } /*-----------------------------------------------*/
我感觉不太对,于是改了一下,有没有大佬看一下思路是否对
程序代码:
/*-----------------广度优先搜索求单源最短路径-------------------*/ int d[Maxsize]; //d数组记录从起始顶点v到各个顶点最短路径长度 int path[Maxsize]; //path数组是一个并查集,采用森林的双亲表示法。数组中的值表示该结点的双亲在数组中的索引值 int visited[Maxsize]; //访问标记数组,已访问写为1 void BFS_MIN_Distance(Graph G,int v) { for(int i=0;i<G.vexnum;i++) { d[i]=∞; //初始化路径长度 path[i]=-1; //初始化并查集,此时并查集是G.vexnum个树构成的森林 } d[v]=0; //起始顶点路径长度为0 visited[v]=1; //标记起始顶点已访问 EnQueue(Q,v); //起始顶点入队 while(!isEmpty(Q)) { int x;//因为下面的for循环会读x的相邻结点,那么在构造生成树时就让X成为x的相邻结点的双亲,也表示到达x的相邻结点要经过x GetHead(Q,x); for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) //每一次for循环w得到的是x的相邻结点 { if(!visited[w]) { d[w]=d[x]+1; //路径长度+1 path[w]=x; //要到达w的最后一步是经过x visited[w]=1; //标记已访问 EnQueue(Q,w); //将顶点w入队 } } DelQueue(Q,x); //队头元素出队 } } /*-----------------------------------------------*/