非线性结构算法

第一章：集合与字典

一、集合 / 哈希表

认识哈希表

1. 是什么

哈希表（Hash table），也叫散列表。

哈希表是根据关键码而直接进行访问的数据结构。

2. 哈希函数

哈希化：将大数字转化成数组范围内下标的过程，就称之为哈希化。

哈希函数：通常会将单词转成大数字，大数字在进行哈希化的代码实现放在一个函数中，这个函数称为哈希函数。

哈希表：最终将数据插入到的这个数组，对整个结构的封装，就称之为是一个哈希表。

1）数字相加

假设我们要把字符串（比如单词）存入哈希表。最直观的想法是把每个字母的 ASCII 码相加。

例子：cats = 99 + 97 + 116 + 115 = 427

致命缺点：这种加法完全忽略了字母的顺序。比如 cats、cast、tacs 加起来总和全都是 427。遇到这些词时，它们会完全冲突（映射到同一个哈希槽中）。

2）幂的连乘

也叫多项式哈希。

为了使得连字母顺序交换也能得到不同的哈希值，给每个位置的字符赋予一个权重。这个权重，就是某个数字（底数，一般用一个质数比如 31、37、131）的连续幂次方。

假设我们选择底数为 $P$（读作底数或基数），对于一个长度为 $n$ 的字符串 $S$，它的转化公式就是多项式展开：

$$Hash=(S_0\times P^{n-1})+(S_1\times P^{n-2})+\cdots +(S_{n-2}\times P^1)+(S_{n-1}\times P^0)$$

举个例子

将单词 cats 进行哈希，选择常数 $P=37$：

• c = 99
• a = 97
• t = 116
• s = 115

代入公式（这里就是所谓的“幂的连乘”）：

$$Hash=99\times {37}^3+97\times {37}^2+116\times {37}^1+115\times {37}^0$$

显然，因为带上了 ${37}^3$、${37}^2$ 这样的次幂权重，一旦字符换了位置（比如 c 放到了末尾），乘的次幂就变了，最终算出来的值就截然不同了。

3）霍纳法则

在实际写代码的时候，不可能真的去算 ${37}^3$、${37}^4$，甚至是 ${37}^{100}$（字符串长了极容易溢出且计算量大）。

所以利用初中数学里的提取公因式，上面的式子可以化简为嵌套的乘法（多项式求值优化）：

$$Hash=(((99\times 37)+97)\times 37+116)\times 37+115$$

代码实现

function hashString(str) {
  let hashCode = 0;
  // 选一个质数作为底数，Java 的 String.hashCode() 就使用的是 31
  let prime = 31; 

  for (let i = 0; i < str.length; i++) {
    // 霍纳法则：上一次的哈希值乘以质数，加上当前的字符编码
    hashCode = prime * hashCode + str.charCodeAt(i);
  }
  return hashCode;
}

通过这种每一步都 乘以一个常数 + 加上新字符 的方式，就高效地用代码实现了理论上的幂的连乘。

数学奥秘

hashCode = prime * hashCode + str.charCodeAt(i)

假设我们要对一个长度为 4 的字符串进行哈希，字符分别是 $C_0,C_1,C_2,C_3$，底数是 $P$ (也就是 prime)。

按照标准的“幂的连乘”公式，应该是这样的：

$$Hash=C_0\times P^3+C_1\times P^2+C_2\times P^1+C_3$$

这看起来需要算 3 次方、2 次方。但是，我们从左往右不断把 $P$ 当作公因式提取出来，公式就会变成这样：

1. 提取最外层的 $P$：

$$Hash=(C_0\times P^2+C_1\times P^1+C_2)\times P+C_3$$

2. 再提取里面的 $P$：

$$Hash=\mathbf{(}\mathbf{(}{\mathbf{C}}_{\mathbf{0}}\times \mathbf{P}\mathbf{+}{\mathbf{C}}_{\mathbf{1}}\mathbf{)}\times \mathbf{P}\mathbf{+}{\mathbf{C}}_{\mathbf{2}}\mathbf{)}\times \mathbf{P}\mathbf{+}{\mathbf{C}}_{\mathbf{3}}$$

注意看最后这个式子，它里面完全没有任何幂乘运算了，只有形式一致的嵌套式：“括号里的结果 $\times P$ + 新项”。

3. 哈希碰撞

若哈希函数计算出的索引一致，会出现哈希碰撞。

1）拉链法 / 链地址法

2）开放地址法

寻找空白的单元格来添加重复的数据。

• 线性探测

  挨着往下找（步长为 1）。

• 二次探测

  跳跃着往下找（步长为平方数：1, 4, 9, 16 ...）。

• 再哈希法

  用第二套公式（第二个哈希函数）来决定每个数据专属的步长。

二、代码实现

第二章：树

一、简介

1. 是什么

树是计算机编程中最重要、最核心的一种数据结构。

在日常生活中，树状结构也是广泛存在的，例如家族的族谱、公司部门结构图等。在计算机编程中，树更是无处不在，你平时接触到的二叉查找树、堆、并查集、线段树、树状数组、前缀树、红黑树，这些都是属于树这种数据结构的一种。

应用场景：数据库索引 B+ 树、编译器的 AST 语法树、操作系统的文件系统、Vue 中的虚拟 DOM ……

2. 术语与度量

术语

1. 节点：树的基本单位，一棵树就是由一个一个节点组成的。
2. 边：两个节点之间的连接或链接。如果节点 A 和节点 B 之间存在一条边，A 可能是父节点，B 可能是子节点，反之亦然。
3. 根节点：整颗树的顶端节点，它上面没有父节点。
4. 父节点：一个节点的上一级节点。
5. 子节点：一个节点派生出来的节点，只计算下一层。例如 A 节点的子节点就是 B、C、C 节点的子节点就是 E、F。
6. 兄弟节点：具备相同父节点的节点互称为兄弟节点。
7. 叶子节点：没有子节点的节点，称之为叶子节点，位于树的末端。
8. 内部节点：任何至少有一个子节点的节点（即，不是叶节点的任何节点）。
9. 子树：树的一部分，由一个节点及其所有后代组成。它本身也是一棵以该节点为根的有效树。
10. 森林：由 m（m >= 0）棵互不相交的树的集合称为森林。

