| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 644 人关注过本帖
标题:广度优先遍历算法求无权图的单源最短路径思路辨析
只看楼主 加入收藏
ghxjk666
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2022-10-22
结帖率:100%
收藏
 问题点数:0 回复次数:0 
广度优先遍历算法求无权图的单源最短路径思路辨析
原代码是这样
程序代码:
/*-----------------广度优先搜索求单源最短路径-------------------*/
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);        //队头元素出队
        }
    }
/*-----------------------------------------------*/
搜索更多相关主题的帖子: 路径 path 最短路径 int 数组 
2023-03-18 00:09
快速回复:广度优先遍历算法求无权图的单源最短路径思路辨析
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024837 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved