剖析无处不在的数据结构

Last updated 3 years ago

数据结构是计算机中组织和存储数据的特定方式，它的目的是方便且高效地对数据进行访问和修改。数据结构表述了数据之间的关系，以及操作数据的一系列方法。数据又是程序的基本单元，因此无论是哪种语言、哪种领域，都离不开数据结构；另一方面，数据结构是算法的基础，其本身也包含了算法的部分内容。也就是说，想要掌握算法，先有一个巩固的数据结构基础是必要条件。

前端领域也到处体现着数据结构的应用，尤其是随着需求的复杂度上升，前端工程师越来越离不开数据结构。React、Vue 这些设计精巧的框架，在线文档编辑系统、大型管理系统，甚至一个简单的检索需求，都离不开数据结构的支持。是否能够掌握这个难点内容，将是进阶的重要考量。我们应该如何学习数据结构呢？

下图是本讲内容的提纲。

数据结构和学习方法概览

我通常将数据结构分为八大类：

数组：Array
堆栈：Stack
队列：Queue
链表：Linked Lists
树：Trees
图：Graphs
字典树：Trie
散列表（哈希表）：Hash Tables

这么多的类型，这节课该如何介绍呢？我认为，按部就班地只是实现各种数据结构的意义不大，这些内容读者都可以从算法书籍中找到。更重要地是应用，也只有在应用中，才能真正地记住并掌握特定的数据结构，才能在下次有类似场景时，能够想起来相关的数据结构实现。因此，这节课程我将从前端出发，从前端类库或者典型场景入手，结合数据结构来剖析其实现和应用。这需要读者首先对每种数据结构有一个大概认知，我们可以先来细化感知一下：

栈和队列是类似数组的结构，非常多的初级题目要求用数组实现栈和队列，他们在插入和删除的方式上和数组有所差异，但是实现还是非常简单的；
链表、树和图这种数据结构的特点是，其节点需要引用到其他节点，因此在增删时，需要注意对相关前驱和后继节点的影响；
可以从堆栈和队列出发，构建出链表；
树和图最为复杂，因为他们本质上是扩展了链表的概念；
散列表的关键是理解散列函数，明白依赖散列函数实现保存和定位数据的过程；
直观上认为，链表适合记录和存储数据；哈希表和字典树在检索数据以及搜索方面有更大的应用场景。

以上这些“直观感性”的认知并不是“恒等式”， 我们将在下面的学习中去印证这些“认知”，你将会看到熟悉的 React、Vue 框架的部分实现，将会看到典型的算法场景，也请读者做好基础知识的储备。

堆栈和队列

栈和队列是一种操作受限的线性结构，它们非常简单，虽然 JavaScript 并没有原生内置这样的数据结构，但是我们可以轻松地模拟出来。

栈的实现，后进先出 LIFO（Last in、First out）：

class Stack {
  constructor(...args) {
    this.stack = [...args]
  }

  // Modifiers
  push(...items) {
    return this.stack.push(... items)
  }

  pop() {
    return this.stack.pop()
  }

  // Element access
  peek() {
    return this.isEmpty() 
        ? undefined
        : this.stack[this.size() - 1]
  }

  // Capacity
  isEmpty() {
    return this.size() == 0
  }

  size() {
    return this.stack.length
  }
}

队列的实现，先进先出 FIFO（First in、First out）：

class Queue {
  constructor(...args) {
    this.queue = [...args]
  }

  // Modifiers
  enqueue(...items) {
    return this.queue.push(... items)
  }

  dequeue() {
    return this.queue.shift()
  }

  // Element access
  front() { 
    return this.isEmpty()
        ? undefined
        : this.queue[0]
  }

  back() {
    return this.isEmpty()
        ? undefined
        : this.queue[this.size() - 1]
  }

  // Capacity
  isEmpty() {
    return this.size() == 0
  }

  size() {
    return this.queue.length
  }
}

关于栈和队列的实际应用比比皆是：

浏览器的历史记录，因为回退总是回退“上一个”最近的页面，它需要遵循栈的原则；
类似浏览器的历史记录，任何 undo/redo 都是一个栈的实现；
在代码中，广泛应用的递归产生的调用栈，同样也是栈思想的体现，想想我们常说的“栈溢出”就是这个道理；
同上，浏览器在抛出异常时，常规都会抛出调用栈信息；
在计算机科学领域应用广泛，如进制转换、括号匹配、栈混洗、表达式求值等；
队列的应用更为直观，我们常说的宏任务 / 微任务都是队列，不管是什么类型的任务，都是先进先执行；
后端也应用广泛，如消息队列、RabbitMQ、ActiveMQ 等，能起到延迟缓冲的功效。

我们看到不管是栈还是队列，都是用数组来模拟的。数组是最基本的数据结构，但是它的价值是惊人的，这里稍微提一下 React hooks 的本质就是数组。给大家推荐文章：React hooks: not magic, just arrays

另外，与性能后话相关，HTTP 1.1 有一个队头阻塞问题，这个原因就在于队列这样的数据结构：我们先看 HTTP 1.0，对于同一个 tcp 连接，HTTP 1.0 是将所有请求都放入队列当中，这么一来，在客户端，“先进先出”，只有前一个请求得到了响应，下一个请求才会发出。在 HTTP 1.1 中，这样的情况得到了改观，每一个链接都默认是长链接，因此对于同一个 tcp 链接，不必等到前一个响应回来。但是这只是解决了客户端的队头阻塞问题，事实上，HTTP 1.1 规定：服务端的响应返回顺序需要遵循其接收到相应的顺序，这样的问题是：如果第一个请求处理需要较长时间，响应较慢，也都会“拖累”其他后续请求的响应，这仍然是一种队头阻塞。

HTTP 2 采用了二进制分帧和多路复用等方法，同域名下的通信都是在同一个连接上完成，并且这种链接是双向的，在这个链接上可以并行请求和响应而互不干扰。

这里延伸的有点多了，主要是读者需要明白队列和栈这种数据结构的应用，以及利弊。

链表（单向链表和双向链表）

堆栈和队列都可以用数组实现，链表同样和数组一样，都实现了 按照一定的顺序 存储元素，不同的地方在于链表不能像数组一样通过下标访问，而是每一个元素指向下一个元素。我们不再过多介绍链表方面的基础知识，对于链表仍不理解的读者可以先自行学习。

直观上我们就可以得出结论：链表不需要一段连续的存储空间，“指向下一个元素”的方式能够更大限度地利用内存。

根据上面结论可以继续总结，链表的优点在于：

链表的插入和删除操作的时间复杂度是常数级的，我们只需要改变相关节点的指针指向即可；
链表可以像数组一样顺序访问，查找元素的时间复杂度是线性的。

我们来看看链表的应用场景：

React 的核心算法 Fiber 的实现就是链表

关于此我们可以稍作展开。React 最早开始使用大名鼎鼎的 Stack reconciler 调度算法，关于此在之前的课程中已经有所涉及。Stack reconciler 调度算法最大的问题在于： 它是像函数调用栈一样，递归地、自顶向下进行 diff 和 render 相关操作的 ，在 Stack reconciler 执行的过程当中，该调度算法始终会占据浏览器主线程。也就是说在此期间，用户的交互所触发的布局行为、动画执行任务都不会被立即响应，从而影响用户体验。

因此 React Fiber 将渲染和更新过程进行了拆解，简单来说，就是每次检查虚拟 DOM 的一小部分，在检查间隙会检查“是否还有时间继续执行下一个虚拟 DOM 树上某个分支任务”，同时观察是否有更优先的任务需要响应，如果“没有时间执行下一个虚拟 DOM 树上某个分支任务”，且有更高优先级，React 就会让出主线程，直到主线程“不忙”的时候继续执行任务。

React Fiber 因此也很简单，它是将 Stack reconciler 过程分成块，一次执行一块，执行完一块需要将结果保存起来，根据是否还有空闲的响应时间（requestIdleCallback）来决定下一步策略。当所有的块都已经执行完，就进入提交阶段，这个阶段需要更新 DOM，它是一口气完成的。

以上是比较主观地介绍，我们来看更具体的实现。

为了达到“随意中断调用栈并手动操作调用栈”，React Fiber 就是专门用于 React 组件堆栈调用的重新实现，也就是说一个 Fiber 就是一个虚拟堆栈帧，一个 Fiber 的结构类似：

function FiberNode(
  tag: WorkTag,
  pendingProps: mixed,
  key: null | string,
  mode: TypeOfMode,
) {
  // Instance
  // ...
  this.tag = tag;                       

  // Fiber
  this.return = null;
  this.child = null;
  this.sibling = null;
  this.index = 0;

  this.ref = null;

  this.pendingProps = pendingProps;
  this.memoizedProps = null;
  this.updateQueue = null;
  this.memoizedState = null;
  this.dependencies = null;

  // Effects
  // ...
  this.alternate = null; 
}