树的度量

1. 深度：对于任意节点 n，n 的深度为从根到 n 的唯一路径长，根的深度为 0。
2. 高度：对于任意节点 n，n 的高度为从 n 到一片树叶的最长路径长，所有树叶的高度为 0。
3. 层：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推。
4. 度：一个节点的子节点的个数称之为度。例如 A 节点的度就为 2、D 节点的度为 3，C 节点的度也为 2。

3. 树的表示法

• 图形表示法

• 符号表示法：用小括号先将根节点放入到括号里面，然后将子节点从左往右放入括号，对子节点的子节点也采用相同的方式。同层的子节点使用逗号隔开。

  (A(B(D(G, H, I)), C(E(J), F)))

4. 树的分类

二叉树

• 定义：每个节点最多有 2 个子节点（左、右子节点）。

• 变种：

  • 满二叉树：所有非叶子节点均有 2 个子节点，且所有叶子在同一层。

  • 完全二叉树：除最后一层外，其他层均满，且最后一层节点左对齐。

  • 二叉搜索树 (Binary Search Tree) ：左子树所有节点值 < 根节点值 < 右子树所有节点值。用于快速查找、插入、删除。

  • 平衡二叉搜索树：通过旋转操作保持树高平衡，确保操作效率稳定在。

    O(logn)

    常见类型：

    • AVL 树：严格平衡（左右子树高度差 ≤ 1），适合读密集型场景。
    • 红黑树：弱平衡（通过颜色标记规则），插入删除效率更高，广泛应用于系统级代码。
    • Treap：结合 BST 和堆特性，随机优先级保证平衡。
    • 伸展树 (Splay Tree)：通过“伸展”操作将最近访问节点移至根，适合局部性访问。

多叉树

多叉树也存在多种类型：

• B 树 (B-Tree) ：每个节点可包含多个键和子节点，所有叶子在同一层。常用于数据库索引、文件系统。
• B+ 树：针对 B 树的一种优化，非叶子节点仅存键，数据全存储在叶子节点，叶子节点通过指针链接。
• 字典树 (Trie) ： 每个节点存储字符，路径构成字符串，叶子节点标记单词结束。前缀匹配高效，常用于自动补全、拼写检查、IP 路由表。

特殊用途树

• 堆 (Heap) ：一种完全二叉树，满足堆性质（最大堆/最小堆）。
• 线段树 (Segment Tree) ：每个节点代表一个区间，支持区间查询与更新。常用于动态范围统计，例如区间最值、区间和。
• 哈夫曼树 (Huffman Tree) ：构造带权路径最短的二叉树，用于无损数据压缩。常用于 zip 压缩、jpeg 编码。
• 并查集 (Union-Find) ：森林表示集合，支持合并与查找操作。常用于连通性问题，例如社交网络好友关系。
• KD 树 (K-Dimensional Tree) ：二叉树，交替按不同维度划分空间。常用于多维数据近邻搜索，例如地理坐标查询的场景。

其他变种

• 二叉线索树 (Threaded Binary Tree) ： 利用空指针记录前驱/后继，加速遍历（中序、先序、后序）。
• 后缀树 (Suffix Tree) ：压缩字典树，存储字符串所有后缀。常用于模式匹配、生物信息学中 DNA 序列分析等场景。
• 决策树 (Decision Tree) ：机器学习中的分类与回归模型，通过树结构划分特征空间。

二、二叉树

1. 是什么

2. 代码实现

1）基本结构

import Node from "../types/Node"

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null
  right: TreeNode<T> | null = null
} 

class BSTree<T> {
  private root: TreeNode<T> | null = null
}

export {}

2）插入操作

/* 插入数据的操作 */
insert(value: T) {
  // 1.根据传入value创建Node(TreeNode)节点
  const newNode = new TreeNode(value)

  // 2.判断当前是否已经有了根节点
  if (!this.root) { // 当前树为空
    this.root = newNode
  } else { // 树中已经有其他值
    this.insertNode(this.root, newNode)
  }
}

private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
  if (newNode.value < node.value) { // 去左边继续查找空白位置
    if (node.left === null) { // node节点的左边已经是空白
      node.left = newNode
    } else {
      this.insertNode(node.left, newNode)
    }
  } else { // 去右边继续查找空白位置
    if (node.right === null) {
      node.right = newNode
    } else {
      this.insertNode(node.right, newNode)
    }
  }
}

3）遍历操作

[1] 先序遍历

先序遍历或前序遍历：根节点 ==> 左子树 ==> 右子树

遍历出来的顺序如下：A -> B -> D -> H -> I -> E -> J -> K -> C -> F -> L -> M -> G -> N -> O

// 先序遍历
preOrderTraverse() {
  this.preOrderTraverseNode(this.root)
}

private preOrderTraverseNode(node: TreeNode<T> | null) {
  if (node) {
    console.log(node.value)
    this.preOrderTraverseNode(node.left)
    this.preOrderTraverseNode(node.right)
  }
}

[2] 中序遍历

中序遍历：左子树 ==> 根节点 ==> 右子树

中序遍历的具体顺序可以看节点投影，投影出来的线性顺序就是遍历出来的顺序。

遍历出来的顺序如下：H -> D -> I -> B -> J -> E -> K -> A -> L -> F -> M -> C -> N -> G -> O

// 中序遍历
inOrderTraverse() {
  this.inOrderTraverseNode(this.root)
}

private inOrderTraverseNode(node: TreeNode<T> | null) {
  if (node) {
    this.inOrderTraverseNode(node.left)
    console.log(node.value)
    this.inOrderTraverseNode(node.right)
  }
}

[3] 后序遍历

中序遍历：左子树 ==> 右子树 ==> 根节点

遍历出来的顺序如下：H -> I -> D -> J -> K -> E -> B -> L -> M -> F -> N -> O -> G -> C -> A

