广度优先遍历算法求无权图的单源最短路径思路辨析
原代码是这样
程序代码：
/*-----------------广度优先搜索求单源最短路径-------------------*/
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); //队头元素出队
}
}
/*-----------------------------------------------*/