这么看 Fiber 就是一个对象，通过 parent、children、sibling 维护一个树形关系，同时 parent、children、sibling 也都是一个 Fiber 结构，FiberNode.alternate 这个属性来存储上一次渲染过的结果，事实上整个 Fiber 模式就是一个链表。React 也借此，从依赖于内置堆栈的同步递归模型，变为具有链表和指针的异步模型了。

具体的渲染过程：

function renderNode(node) {
   // 判断是否需要渲染该节点，如果 props 发生变化，则调用 render
   if (node.memoizedProps !== node.pendingProps) {
      render(node)
   }

   // 是否有子节点，进行子节点渲染
   if (node.child !== null) {
      return node.child
   // 是否有兄弟节点，进行兄弟点渲染
   } else if (node.sibling !== null){
      return node.sibling
   // 没有子节点和兄弟节点
   } else if (node.return !== null){
      return node.return
   } else {
      return null
   }
}

function workloop(root) {
   nextNode = root
   while (nextNode !== null && (no other high priority task)) {
      nextNode = renderNode(nextNode)
   }
}

注意在 workloop 当中，while 条件 nextNode !== null && (no other high priority task)，这是描述 Fiber 工作原理的关键伪代码。

当然这里是为了说明链表的数据结构，伪代码较为简略，也没有深入：

requestAnimationFrame(callback)
requestIdleCallback(callback)

的实现和应用。React Fiber 的介绍我们先到此为止，重点是体会链表数据结构的思想。

链表实现

实现链表，我们需要先对链表进行分类，常见的有：

单链表：单链表是维护一系列节点的数据结构，其特点是：每个节点包含了数据，同时包含指向链表中下一个节点的指针。
双向链表：不同于单链表，双向链表特点：每个节点分除了包含其数据以外，还包含了分别指向其前驱和后继节点的指针。

由于篇幅有原因，我们挑选更加复杂的双向链表进行实现，实现思路如下。

首先，根据双向链表的特点，我们实现一个节点构造函数（节点类）：

class Node {
    constructor(data) {
        // data 为当前节点所储存的数据
        this.data = data
        // next 指向下一个节点
        this.next = null
        // prev 指向前一个节点
        this.prev = null
    }
}

有了节点类，我们来初步实现双向链表类：

class DoublyLinkedList {
    constructor() {
        // 双向链表开头
        this.head = null
        // 双向链表结尾
      this.tail = null
    }

    // ...
}

接下来，需要实现双向链表原型上的一些方法，这些方法包括

add：在链表尾部添加一个新的节点
addAt：在链表指定位置添加一个新的节点
remove：删除链表指定数据项节点
removeAt：删除链表指定位置节点
reverse：翻转链表
swap：交换两个节点数据
isEmpty：查询链表是否为空
length：查询链表长度
traverse：遍历链表
find：查找某个节点的索引

add 方法：

add(item) {
  // 实例化一个节点
  let node = new Node(item)

  // 如果当前链表还没有头
  if(!this.head) {
    this.head = node
    this.tail = node
  } 
  // 如果当前链表已经有了头，只需要在尾部加上该节点
  else {
    node.prev = this.tail
    this.tail.next = node
    this.tail = node
  }
}

addAt 方法：

addAt(index, item) {
   let current = this.head
   // 维护查找时当前节点的索引
   let counter = 1
   let node = new Node(item)

   // 如果在头部插入
   if (index === 0) {
     this.head.prev = node
     node.next = this.head
     this.head = node
   } 
   // 非头部插入，需要从头开始，找寻插入位置
   else {
     while(current) {
      current = current.next
      if( counter === index) {
        node.prev = current.prev
        current.prev.next = node
        node.next = current
        current.prev = node
      }
      counter++
    }
  }
}

remove 方法：