// 后序遍历
postOrderTraverse() {
  this.postOrderTraverseNode(this.root)
}

private postOrderTraverseNode(node: TreeNode<T> | null) {
  if (node) {
    this.postOrderTraverseNode(node.left)
    this.postOrderTraverseNode(node.right)
    console.log(node.value)
  }
}

[4] 层序遍历

// 层序遍历
levelOrderTraverse() {
  // 1.如果没有根节点, 那么不需要遍历
  if (!this.root) return

  // 2.创建队列结构
  const queue: TreeNode<T>[] = []
  // 第一个节点时根节点
  queue.push(this.root)

  // 3.遍历队列中所有的节点(依次出队)
  while (queue.length) {
    // 3.1.访问节点的过程
    const current = queue.shift()!
    console.log(current.value)

    // 3.2.将左子节点放入到队列
    if (current.left) {
      queue.push(current.left)
    }

    // 3.3.将右子节点放入到队列
    if (current.right) {
      queue.push(current.right)
    }
  }
}

4）最值

/* 获取最值操作: 最大值/最小值 */
getMaxValue(): T | null {
  let current = this.root
  while (current && current.right) {
    current = current.right
  }

  return current?.value ?? null
}

getMinValue(): T | null {
  let current = this.root
  while (current && current.left) {
    current = current.left
  }

  return current?.value ?? null
}

5）搜索

/* 搜索特定的值, 返回 boolean */
search(value: T): boolean {
  let current = this.root
  while (current) {
    // 找到了节点
    if (current.value === value) return true

    if (current.value < value) {
      current = current.right
    } else {
      current = current.left
    }
  }

  return false
}

6）删除节点

[1] 删除功能实现

remove (value: T): boolean {
  // 1.搜索: 当前是否有这个value
  const current = this.searchNode(value)
  if (!current) return false

  // 2.获取到三个东西: 当前节点/父节点/是属于父节点的左子节点, 还是右子节点
  // 2.如果删除的是叶子节点
  if (current.left === null && current.right === null) {
    if (current === this.root) {
      // 根节点
      this.root = null
    } else if (current.isLeft) {
      // 父节点的左子节点
      current.parent!.left = null
    } else {
      current.parent!.right = null
    }
  }

  // 3.只有一个子节点: 只有左子节点
  else if (current.right === null) {
    if (current === this.root) {
      this.root = current.left
    } else if (current.isLeft) {
      current.parent!.left = current.left
    } else {
      current.parent!.right = current.left
    }
  }

  // 4.只有一个子节点: 只有右子节点
  else if (current.left === null) {
    if (current === this.root) {
      this.root = current.right
    } else if (current.isLeft) {
      current.parent!.left = current.right
    } else {
      current.parent!.right = current.right
    }
  }

  // 5.有两个子节点
  else {
    const successor = this.getSuccessor(current)
    if (current === this.root) {
      this.root = successor
    } else if (current.isLeft) {
      current.parent!.left = successor
    } else {
      current.parent!.right = successor
    }
  }

  return true
}

要删除的节点的子节点有两个，需要从子节点中找到比要删除节点的值要么小一点或大一点的节点。而这两个节点有特殊的名字。

• 前驱：比要删除节点的值要么小一点的节点叫前驱。
• 后继：比要删除节点的值要么大一点的节点叫后驱。

/* 实现删除操作 */
private getSuccessor (delNode: TreeNode<T>): TreeNode<T> {
  // 获取右子树
  let current = delNode.right
  let successor: TreeNode<T> | null = null
  while (current) {
    successor = current
    current = current.left
    if (current) { // 用于第 16 行代码的操作
      current.parent = successor
    }
  }

  // 拿到了后继节点
  if (successor !== delNode.right) { // 例如: 假设没有 8 节点, 删除 7, 后继节点为 9, 这时候不需要操作后继节点的 right
    successor!.parent!.left = successor!.right // 例如: 删除 15, 后继节点为 18, 需要把 19 节点给 20 节点的 left
    successor!.right = delNode.right
  }

  // 一定要进行的操作: 将删除节点的 left, 赋值给后继节点的 left
  successor!.left = delNode.left // 例如: 删除 7, 后继节点为 8, 需要把 5 节点给 8 的 left

  return successor!
}

第三章：堆

一、简介

二叉堆在计算机科学中是一种非常著名的数据结构，由于它能高效、快速的找出最大值、最小值，常常被用于优先队列。它也被用于著名的排序算法中。

二叉堆分为两种：

1. 最小堆：特点是每个子节点都大于等于父节点，因此在最小堆中可以快速找出最小值。
2. 最大堆：每个子节点都小于等于父节点，因此在最大堆中可以快速找出最大值。

二叉堆本质上是一颗完全二叉树，但是和前面介绍过的二叉搜索树又有一定的区别：

• 二叉搜索树：左侧子节点总是比父节点小，右侧子节点总是比父节点大。
• 二叉堆：不需要遵循二叉搜索树的原则。

[4, 2, 7, 1, 3, 6, 5]

二叉堆的存储

使用数组来存储二叉堆。

已知一个节点的索引下标值 index，可以求出：

1. 左子节点的下标值：2 * index + 1
2. 右子节点的下标值：2 * index + 2
3. 父节点的下标值：Math.floor((index - 1) / 2)

二、实现代码

// utils.js
const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
}
function defaultCompare(a, b){
  if(a === b) return Compare.EQUALS;
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN
}
module.exports = {
  defaultCompare
}

const { defaultCompare } = require("./utils.js")
// 最小堆类
class MinHeap{
  /**
   * compareFn - 比较方法
   */
  constructor(compareFn = defaultCompare){
    this.compareFn = compareFn;
    this.heap = []; // 用于存储最小堆所有元素
  }
  // 获取左子节点下标
  getLeftIndex(index){
    return 2 * index + 1;
  }
  // 获取右子节点下标
  getRightIndex(index){
    return 2 * index + 2;
  }
  // 获取父节点
  getParentIndex(index){
    if(index === 0) return undefined;
    return Math.floor((index - 1) / 2);
  }
  // 获取当前最小堆的最小值
  // 最小堆中，堆顶的元素就是最小的，是数组的第一个元素
  findMini(){
    return this.isEmpty() ? undefined : this.heap[0];
  }
  // 还有一些工具方法
  size() {
    return this.heap.length;
  }
  isEmpty() {
    return this.size() <= 0;
  }
  clear() {
    this.heap = [];
  }
}

