不想学算法的前端开发不是好程序员

碎碎念

《算法(第 4 版)》为主,《算法导论》为参考书。即使按照“不追究细枝末节,不做习题,只求踏实把书读一遍”的原则,也看了很长一段时间。 在看书的同时,也装模做样的建了一个 js-algorithms 来记录学习过程。

抄书、将 Java 代码翻译为 JavaScript 代码也实在是没有意思,本文就简单记录一下我看书过程中觉得很赞和迷惑的内容和地方。

正文

二叉树(Binary Tree)中的“树”的概念与图(Graph)中“树”的概念有什么区别?

《算法导论》 P688

树 (数据结构) - Wiki

树的种类:

  • 无序树(自由树):树中任意节点的子节点之间没有顺序关系(一个连通无环的无向图)
    • 生成树:一棵含有其所有顶点的无环连通子图
      • 最小生成树:对于加权图,树中所有边的权值之和最小的生成树
  • 有根树:一棵自由树,其顶点中存在一个与其他顶点不同的顶点,称之为“根节点”
    • 有序树:一棵有根树,树中任意节点的子节点之间有顺序关系
      • 二叉树:一个有序树,每个节点最多含有两个子树的树,需要区分子节点是左还是右

所以,二叉树(Binary Tree)中的“树”说的是有序树,图(Graph)中“树”说的是无序树(自由树)

相关链接:

数组

用数组来完成对“树(Tree)”的数据存储,让我涨了不少姿势。

拿“加权有向图的最小生成树”举个例子:

有以下最小生成树路径

5 -> 1
0 -> 2
7 -> 3
0 -> 4
4 -> 5
3 -> 6
2 -> 7

转换为数组:

// paths[from] = to
const paths = [undefined, 5, 0, 7, 0, 4, 3, 2]

JS Bin on jsbin.com

以上。