remove(item) {
  let current = this.head

  while (current) {
       // 找到了目标节点
    if (current.data === item ) {
      // 目标链表只有当前目标项，即目标节点即是链表头又是链表尾
      if (current == this.head && current == this.tail) {
        this.head = null
        this.tail = null
      } 
      // 目标节点为链表头
      else if (current == this.head ) {
        this.head = this.head.next
        this.head.prev = null
      } 
      // 目标节点为链表尾部
      else if (current == this.tail ) {
        this.tail = this.tail.prev;
        this.tail.next = null;
      } 
      // 目标节点在链表收尾之间，中部
      else {
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
   }
   current = current.next
  }
}

removeAt 方法：

removeAt(index) {
  // 都是从“头”开始遍历
  let current = this.head
  let counter = 1

  // 删除链表头部
  if (index === 0 ) {
   this.head = this.head.next
   this.head.prev = null
  } 
  else {
   while(current) {
    current = current.next
    // 如果目标节点在链表尾
    if (current == this.tail) {
     this.tail = this.tail.prev
     this.tail.next = null
    } 
    else if (counter === index) {
     current.prev.next = current.next
     current.next.prev = current.prev
     break
    }
    counter++
   }
  }
}

reverse 方法：

reverse() {
  let current = this.head
  let prev = null

  while (current) {
   let next = current.next

   // 前后倒置
   current.next = prev
   current.prev = next

   prev = current
   current = next
  }

  this.tail = this.head
  this.head = prev
}

swap 方法，交换两个节点数据值：

swap(index1, index2) {
  // 使 index1 始终小于 index2，方便后面查找交换
  if (index1 > index2) {
    return this.swap(index2, index1)
  }

  let current = this.head
  let counter = 0
  let firstNode

  while(current !== null) {
    // 找到第一个节点，先存起来
    if (counter === index1 ){
        firstNode = current
    } 

    // 找到第二个节点，进行数据交换
    else if (counter === index2) {
      // ES 提供了更简洁交换数据的方法，这里我们用传统方式实现，更为直观
      let temp = current.data
      current.data = firstNode.data
      firstNode.data = temp
    }

    current = current.next
    counter++
  }
  return true
}

isEmpty 方法：

isEmpty() {
  return this.length() < 1
}

这里通过 DoublyLinkedList 类 length 的方法实现。马上看一下 length 方法：

length() {
  let current = this.head
  let counter = 0
  while(current !== null) {
    counter++
    current = current.next
  }
  return counter
}

length 方法通过遍历链表，返回链表的长度。

traverse 方法：

traverse(fn) {
  let current = this.head
  while(current !== null) {
    fn(current)
    current = current.next
  }
  return true
}

有了上面 length 方法的遍历实现，traverse 也就不难理解了，它接受一个遍历执行函数，在 while 循环中进行调用。

最后一个 search 方法：

search(item) {
  let current = this.head
  let counter = 0

  while( current ) {
    if( current.data == item ) {
      return counter
    }
    current = current.next
    counter++
  }
  return false
}

到此，我们就实现了所有 DoublyLinkedList 类双向链表的方法。仔细分析整个实现过程，可以发现：双向链表的实现并不复杂，在手写过程当中，需要开发者做到心中有表，考虑到当前节点的 next 和 prev 取值，逻辑上还是很简单的。

掌握了这些内容，在回想一下链表的应用，回想 React Fiber 的设计和实现，也许一切都变的不再神秘。

树

前端开发者应该对树这个数据结构丝毫不陌生，不同于之前介绍的所有数据结构，树是非线性的。因为树决定了其存储的数据直接有明确的层级关系，因此对于维护具有层级特性的数据，树是一个天然良好的选择。

在前面总领中，我们看到树有很多种分类，但是他们都具有以下特性：

除了根节点以外，所有的节点都有一个父节点
每一个节点都 可以有 若干子节点，如果没有子节点，那么称此节点为叶子节点
一个节点所拥有的叶子节点的个数，称之为该节点的度，因此叶子节点的度为 0
所有节点中，最大的度为整棵树的度
树的最大层次称为树的深度

从应用上来看，我们前端开发离不开的 DOM 就是一个树状结构；同理，不管是 React 还是 Vue 的虚拟 DOM 也都是树。

我们从最基本的二叉树入手，来慢慢深入。

二叉搜索树的实现和遍历

说二叉树最为基本，因为他的结构最简单，每个节点至多包含两个子节点。二叉树又非常有用：因为根据二叉树，我们可以延伸出二叉搜索树（BST）、平衡二叉搜索树（AVL）、红黑树（R/B Tree）等。

二叉搜索树有以下特性：

左子树上所有结点的值均小于或等于它的根结点的值
右子树上所有结点的值均大于或等于它的根结点的值
左、右子树也分别为二叉搜索树

根据其特性，我们实现二叉搜索树还是应该先构造一个节点类：

class Node { 
  constructor(data) { 
    this.left = null
    this.right = null
    this.value = data
  } 
}

接着按照惯例，我们实现二叉搜索树的以下方法：

insertNode：根据一个父节点，插入一个子节点
insert：插入一个新节点
removeNode：根据一个父节点，移除一个子节点
remove：移除一个节点
findMinNode：获取子节点的最小值
searchNode：根据一个父节点，查找子节点
search：查找节点
preOrder：前序遍历
InOrder：中序遍历
PostOrder：后续遍历

insertNode(root, newNode) {
  if (newNode.value < root.value) {
    (!root.left) ? root.left = newNode : this.insertNode(root.left, newNode)
  } else {
    (!root.right) ? root.right = newNode : this.insertNode(root.right, newNode)
  }
}

insert(value) {
    let newNode = new Node(value)
    if (!this.root) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
}

理解这两个方法是理解二叉搜索树的关键，下面的其他方法也就“不在话下”。我们看，insertNode 方法先判断目标父节点和插入节点的值，如果插入节点的值更小，则考虑放到父节点的左边，接着递归调用 his.insertNode(root.left, newNode)；如果插入节点的值更大，以此类推即可。

insert 方法只是多了一步构造 Node 节点实例，接下来区分有无父节点的情况，调用 this.insertNode 方法即可。

 removeNode(root, value) {
    if (!root) {
      return null
    }

    if (value < root.value) {
      root.left = this.removeNode(root.left, value)
      return root
    } else if (value > root.value) {
      root.right = tis.removeNode(root.right, value)
      return root
    } else {
      // 找到了需要删除的节点 
      // 如果当前 root 节点无左右子节点
      if (!root.left && !root.right) {
        root = null
        return root
      }

      // 只有左节点
      if (root.left && !root.right) {
        root = root.left
        return root
      } 
      // 只有右节点
      else if (root.right) {
        root = root.right
        return root
      }

      // 有左右两个子节点
      let minRight = this.findMinNode(root.right)
      root.value = minRight.value
      root.right = this.removeNode(root.right, minRight.value)
      return root
    }
  }

remove(value) {
    if (this.root) {
      this.removeNode(this.root, value)
    }
}

上述代码不难理解，可能最需要读者思考的就是：

// 有左右两个子节点
let minRight = this.findMinNode(root.right)
root.value = minRight.value
root.right = this.removeNode(root.right, minRight.value)
return root

我来特殊说明一下：当需要删除的节点含有左右两个子节点时，因为我们要把当前节点删除，就需要找到合适的“补位”节点，这个“补位”节点一定在该目标节点的右侧树当中，因为这样才能保证“补位”节点的值一定大于该目标节点的左侧树所有节点，而该目标节点的左侧树不需要调整；同时为了保证“补位”节点的值一定要小于该目标节点的右侧树值，因此要找的“补位”节点其实就是该目标节点的右侧树当中最小的那个节点。

这个过程我们借助 this.findMinNode 方法实现：

findMinNode(root) {
    if (!root.left) {
      return root
    } else {
      return this.findMinNode(root.left)
    }
}

该方法不断递归，直到找到最左叶子节点即可。

查找方法：

searchNode(root, value) {
    if (!root) {
      return null
    }

    if (value < root.value) {
      return this.searchNode(root.left, value)
    } else if (value > root.value) {
      return this.searchNode(root.right, value)
    }

    return root
}

search(value) {
    if (!this.root) {
      return false
    }
    return Boolean(this.searchNode(this.root, value))
}

这也比较简单，其实就是对递归的运用。最能体现递归简便优势的其实是对于树的遍历：

前序遍历：

preOrder(root) {
    if (root) {
      console.log(root.value)
      this.preOrder(root.left)
      this.preOrder(root.right)
    }
}

中序遍历：

inOrder(root) {
    if (root) {
      this.inOrder(root.left)
      console.log(root.value)
      this.inOrder(root.right)
    }
}

后序遍历：

postOrder(root) {
    if (root) {
      this.postOrder(root.left)
      this.postOrder(root.right)
      console.log(root.value)
    }
}

前后中序遍历其实就在于 console.log(root.value) 方法执行的位置。

字典树

字典树（Trie）是针对特定类型的搜索而优化的树数据结构。典型的例子是 autoComplete，也就是说它适合实现：通过部分值得到完整值的场景。字典树因此也是一种搜索树，我们有时候也叫做前缀树，因为任意一个节点的后代都存在共同的前缀。更多基础概念请读者先做了解。我们总结一下它的特点：

字典树能做到高效查询和插入，时间复杂度为 O(k)，k 为字符串长度
但是如果大量字符串没有共同前缀，那就很耗内存，读者可以想象一下最极端的情况，所有单词都没有共同前缀时，这颗字典树是什么样子
字典树的核心就是减少没必要的字符比较，使查询高效率，也就是说用空间换时间，再利用共同前缀来提高查询效率

除了我们刚刚提到的 autoComplete 自动填充的情况，字典树还有很多其他应用场景：

搜索
输入法选项
分类
IP 地址检索
电话号码检索

字典树的实现和遍历

字典树的实现也不复杂，我们慢慢一步步来，首先实现一个字典树上的节点：

class PrefixTreeNode {
  constructor(value) {
    // 存储子节点
    this.children = {}
    this.isEnd = null
    this.value = value
  }
}

一个字典树继承 PrefixTreeNode 类：

class PrefixTree extends PrefixTreeNode {
  constructor() {
    super(null)
  }
}

我们实现方法：

addWord：创建一个字典树节点
predictWord：给定一个字符串，返回字典树中以该字符串开头的所有单词

addWord 实现：

addWord(str) {
    const addWordHelper = (node, str) => {
          // 当前 node 不含当前 str 开头的目标
        if (!node.children[str[0]]) {
            // 以当前 str 开头的第一个字母，创建一个 PrefixTreeNode 实例
            node.children[str[0]] = new PrefixTreeNode(str[0])
            if (str.length === 1) {
                node.children[str[0]].isEnd = true
            } 
            else if (str.length > 1) {
                addWordHelper(node.children[str[0]], str.slice(1))
            }
        }
    }
    addWordHelper(this, str)
}

predictWord 实现：

predictWord(str) {
    let getRemainingTree = function(str, tree) {
      let node = tree
      while (str) {
        node = node.children[str[0]]
        str = str.substr(1)
      }
      return node
    }

    // 该数组维护所有以 str 开头的单词
    let allWords = []

    let allWordsHelper = function(stringSoFar, tree) {
      for (let k in tree.children) {
        const child = tree.children[k]
        let newString = stringSoFar + child.value
        if (child.endWord) {
          allWords.push(newString)
        }
        allWordsHelper(newString, child)
      }
    }

    let remainingTree = getRemainingTree(str, this)

    if (remainingTree) {
      allWordsHelper(str, remainingTree)
    }

    return allWords
}

图

图是由具有边的节点集合组成的数据结构，图可以是定向的或不定向的。因此图可以分为好多种类，这里不一一讲解，主要看图的应用场景：

LBS 地图服务以及 GPS 系统
社交媒体网站的用户关系图
前端工程化中的开发依赖图
搜索算法使用图，保证搜索结果的相关性
寻找降低运输和交付货物和服务成本的最佳途径

图也是应用最广泛的数据结构之一，真实场景中处处有图。更多概念还是需要读者先进行了解，尤其是图的几种基本元素：

节点 Node
边 Edge
|V| 图中顶点（节点）的总数
|E| 图中的连接总数（边）

图的实现和遍历

这里我们主要实现一个有向图，Graph 类：

class Graph {
  constructor() {
    this.AdjList = new Map()
  }
}

使用 Map 数据结构表述图中顶点关系。

实现方法：

添加顶点：addVertex
添加边：addEdge
打印图：print
广度优先算法遍历
深度优先算法

addVertex 方法：

addVertex(vertex) {
  if (!this.AdjList.has(vertex)) {
    this.AdjList.set(vertex, [])
  } else {
    throw 'vertex already exist!'
  }
}

创建顶点：

let graph = new Graph();
graph.addVertex('A')
graph.addVertex('B')
graph.addVertex('C')
graph.addVertex('D')

其中 A、B、C、D 顶点都对应一个数组：

  'A' => [],
  'B' => [],
  'C' => [],
  'D' => []

该数组将用来存储边。我们设计图预计得到如下关系：

Map {
  'A' => ['B', 'C', 'D'],
  'B' => [],
  'C' => ['B'],
  'D' => ['C']
}

根据此描述，其实已经可以把图画出来了。addEdge 因此需要两个参数：一个是顶点，一个是连接对象 Node：

 addEdge(vertex, node) {
    if (this.AdjList.has(vertex)) {
      if (this.AdjList.has(node)){
        let arr = this.AdjList.get(vertex)
        if(!arr.includes(node)){
          arr.push(node)
        }
      }else {
        throw `Can't add non-existing vertex ->'${node}'`
      }
    } else {
      throw `You should add '${vertex}' first`
    }
}

理清楚数据关系，我们就可以打印图了，其实就是一个很简单的 for...of 循环：

print() {
  for (let [key, value] of this.AdjList) {
    console.log(key, value)
  }
}

剩下的内容就是遍历图了。

广度优先算法（BFS），是一种利用队列实现的搜索算法。对于图，其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。换成算法语言，就是从起点出发，对于每次出队列的点，都要遍历其四周的点。

因此 BFS 的实现步骤：

起始节点作为起始，并初始化一个空对象：visited
初始化一个空数组，该数组将模拟一个队列
将起始节点标记为已访问
将起始节点放入队列中
循环直到队列为空

实现：

createVisitedObject() {
  let map = {}
  for(let key of this.AdjList.keys()) {
    arr[key] = false
  }
  return map
}

bfs(initialNode) {
  // 创建一个已访问节点的 map
  let visited = this.createVisitedObject()
  // 模拟一个队列
  let queue = []

  // 第一个节点已访问
  visited[initialNode] = true
  // 第一个节点入队列
  queue.push(initialNode)

  while(queue.length) {
    let current = queue.shift()
    console.log(current)

     // 获得该节点的其他节点关系
    let arr = this.AdjList.get(current)

    for (let elem of arr) {
      // 如果当前节点没有访问过
      if (!visited[elem]) {
        visited[elem] = true
        q.push(elem)
      }
    }
  }
}

那么对于深度优先搜索算法（DFS），我把它总结为：“不撞南墙不回头”，从起点出发，先把一个方向的点都遍历完才会改变方向。换成程序语言就是：“DFS 是利用递归实现的搜索算法”。

因此 DFS 过程：

起始节点作为起始，创建访问对象
调用辅助函数递归起始节点

实现代码：

createVisitedObject() {
  let map = {}
  for (let key of this.AdjList.keys()) {
    arr[key] = false
  }
  return map
}

 dfs(initialNode) {
    let visited = this.createVisitedObject()
    this.dfsHelper(initialNode, visited)
  }

  dfsHelper(node, visited) {
    visited[node] = true
    console.log(node)

    let arr = this.AdjList.get(node)

    for (let elem of arr) {
      if (!visited[elem]) {
        this.dfsHelper(elem, visited)
      }
    }
  }
}