第四章：图

一、简介

图是网络结构的抽象模型，由一组顶点和边组成。下图就是一个典型的图结构：

2. 相关术语

1. 顶点：图里面一个一个数据元素被称之为顶点。之前在线性表中称之为元素，树里面称之为节点。

   另外，线性表可以没有元素（空表），树里面可以没有节点（空树），但是在图结构中不能够没有顶点。

2. 相邻顶点：由一条边连接在一起的两个顶点，称之为相邻顶点。

3. 度：一个顶点的相邻顶点的数量。

   出度：指向其他相邻顶点的边。

   入度：指向我自己的边。

4. 路径：指的是一连串顶点序列。其中有一个概念称之为简单路径，指的就是不包含重复顶点的路径。

5. 回路 / 环：从某一个顶点出发，最后回到该顶点，形成了一个闭环。环也会算作是一个简单路径。

3. 分类

1）无向图和有向图

1. 无向图：顾名思义就是顶点之间是没有方向的

由于是无方向的，因此连接 A 和 D 的边，可以表示为 (A, D)，也可以写成(D, A)。对于无向图来讲，G = (V,{E})，其中顶点集合 V = {A,B,C,D}，边集合 E = {(A,B), (B,C), (C,D), (D,A), (A,C)}

在无向图中，如果每一个顶点都和其他所有顶点相连，则称该无向图为无向完全图。如下图所示：

一个含有 n 个顶点的无向完全图拥有 $\frac{n\ast (n-1)}{2}$ 条边。例如上面的无向完全图有 4 个顶点，根据公式计算出最多拥有 6 条边。

2. 有向图：顶点之间有明确的方向

有向图是有方向的，使用尖括号来表示，尖括号中的第一个节点表示 tail，第二个节点表示 head。例如上图为 G = (V,{E})，其中顶点集合 V = {A,B,C,D}，边集合 E = {<A,D>, <B,A>, <C,A>, <B,C>}。

在有向图中，如果任意两个顶点之间都存在方向相反的指向，称之为有向完全图。例如下图就是一个有向完全图：

一个含有 n 个顶点的无向完全图拥有 $n\ast (n-1)$ 条边。例如上面的有向完全图有 4 个顶点，根据公式计算出最多拥有 12 条边。

2）无权图和加权图

图还可以是加权的。如下图所示，加权图的边被赋予了权值。

3）子图

假设有两个图，一个图是 G = (V, {E})，另一个图是 G' = (V', {E'})，如果

$$\begin{array}{rl}{V}^{\prime }& \subseteq V\\ E^{\prime }& \subseteq E\end{array}$$

那么我们称 G' 为 G 的子图。

举个例子：

4）联通图

通常指的是无向图。如果一个无向图中的任意两个顶点都存在一条可以相互到达的路径，那么这个图称为“联通图”。反之则成为“非联通图”。也就是说：

• 联通图：整张图只构成一个联通块，任意两顶点之间都能到达。
• 非联通图：图中出现“孤立”或“分块”的情况。

那么有向图中存不存在联通的概念呢？其实也存在，分为强联通和弱联通：

• 强联通：对于图中的任意两个顶点 V1 和 V2，都有从 V1 到 V2 的有向路径，并且也有从 V2 到 V1 的有向路径。这样的图被称之为强联通图。
• 弱联通：如果将有向图的所有有向边都看作无向边，能形成一幅联通图，则称该有向图是弱连通的。也就是说，忽略了方向后，任意两点间还是能连通，但不一定存在相互可达的有向路径。

4. 图的表示

顶点：数组或集合 set 存放数据。不过实际代码中也可以不定义存放顶点的变量，因为顶点的数据包含在了边的 Map 映射里的 key 中。

边：使用邻接矩阵或邻接表存放数据。

1）邻接矩阵

[1] 是什么

本质上就是使用一个二维数组来存储图。举个例子，假设有如下的有向图：

那么使用一个二维数组存储的结构如下：

$$\left[\begin{array}{ccccc}0& 1& 0& 1& 0\\ 0& 0& 0& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}\right]$$

每一行代表一个顶点，每一列也代表一个顶点。例如上面的图有 5 个顶点，那么这个二维数组就是 $5\times 5$ 的二维数组。如果是 n 个顶点，那么这个二维数组就是 $n\times n$。

其中 1 表示顶点之间是有连接关系的。如 V1 顶点连接 V2，因此第一行第二列就是 1、V1 顶点连接 V4，因此第一行第四列就是 1。

接下来是无向图，如下：

使用邻接矩阵的表示法来表示的话，如下：

$$\left[\begin{array}{ccccc}0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 1& 1\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\end{array}\right]$$

因为无向路是没有方向的，因此 V1 顶点连接 V2 顶点的同时，V2 顶点也连接 V1 顶点。

带边权的图

另外，我们知道图可以是带边权的，此时在二维数组中存储的就是具体的边权值，而非简单的记入 1。

下面是具体的例子。首先是带边权的有向图：

表示出来就是：

$$\left[\begin{array}{ccccc}\mathrm{\infty }& 5& \mathrm{\infty }& 4& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 4\\ \mathrm{\infty }& 1& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 2& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 2& \mathrm{\infty }& \mathrm{\infty }\end{array}\right]$$

注意，现在没有相连的两个顶点，不能用 0 来表示，因为 0 会存在歧义，被误解为边权值。JS 里面就可以使用 Infinity。

下面是带边权的无向图示例：

表示出来就是：

