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:
个人并不喜欢上面的这种注释方式,函数的注释应该写在函数前面,介绍算法思想。函数如果够短,有了前面的说明,函数内部除非特别晦涩的代码,一般也不需要注释。变量名应该是自注释的,代码本身是精确的无歧义的,注释因为是自然语言反而可能存在歧义造成理解问题。
然而现实是,很多人英文水平有限,习惯各异,变量名含义一般都模糊不清。及时写代码的人英文好点,变量名清晰,但读的人英文差也会理解起来费劲(说我自己呢)。
领取专属 10元无门槛券
私享最新 技术干货