BFS 的重点在于队列，而 DFS 的重点在于递归，这是它们的本质区别。

图在前端中的应用

图其实在前端中应用不算特别多，但绝对还是不容忽视的一部分。这里我举一个我现实中应用的例子——循环图。

在前端工程化发展的今天，理清项目中的依赖关系：比如查找项目中的循环依赖，可视化依赖都是图的应用，有助于开发者在宏观上把控工程化项目。在我们的项目中，我借助 mermaidj 画图工具，实现了项目依赖的完全可视化。并借助 npm script 来生成图片结果，相关 script 脚本：

yarn graph

脚本：

import glob from 'glob'
import readJSON from 'XXX/utils/readJSON'

const pkgs = glob.sync('packages/*/package.json').map(readJSON)

const deps = {}

for (const pkg of pkgs) {
  deps[pkg.name] = Object.keys(pkg.dependencies || []).filter(dep =>
    // ...
  )
}

const graph = { code: '', mermaid: { theme: 'default' } }

graph.code += 'graph TD;'
for (const name in deps) {
  for (const dep of deps[name]) {
    graph.code += `${name}-->${dep};`
  }
}

const base64 = Buffer.from(JSON.stringify(graph)).toString('base64')

/* eslint-disable-next-line */
console.log(
  `Open in browser: https://mermaidjs.github.io/mermaid-live-editor/#/edit/${base64}`
)