$$\left[\begin{array}{ccccc}\mathrm{\infty }& 5& \mathrm{\infty }& 4& \mathrm{\infty }\\ 5& \mathrm{\infty }& 1& \mathrm{\infty }& 4\\ \mathrm{\infty }& 1& \mathrm{\infty }& 2& 2\\ 4& \mathrm{\infty }& 2& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& 4& 2& \mathrm{\infty }& \mathrm{\infty }\end{array}\right]$$

[2] 优缺点

优点

（1）容易判断两个顶点是否有边，例如要判断 V1 和 V2 这两个顶点是否有边，只需要看二维数组 arr[0][1] 和 arr[1][0] 是否有值即可。

（2）容易计算顶点的度。例如 V2 顶点的出度，指的是 V2 顶点指向其他边的数量，下图中 V2 顶点的出度就是 1，入度指的是指向当前顶点的边的数量，V2 的入度就为 2。

上图使用邻接矩阵表示出来：

$$\left[\begin{array}{ccccc}0& 1& 0& 1& 0\\ 0& 0& 0& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}\right]$$

该顶点对应的行的 1 的数量就是该顶点出度的数量，该顶点对应的列的 1 的数量就是入度的数量。

缺点

（1）统计边的数量的效率较低，需要去遍历二维数组，时间复杂度为 O(n²)。

（2）空间复杂度高，因为是二维数组来存储，因此空间复杂度也是 O(n²)。

2）邻接表

例如下面的图：

上面的图虽然有 5 个顶点，但是仅仅有顶点 2 连接顶点 1，如果用上面我们介绍过的邻接矩阵的方式来存储的话，就是：

$$\left[\begin{array}{ccccc}\mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ 9& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\end{array}\right]$$

上面的二维数组，仅仅只存储了一个 9，其他空间都浪费掉了。因此这里可以考虑使用邻接表的方式来存储。

邻接表核心思想

邻接表的核心思想是使用一个一维数组来存储所有的顶点，因此有多少个顶点，这个一维数组的长度就是多少。数组里面的每一项是一

个链表，链表会存储和该顶点连接的所有其他顶点。(tips: 实际代码中会使用 JS 内置的 Map 数据类型来实现邻接表)

我们还是来看一个具体的例子，假设还是下面的有向图：

那么使用数组存储的结构如下：

数组的每一项，是一个链表。这里以 V1 顶点为例。V1 指向了 V2 和 V4，V2 和 V4 这两个顶点在数组中的下标分别为 1 和 3，因此整个链表如蓝色部分所示。

注意这里 V2 和 V4 并不存在具体的顺序，因此在链表中的表现也可以是下标为 3 的顶点在前面，下标为 1 的顶点在后面。

因此，上面的有向图使用邻接表来存储的话，完整的邻接表为：

搞清楚了有向图后，无向图基本也是相同的道理，仅仅是链表的长度会更长一些，因为会包含出度和入度。例如下面的无向图：

使用邻接表的方式来存储的话，完整的数组结构如下图：

二、图的代码实现

1. 基本结构

class Graph<V, E> {
  // 顶点 (可以不定义, 使用 map 类型的 adjList 变量中的 key 代替, 这样就能少维护一个变量)
  private verteces: V[] = []
  // 通过 map 来存储所有顶点以及所有出边的信息, 最终 map 所存储的信息大致如下
  // Map {
  //   'A' => [{node: 'B', weight: 2}, {node: 'C', weight: 1}],
  //   'B' => [{node: 'C', weight: 3}],
  //   'C' => [],
  // }
  private adjList: Map<V, E[]> = new Map() // 存储边的, 使用邻接表

  constructor(isDirected = false){
    this.isDirected = isDirected;
  }
}

export {}

接下来实现一些辅助方法。

// 获取图中所有的顶点列表
getVertices(): V[] {
  return [...this.adjList.keys()];
}

// 获取图中所有的边
getEdges(): [V, V][] {
  let edges = []; // 这个数组就存储所有的边
  for(let [vertex, neighbors] of this.adjList){
    for(let {node} of neighbors){
      edges.push([vertex, node]); // 数组的每一项是 [起点节点，终点节点]
    }
  }
  return edges;
}

// 统计图中所有边的数量
edgeCount(): number {
  let count = 0; // 计数器，对边进行计数
  for(let [_, neighbors] of this.adjList){
    count += neighbors.length;
  }

  // 如果是无向图，每条边在两个顶点的邻接表中会出现两次，需要除以2
  return this.isDirected ? count : count / 2;
}

// 判断图中是否存在某一条边
// src - 起点
// dest - 终点
hasEdge(src: V, dest: V): boolean {
  if(!this.adjList.has(src)) return false;
  return this.adjList.get(src).some(nodeObj => nodeObj.node === dest);
}

2. 添加操作

添加操作分为两个：

1. 添加顶点

   g.addVertex('A');

2. 添加边

   g.addEdge('A', 'B', 5);

代码如下：

/**
 * 添加一个顶点到图中。
 * @param {*} vertex - 新顶点的名称或标识
 */
addVertex(vertex: V): void {
  // 将顶点添加到set中
  if(!this.verteces.has(vertex)){
    this.verteces.add(vertex)
  }
  // 创建一个邻接表中的数组
  if(!this.adjList.has(vertex)){ // 先判断主要是防止现有数据被覆盖
    this.adjList.set(vertex, []);
  }
}

/**
 * 添加一条边 (支持有向/无向、支持权重)
 * @param {*} src - 边的起点
 * @param {*} dest - 边的终点
 * @param {number} [weight=1] - 该边的权重 (可选, 默认1)
 */
