概念

树的数据结构用来表示层级关系。
图的数据结构用来表示网络关系。

图的表示

我们需要研究的本质还是节点和节点间的关系，所以当一种表述方式能够说清楚这样的关系，它就是一种好的表示。常见的表示方法有：对象、邻接表、邻接矩阵（二维数组）。

  • 对象这种形式将节点抽象成node对象、边抽象成edge对象，这样的表示常见于可视化工具库中，比如AntV、D3.js:
  • 邻接表相较上面的对象的方法稍微抽象点，可以理解是用Map在对象和其关系之间做了一个映射。
  • 而最抽象的莫过于邻接矩阵了，在邻接矩阵中，没有体现具体节点，而节点的内涵隐式的包含在数组的下标之中。所以，这个矩阵（二维数组）展示的就是某节点和另一个节点是否存在边。这种表示方法虽然抽象，但是对于计算机而讲，就可以应用线性代数中矩阵的很多性质，相应的快速做出变换。

用最简单的图来举例说下我们的几种表示方法吧：
（如果我们现在有一个关系是这样的：节点有两个：1，2，其关系是：1->2）
用Object最直白的表示：

  1. const graph = {
  2.   nodes:[
  3.     {id: 1}, 
  4.     {id: 2}
  5.   ],
  6.   edges:[
  7.     { 
  8.       source: 1 ,
  9.       target: 2
  10.     }
  11.   ]
  12. }

用邻接表来表示：

  1. const gTable = {
  2.   1: [2],
  3.   2: []
  4. }

用邻接矩阵来表示：

  1. const gMatrix = [
  2.   [0, 1], 
  3.   [0, 0]
  4. ];

不过问题来了，看上去似乎object可以表述更多的信息，比如扩展下：

  1. const graph = {
  2.   nodes:[
  3.     {id: 1, name: 'lin7', gender: 'female'}, 
  4.     {id: 2, name: 'cjj', gender: 'male'}
  5.   ],
  6.   edges:[
  7.     { 
  8.       source: 1 ,
  9.       target: 2,
  10.       isInLove:true,
  11.       when:'at frist sight' 
  12.     }
  13.   ]
  14. }

这样我们表述了更多的信息，那么如果是这样的信息，邻接矩阵怎么做呢？

  1. const gMatrix = [
  2.   [
  3.     0, 
  4.     { 
  5.       isInLove:true,
  6.       when:'at frist sight' 
  7.     }
  8.   ], 
  9.   [0, 0]
  10. ];

邻接矩阵并不关心节点，或者说节点信息在另外的地方维护，我们通过gMatrix就知道，存在第一个节点指向第二个节点的边，那么具体第一个节点和第二个节点是谁？那其实就是你说是谁就可以是谁。
那么邻接表这种方式其实是一个点边映射的Map，那么，当信息复杂需要做映射的时候，我们用一个WeakMap就能说的清楚。

遍历

遍历是最基本和最重要的方法了。
对于图，基本的遍历和树一样，也分为深度、广度优先（DFS & BFS）。
不过图有一点需要格外注意的是，在遍历过程中要防止路径成环，比如,可能出现这样的路径 A -> B -> C -> D -> B … 这种情况需要避免，否则程序奔溃，调用栈溢出了。怎么避免？用Set记录下遍历过的节点就好。
同样的DFS可以借助递归或者栈来实现。BFS需要借助队列实现。

题目

LeetCode 133:克隆图

133. 克隆图
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
class Node {
public int val;
public List neighbors;
}
_
这道题是让我们深拷贝题目给出的数据结构。其实差不多是一道遍历题，但是按照题目的数据结构，我们的边关系也需要深拷贝，这点是这个题目的点。

  1. /**
  2.  * // Definition for a Node.
  3.  * function Node(val, neighbors) {
  4.  *    this.val = val === undefined ? 0 : val;
  5.  *    this.neighbors = neighbors === undefined ? [] : neighbors;
  6.  * };
  7.  */
  9. /**
  10.  * @param {Node} node
  11.  * @return {Node}
  12.  */
  13. var cloneGraph = function(node) {
  14.     if(!node) return;
  16.     // 存放node和其备份的Map
  17.     const nodeMapToCopy = new Map();
  18.     const dfs = (n) => {
  19.         const { val, neighbors } = n;
  20.         const newNode = new Node(val);
  21.         // 把克隆体放入map
  22.         nodeMapToCopy.set(n, newNode);
  23.         (neighbors || []).forEach(ngb => {
  24.             if(!nodeMapToCopy.has(ngb)){
  25.                 dfs(ngb);
  26.             }
  27.             // 这时候一定存在nodeMapToCopy.get(ngb)
  28.             newNode.neighbors.push(nodeMapToCopy.get(ngb));
  29.         })
  30.     }
  31.     dfs(node);
  33.     return nodeMapToCopy.get(node);
  35. };

LeetCode 65: 有效数字

65. 有效数字
验证给定的字符串是否可以解释为十进制数字。
例如:
“0” => true
“ 0.1 “ => true
“abc” => false
“1 a” => false
“2e10” => true
“ -90e3 “ => true
“ 1e” => false
“e3” => false
“ 6e-1” => true
“ 99e2.5 “ => false
“53.5e93” => true
“ —6 “ => false
“-+3” => false
“95a54e53” => false

这个题本来是个字符串题目，不用正则，一个个字符校验的话，用状态机图的思路解决，就和图扯上关系了。
下面是一副状态机图，这个状态机的节点表述当前状态，状态间的转化用边来表示。这个状态机的入口是0状态，成功的出口是：3、5、6状态。
每当新遇到一个字符，在当前状态的基础上根据边规定的条件，转化成下一种状态。如果最终能到成功状态，就返回成功。
image.png_

  1. /**
  2.  * @param {string} s
  3.  * @return {boolean}
  4.  */
  5. var isNumber = function (s) {
  6.     // 学习别人的状态机图解法
  8.     // blank 表示空格
  9.     // sign 表示正负号
  10.     // digit 表示数字
  11.     // . 就是小数点
  12.     // e 就是 e
  14.     // 邻接表表示状态机
  15.     const graph = {
  16.         0: { "blank": 0, "sign": 1, ".": 2, "digit": 6 },
  17.         1: { "digit": 6, ".": 2 },
  18.         2: { "digit": 3 },
  19.         3: { "digit": 3, "e": 4 },
  20.         4: { "digit": 5, "sign": 7 },
  21.         5: { "digit": 5 },
  22.         6: { "digit": 6, ".": 3, "e": 4 },
  23.         7: { "digit": 5 },
  24.     };
  26.     let state = 0;
  27.     let char;
  28.     s = s.trim();
  29.     for (char of s) {
  30.         if (char >= "0" && char <= "9") {
  31.             char = "digit";
  32.         } else if (char == " ") {
  33.             char = "blank";
  34.         } else if (char == "+" || char == "-") {
  35.             char = "sign";
  36.         }
  37.         state = graph[state][char];
  38.         if (state == undefined) {
  39.             return false;
  40.         }
  41.     }
  42.     // 3 是小数，5是科学计数法，6是整数
  43.     return state == 3 || state == 5 || state == 6;
  44. };

上面的代码中，状态机图的表示用邻接表表示法。