上述代码，我首先获取到 packages/*/package.json 中声明的所有依赖，然后对依赖进行必要性过滤之后，维护到 deps 对象当中，按照 mermaid 需求，将 monorepo 项目中的每一个子项目名和依赖按照 → 的间隔维护为 graph.code，最后通过生成 base64 交给 mermaid 进行绘图，绘图过程会根据约定（→ 的标记），成生可视化的依赖图。

最终效果：

那么 mermaid 是如何对图进行绘制的呢？了解了课程前面实现图的代码，我们再看 mermaid 绘制图的部分源码实现：

export const addVertices = function (vert, g, svgId) {
  const svg = d3.select(`[id="${svgId}"]`)
  const keys = Object.keys(vert)

  const styleFromStyleArr = function (styleStr, arr) {
    // Create a compound style definition from the style definitions found for the node in the graph definition
    for (let i = 0; i < arr.length; i++) {
      if (typeof arr[i] !== 'undefined') {
        styleStr = styleStr + arr[i] + ';'
      }
    }

    return styleStr
  }

  // Iterate through each item in the vertex object (containing all the vertices found) in the graph definition
  keys.forEach(function (id) {
    const vertex = vert[id]

    /**
     * Variable for storing the classes for the vertex
     * @type {string}
     */
    let classStr = ''
    if (vertex.classes.length > 0) {
      classStr = vertex.classes.join(' ')
    }

    /**
     * Variable for storing the extracted style for the vertex
     * @type {string}
     */
    let style = ''
    // Create a compound style definition from the style definitions found for the node in the graph definition
    style = styleFromStyleArr(style, vertex.styles)

    // Use vertex id as text in the box if no text is provided by the graph definition
    let vertexText = vertex.text !== undefined ? vertex.text : vertex.id

    // We create a SVG label, either by delegating to addHtmlLabel or manually
    let vertexNode
    if (conf.htmlLabels) {
      // TODO: addHtmlLabel accepts a labelStyle. Do we possibly have that?
      const node = { label: vertexText.replace(/fa[lrsb]?:fa-[\w-]+/g, s => `<i class='${s.replace(':', ' ')}'></i>`) }
      vertexNode = addHtmlLabel(svg, node).node()
      vertexNode.parentNode.removeChild(vertexNode)
    } else {
      const svgLabel = document.createElementNS('http://www.w3.org/2000/svg', 'text')

      const rows = vertexText.split(/<br[/]{0,1}>/)

      for (let j = 0; j < rows.length; j++) {
        const tspan = document.createElementNS('http://www.w3.org/2000/svg', 'tspan')
        tspan.setAttributeNS('http://www.w3.org/XML/1998/namespace', 'xml:space', 'preserve')
        tspan.setAttribute('dy', '1em')
        tspan.setAttribute('x', '1')
        tspan.textContent = rows[j]
        svgLabel.appendChild(tspan)
      }
      vertexNode = svgLabel
    }

    // If the node has a link, we wrap it in a SVG link
    if (vertex.link) {
      const link = document.createElementNS('http://www.w3.org/2000/svg', 'a')
      link.setAttributeNS('http://www.w3.org/2000/svg', 'href', vertex.link)
      link.setAttributeNS('http://www.w3.org/2000/svg', 'rel', 'noopener')
      link.appendChild(vertexNode)
      vertexNode = link
    }

    let radious = 0
    let _shape = ''
    // Set the shape based parameters
    switch (vertex.type) {
      case 'round':
        radious = 5
        _shape = 'rect'
        break
      case 'square':
        _shape = 'rect'
        break
      case 'diamond':
        _shape = 'question'
        break
      case 'odd':
        _shape = 'rect_left_inv_arrow'
        break
      case 'lean_right':
        _shape = 'lean_right'
        break
      case 'lean_left':
        _shape = 'lean_left'
        break
      case 'trapezoid':
        _shape = 'trapezoid'
        break
      case 'inv_trapezoid':
        _shape = 'inv_trapezoid'
        break
      case 'odd_right':
        _shape = 'rect_left_inv_arrow'
        break
      case 'circle':
        _shape = 'circle'
        break
      case 'ellipse':
        _shape = 'ellipse'
        break
      case 'group':
        _shape = 'rect'
        break
      default:
        _shape = 'rect'
    }
    // Add the node
    g.setNode(vertex.id, { labelType: 'svg', shape: _shape, label: vertexNode, rx: radious, ry: radious, 'class': classStr, style: style, id: vertex.id })
  })
}