addEdge(src: V, dest: V, weight? = 1): void {
  // 首先需要判断一下，起点和终点是否存在于 map 中
  // 如果没有，需要先添加对应的顶点
  if(!this.adjList.has(src)) this.addVertex(src);
  if(!this.adjList.has(dest)) this.addVertex(dest);

  // 添加边
  const srcNeighbors = this.adjList.get(src); // 先获取起点对应的连接顶点数组
  // 接下来需要检查一下，看是否已经有了这条边
  let hasExist = srcNeighbors.some(nodeObj => nodeObj.node === dest);
  if(!hasExist){ // 不存在才添加
    srcNeighbors.push({node : dest, weight})
  }

  // 如果是无向图，还需要添加 dest --> src
  if(!this.isDirected){
    const destNeighbors = this.adjList.get(dest); // 先获取起点对应的连接顶点数组
    // 接下来需要检查一下，看是否已经有了这条边
    let hasExist = destNeighbors.some(nodeObj => nodeObj.node === src);
    if(!hasExist){
      destNeighbors.push({node : src, weight})
    }
  }
}

3. 删除操作

同样分为删除顶点和删除边

g.removeVertex("B");
g.removeEdge("A", "C");

实现代码：

/**
 * 移除一个顶点, 以及与它相关的所有边 (出边和入边)
 * @param {*} vertex - 要移除的顶点
 */
removeVertex(vertex: V): void {
  if(!this.verteces.has(vertex) && !this.adjList.has(vertex)) return;

  // 开始进行删除操作

  // 这里只是删除了对应的顶点以及顶点对应的边的集合
  this.verteces.delete(vertex);
  this.adjList.delete(vertex);

  // 还有一个很重要的步骤, 删除其他顶点对该顶点的指向
  for(let [key, edgeArr] of this.adjList.entries()){
    this.adjList.set(key, edgeArr.filter(nodeObj => nodeObj.node !== vertex))
  }
}

/**
 * 移除一条边
 * @param {*} src - 边的起点 A
 * @param {*} dest - 边的终点 B
 */
removeEdge(src: V, dest: V): void {
  if(!this.adjList.has(src)) return;

  // 接下来进行过滤操作，假设删除 AB 这条边
  this.adjList.set(
    src,
    this.adjList.get(src).filter(nodeObj => nodeObj.node !== dest)
  )

  // 注意：如果是无向图，也需要移除 dest --> src 这条边
  if(!this.isDirected && this.adjList.has(dest)){
    this.adjList.set(
      dest,
      this.adjList.get(dest).filter(nodeObj => nodeObj.node !== src)
    )
  }
}

4. 遍历

1）广度优先搜索 BFS

广度优先遍历，用一句话来概括其核心思路就是层层扩散。这里我们还是先以一个有向图为例：

首先我们选择 V1 作为起始顶点，那么：

第一层：V1
第二层：V2 V4
第三层：V5 V3

当 V1 作为顶点时，它的下一层就是 V2 和 V4 这两个顶点，然后取 V2 找它的下一层，就是 V5，取 V4 找它的下一层就是 V3。注意在寻找下一层顶点的时候，要按照上一层顶点的顺序来找。例如，在第二层的时候，V2 在 V4 前面，因此在开始第三层的时候，先找 V2 的下一层顶点，然后再找 V4 的下一层顶点。最终，按照广度优先遍历出来的顺序为：V1 → V2 → V4 → V5 → V3。

另外，广度优先遍历的顺序，同样不是唯一的。例如在上面的例子中，第二层我们把 V4 放在前面，V2 放在后面，导致第三层也会受到影响。倘若第二层将 V4 放在 V2 前面，那么遍历出来的顺序就是 V1 → V4 → V2 → V3 → V5。

对于一个无向图，广度优先遍历的思路也是一样的。例如下面的无向图：

其遍历的路径有（括号表示层数）：

(V1) → (V2 → V4) → (V3 → V5)
(V1) → (V2 → V4) → (V5 → V3)
(V1) → (V4 → V2) → (V3 → V5)

代码实现

/**
 * 广度优先搜索 (BFS), 从指定顶点开始遍历。
 * @param {*} startVertex - 起始顶点
 * @returns {Array} 返回按访问顺序得到的顶点列表
 */
bfs(startVertex: V): V[] {
  if(!this.adjList.has(startVertex)) return [];

  const result = []; // 存储最终的结果
  const visited = new Set(); // 创建Set结构, 记录某一个顶点是否被访问过
  visited.add(startVertex);
  const queue = []; // 需要将每一层的顶点加入到队列里面
  queue.push(startVertex);

  // 遍历队列中每一个顶点
  while(queue.length > 0){
    const current = queue.shift()!; // 先拿到这个顶点
    result.push(current);

    // 接下来就需要寻找该顶点对应的下一层
    for(let nodeObj of this.adjList.get(current)){
      const v = nodeObj.node;
      if(!visited.has(v)){
        visited.add(v);
        queue.push(v);
      }
    }
  }

  return result;
}

2）深度优先搜索 DFS

图的深度优先搜索，其实就是深度优先遍历，如果用一句话来概括，那就是不撞南墙不回头。举个例子，假设有如下的有向图：

然后我们从 V1 出发，那就可以是这样的顺序：

V1 → V2 → V5 → V3

首先从 V1 出发，下一个顶点到 V2，然后再下一个顶点到 V5，，然后再下一个顶点到 V3。到了 V3 后发现后面没有顶点了，则回退到 V5，发现 V5 也没有其他的路，接着在回退到 V2，发现 V2 也没有其他的路，于是回退到 V1，然后访问 V4。因此整个遍历出来的顺序为：

V2，V2 也没有其他的路，于是回退到 V1，然后访问 V4 和 V3。因此整个遍历出来的顺序为：

V1 → V2 → V5 → V3 → V4

回到 V1 后，到下一个顶点 V4，从而完成了一整个图的遍历。

需要注意的是，深度优先遍历的路径不是唯一的，哪怕是从 V1 出发，也可以有如下不同的遍历路径：

V1 → V4 → V3 → V2 → V5
V1 → V4 → V3 → V5 → V2

在上面的例子中，我们选择了 V1 作为我们的起始顶点。那能不能选择其他顶点作为起始顶点呢？

其实也是可以的，例如这里我们选择 V2 作为起始顶点，那么 V2 能够走的路径就是：

V2 → V5

此时你会发现并没有遍历完整张图，所以就还需要再选择一个未遍历的顶点作为起始顶点来进行遍历。

