首页 > 试题广场 >

设计一个算法,求出无向无权连通图中距离顶点v的最短路径长度为

[问答题]
设计一个算法,求出无向无权连通图中距离顶点v的最短路径长度为k的所有顶点,路径长度以边数为单位计算。要求:
(1)给出算法的基本设计思想;
(2)用算法描述语言描述算法,并要求对算法中的关键步骤给出注释。


利用广度优先遍历对图进行遍历,从v开始,依次访问与v相邻接的各个顶点,利用一个队列存储所有已经访问过的顶点和该顶点与v的最短路径,并将该顶点的标志位置为1表示已经访问过。依次取出队列的各个顶点,如果该顶点存在未访问过的邻接点,首先判断该顶点是否距离v的最短路径为k,如果满足条件将该邻接点输出,否则将该邻接点入队,并将距离v的层次加1。重复执行上述操作,直到队列为空或者存在满足条件的顶点为止。

发表于 2019-09-23 16:00:51 回复(0)
利用广度优先遍历对图进行遍历,从v开始,依次访问与v相邻接的各个顶点,利用一个队列存储所有已经访问过的顶点和该顶点与v的最短路径,并将该顶点的标志位置为1表示已经访问过。依次取出队列的各个顶点,如果该顶点存在未访问过的邻接点,首先判断该顶点是否距离v的最短路径为k,如果满足条件将该邻接点输出,否则将该邻接点入队,并将距离v的层次加1。重复执行上述操作,直到队列为空或者存在满足条件的顶点为止。
发表于 2020-08-11 09:29:15 回复(0)