/**
 * Add edges to graph based on parsed graph defninition
 * @param {Object} edges The edges to add to the graph
 * @param {Object} g The graph object
 */
export const addEdges = function (edges, g) {
  let cnt = 0

  let defaultStyle
  if (typeof edges.defaultStyle !== 'undefined') {
    defaultStyle = edges.defaultStyle.toString().replace(/,/g, ';')
  }

  edges.forEach(function (edge) {
    cnt++
    const edgeData = {}

    // Set link type for rendering
    if (edge.type === 'arrow_open') {
      edgeData.arrowhead = 'none'
    } else {
      edgeData.arrowhead = 'normal'
    }

    let style = ''
    if (typeof edge.style !== 'undefined') {
      edge.style.forEach(function (s) {
        style = style + s + ';'
      })
    } else {
      switch (edge.stroke) {
        case 'normal':
          style = 'fill:none'
          if (typeof defaultStyle !== 'undefined') {
            style = defaultStyle
          }
          break
        case 'dotted':
          style = 'stroke: #333; fill:none;stroke-width:2px;stroke-dasharray:3;'
          break
        case 'thick':
          style = 'stroke: #333; stroke-width: 3.5px;fill:none'
          break
      }
    }
    edgeData.style = style

    if (typeof edge.interpolate !== 'undefined') {
      edgeData.curve = interpolateToCurve(edge.interpolate, d3.curveLinear)
    } else if (typeof edges.defaultInterpolate !== 'undefined') {
      edgeData.curve = interpolateToCurve(edges.defaultInterpolate, d3.curveLinear)
    } else {
      edgeData.curve = interpolateToCurve(conf.curve, d3.curveLinear)
    }

    if (typeof edge.text === 'undefined') {
      if (typeof edge.style !== 'undefined') {