一般来讲，我们可以选择一个入度为 0 的顶点来作为起始顶点，因此在上面的示例中，选择 V1 作为起始顶点是最合适的。

对于无向图的深度优先遍历，道理是一样的，不过相对于有向图，无向图能够走的边会更多一些。例如下面的无向图：

采用深度优先遍历能够走的路径有：

V1 → V2 → V3 → V4 (回退) → V5
V1 → V2 → V3 → V5 (回退) → V4
V1 → V2 → V5 → V3 → V4
V1 → V4 → V3 → V2 → V5
V1 → V4 → V3 → V5 → V2

一共有 5 条路径。

代码实现

dfs(startVertex: V): V[] {
  if(!this.adjList.has(startVertex)) return [];

  const visited = new Set(); // 创建Set结构, 记录某一个顶点是否被访问过
  const result = []; // 存储遍历的结果

  const dfsHelper = (vertex)=>{
    visited.add(vertex);
    result.push(vertex);

    for(let nodeObj of this.adjList.get(vertex)){
      const v = nodeObj.node;
      if(!visited.has(v)){
        // 进入该分支，说明当前这个节点还没有遍历到
        dfsHelper(v);
      }
    }
  }
  dfsHelper(startVertex);

  return result;
}

三、最小生成树

最小生成树（Minimum Spanning Tree, MST）：图结构转为树结构，且边权和最小。

树本身就是一种无环图。

1. 普里姆算法

1）核心思想

普里姆算法（Prim's Algorithm），是一种用于在加权无向联通图中寻找最小生成树的经典算法，其核心思想为：从一个顶点开始，逐步“扩张”树，把与当前树相连的最小权重边加入进来，直到包含图中所有顶点为止。

先确定一个起始顶点，之后把与点亮的点最近的那个点加进来，一直循环这个步骤，直到顶点全被加进来结束。

因此普里姆算法又被称之为加点法。假设现在要针对这个图寻找最小生成树：(tips: 以 A 为起始)

再看一个例子。(tips: 以 V1 为起始)

虽然一个图的最小生成树会根据起始顶点的不同，最终生成的结果不同。但是不管最终生成整样的最小生成树，边权值的总和一定是相等的。另外还有一个规律：针对 $n$ 个顶点的图，最终的最小生成树的边为 $n-1$。

普里姆算法是加节点的，跟边多边少没关系，更适合稠密图。

2）代码实现

对应的 this.adjList 的 Map 结构如下：

Map(5) {
  'A' => [ { node: 'B', weight: 4 }, { node: 'C', weight: 7 } ],
  'B' => [
    { node: 'A', weight: 4 },
    { node: 'D', weight: 6 },
    { node: 'C', weight: 8 }
  ],
  'D' => [
    { node: 'B', weight: 6 },
    { node: 'E', weight: 7 },
    { node: 'C', weight: 5 }
  ],
  'E' => [ { node: 'D', weight: 7 } ],
  'C' => [
    { node: 'A', weight: 7 },
    { node: 'B', weight: 8 },
    { node: 'D', weight: 5 }
  ]
}

/**
 * startVertex - 指定的起始顶点
 * returns - 一个对象 { edges: [], totalWeight: 0}
 * edges 记录有哪些边，totalWeight 记录最小生成树的总权重
 */
primMST(startVertex){
  if(this.isDirected){
    // 进入此分支，说明当前是有向图
    // 有向图一般不太适用
    throw new Error("普里姆算法一般适用于无向图");
  }

  // 接下来判断一下图中是否存在这个起始顶点
  if(!this.adjList.has(startVertex)) return { edges: [], totalWeight: 0}

  // 获取所有的顶点
  const vertices = this.getVertices(); // ['A', 'B', 'C', 'D', 'E']

  const mstSet = new Set(); // 用来存储已经加入到了 MST 的顶点
  const dist = new Map(); // 记录一个顶点连接到已经生成的 MST 的最小权重
  const parent = new Map(); // 记录一个顶点连接到 MST 最优的那条边的“父顶点”

  // 接下来初始化 dist 和 parent
  for(let v of vertices){
    dist.set(v, Infinity);
    parent.set(v, null);
  }
  dist.set(startVertex, 0);
  	// dist = {
    //   A: 0,
    //   B: Infinity,
    //   C: Infinity,
    //   D: Infinity,
    //   E: Infinity
    // }
    // parent = {
    //   A: null,
    //   B: null,
    //   C: null,
    //   D: null,
    //   E: null
    // }
    // mstSet = { } (空)
  
  // 遍历所有的顶点，每一次遍历都会将一个顶点加入到 MST 里面
  for(let i = 0; i < vertices.length; i++){
    // 1. 首先需要找到还没有加入到 MST 并且 dist 是最小的顶点
    let current = null;
    let minDist = Infinity;

    for(let v of vertices){
      if(!mstSet.has(v) && dist.get(v) < minDist){
        minDist = dist.get(v);
        current = v;
      }
    }

    // 如果没有找到这样的顶点（可能图不联通之类的），提前结束
    if(current === null) break;

    // 代码来到这里，说明找到了，将选定的顶点加入到 MST 集合里面
    mstSet.add(current);

    // 现在 current（顶点）已经找到了，需要根据 current 顶点来更新 dist 以及 parent
    for(let neighborObj of this.adjList.get(current)){
      const neighbor = neighborObj.node; // 拿到该顶点（current）对应的邻居顶点
      const weight = neighborObj.weight; // 拿到该顶点（current）到邻居顶点的加权值

      // 接下来更新那些还没有加入 MST，并且存在最小边权的顶点
      if(!mstSet.has(neighbor) && weight < dist.get(neighbor)){
        dist.set(neighbor, weight);
        parent.set(neighbor, current);
      }
    }
  }
  	// i = 0, current = A
  	// mstSet = { 'A' }
  	// 找到 A 的邻居 B(weight = 4)，C(weight = 7)
  	// dist = { A:0, B:4, C:7, D:Infinity, E:Infinity }
  	// parent = { A:null, B:'A', C:'A', D:null, E:null }
  
  	// i = 1, current = B
  	// mstSet = { 'A', 'B' }
  	// 找到 B 的邻居 A(weight = 4) D(weight=6) C(weight=8)
  	// dist = { A:0, B:4, C:7, D:6, E:Infinity }
  	// parent = { A:null, B:'A', C:'A', D:'B', E:null }

  // 生成 MST 的边信息
  const mstEdges = [];
  let totalWeight = 0;

  for(let v of vertices){
    const p = parent.get(v);
    if(p !== null){
      const w = dist.get(v); // 获取到当前这个顶点加入到 MST 时的最小边权值
      mstEdges.push([p, v, w]);
      totalWeight += w;
    }
  }

  return {
    mstEdges,
    totalWeight
  }
}

