算法:查找图中两个节点之间的距离

https://learn.freecodecamp.org/coding-interview-prep/data-structures/breadth-first-search

要求给出无向图中一个节点,计算次节点到各个节点之间的距离。

图的结构使用邻接矩阵表示。

先说明一下无向图的邻接矩阵表示形式,无向图的邻接矩阵是一个二维数组,数组的元素 [i, j] = 1 表示节点 i 和 节点 j 之间存在一条边,如果 [i, j]=0 则表示节点 i 和节点 j 之间不存在边。例如如下数组:

第一行[,1,]表示 节点0 和 节点1 之间存在一条边。

第二行[1,,1]表示节点1和节点0之间存在一条边,节点1和节点2之间也存在一条边。

第三行[,1,]表示节点2和节点1之间存在一条边。

现在给定一个节点 root,使用广度优先,计算 root 到其他节点之间的距离。

函数 bfs 返回的是一个距离对象,类似 ,表示 root 到节点0的距离是0(由此可以推断root=0),到节点1的距离是1。

具体实现代码如下:

注意上面的实现中计算的距离并不是最短距离。如果要计算最短距离,则需要在找到抵达路径时不退出 while 循环而是记录当前路径长度与已取得的最小路径长度中的最小值。直到 stack 为空,遍历完所有可能的路径后,返回记录的最小值。

PS:

个人并不喜欢上面的这种注释方式,函数的注释应该写在函数前面,介绍算法思想。函数如果够短,有了前面的说明,函数内部除非特别晦涩的代码,一般也不需要注释。变量名应该是自注释的,代码本身是精确的无歧义的,注释因为是自然语言反而可能存在歧义造成理解问题。

然而现实是,很多人英文水平有限,习惯各异,变量名含义一般都模糊不清。及时写代码的人英文好点,变量名清晰,但读的人英文差也会理解起来费劲(说我自己呢)。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181113G21L5M00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券