2. 克鲁斯卡尔算法

1）核心思想

又被称之为加边法。

找图结构中权重最小的边，若找到的边在联通分量里，就丢弃，否则加入，直到所有点都在联通分量里结束。

例一：

例二：

2）代码实现

/**
 * Kruskal（克鲁斯卡尔）最小生成树算法，适用于无向图。
 * 返回生成树的所有边及其总权重。
 * @returns
 *   例如 { edges: [[ 'A', 'B', 4 ], [ 'C', 'D', 5 ], [ 'B', 'D', 6 ], [ 'D', 'E', 7 ]], totalWeight: 22 }
 */
kruskalMST() {
  // 如果是有向图，Kruskal 算法一般不适用，这里直接抛出异常
  if (this.isDirected) {
    throw new Error("克鲁斯卡尔算法一般用于无向图");
  }

  // 1. 需要收集所有的边 [src, dest, weight]
  // 除了简单收集以外，还需要去重，因为是无向图，每条边会出现两次 A-->B,B-->A
  // A < B 的情况才保留
  const edges = [];
  for(let [vertex, neighbors] of this.adjList){
    for(let {node, weight} of neighbors){
      // 比较顶点，避免重复的边
      if(vertex < node){
        edges.push([vertex, node, weight])
      }
    }
  }

  // 上面的代码执行完成后，edges 就会存储所有的边信息，并且没有重复的
  // edges = [
  //   ['A','B',4],  // A <-> B
  //   ['A','C',7],  // A <-> C
  //   ['B','D',6],  // B <-> D
  //   ['B','C',8],  // B <-> C
  //   ['D','E',7],  // D <-> E
  //   ['C','D',5],  // C <-> D
  // ]

  // 接下来就对 edges 按照边权值进行排序
  edges.sort((a, b) => a[2] - b[2]);
  // edges = [
  //   ['A','B',4], // 权重 4
  //   ['C','D',5], // 权重 5
  //   ['B','D',6], // 权重 6
  //   ['A','C',7], // 权重 7
  //   ['D','E',7], // 权重 7
  //   ['B','C',8], // 权重 8
  // ]

  const parent = new Map(); // 用于记录每个顶点的父节点
  const rank = new Map(); // 用于近似表示树的高度，从而在合并两颗树的时候，可以让矮的树挂到高的树下面。

  // 接下来对这两个 Map 进行初始化
  const vertices = this.getVertices(); // 获取所有的顶点 [ 'A', 'B', 'C', 'D', 'E' ]
  for(let v of vertices){
    parent.set(v, v);
    rank.set(v, 0);
  }
  // parent = {
  //   A: 'A',
  //   B: 'B',
  //   C: 'C',
  //   D: 'D',
  //   E: 'E'
  // }
  // rank = {
  //   A: 0,
  //   B: 0,
  //   C: 0,
  //   D: 0,
  //   E: 0
  // }

  // 接下来需要写一个辅助方法
  /**
   * x - 要查找根节点的元素
   * returns x 的根节点
   */
  // parent(A) = B  parent(B) = C  parent(C) = C
  // find(A)-->find(B)-->find(C)
  // 最终 find(A) 的返回值就是 C
  // 这里不仅仅是返回一个顶点的根，而且还做了路径压缩
  // parent.set(B, C)，递归回到外层后还执行了 parent.set(A, C)
  // 最终 A、B、C 的父节点都指向 C，并且以后再 find(A) 或者 find(B) 的时候，直接就得到根节点 C
  const find = (x) => {
    if(parent.get(x) !== x){
      // 如果 x 的父节点不是自己，说明 x 还没有到达根节点
      // 那么就递归的向上查找
      parent.set(x, find(parent.get(x)));
    }
    return parent.get(x);
  }

  // 接收两个顶点
  // 合并两个顶点的联通分量
  const union = (x, y)=>{
    const rootX = find(x); // 找到 x 的根节点
    const rootY = find(y); // 找到 y 的根节点

    // 如果已经在同一个联通分量
    if(rootX === rootY) return false;

    // 接下来是不等的情况，我们就需要合并
    if(rank.get(rootX) > rank.get(rootY)){
      // 说明 X 的树更高
      parent.set(rootY, rootX);
    } else if(rank.get(rootX) < rank.get(rootY)){
      // 说明 Y 树更高
      parent.set(rootX, rootY);
    } else {
      // rank 相等的时候，那么就随便选择一个来作为根
      parent.set(rootY, rootX)
      rank.set(rootX, rank.get(rootX) + 1);
    }
    return true;
  }
  // parent(A) = A, rank(A) = 1, 表示 A 是一颗独立的树，树高为 1
  // parent(B) = B, rank(B) = 0, 表示 B 也是一颗独立的树，但是这颗树要更矮一些
  // union(A, B)
  // rootX = A	rootY = B
  // parent.set(rootY, rootX); --> parent.set(B, A) 表示 B 现在是挂在 A 下面的

  // 最后就是生成返回的 MST 对应的信息
  let mstEdges = [];
  let totalWeight = 0;

  for(let [src, dest, weight] of edges){
    if(union(src, dest)){
      mstEdges.push([src, dest, weight]);
      totalWeight += weight;
    }
  }

  return {
    mstEdges,
    totalWeight
  }
}