数据结构复习（JavaScript）

一、二叉树

1.1 二叉树遍历

中序遍历、前序遍历、后序遍历(根据根节点遍历次序划分)
中序遍历：

//递归:
var inorderTraversal = function (root, array = []) {
  if (root) {
    inorderTraversal(root.left, array);
    array.push(root.val);
    inorderTraversal(root.right, array);
  }
  return array;
};

//非递归
var inorderTraversal = function (root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current || stack.length > 0) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.val);
    current = current.right;
  }
  return result;
};

1.2 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。

function reConstructBinaryTree(pre, vin) {
  // write code here
  if (pre.length === 0 || vin.length === 0) {
    return null;
  }
  // 前序第一个是根节点，也是中序左右子树的分割点
  const index = vin.indexOf(pre[0]),
    left = vin.slice(0, index),
    right = vin.slice(index + 1);
  return {
    val: pre[0],
    // 递归左右子树的前序、中序
    left: reConstructBinaryTree(pre.slice(1, index + 1), left),
    right: reConstructBinaryTree(pre.slice(index + 1), right)
  };
}

1.3 二叉树的深度

//最大深度
function TreeDepth(pRoot) {
  return !pRoot ? 0 : Math.max(TreeDepth(pRoot.left), TreeDepth(pRoot.right)) + 1
}

//最小深度
var minDepth = function (root) {
  if (!root) {
    return 0;
  }
  if (!root.left) {
    return 1 + minDepth(root.right);
  }
  if (!root.right) {
    return 1 + minDepth(root.left);
  }
  return Math.min(minDepth(root.left), minDepth(root.right)) + 1
};

1.4 平衡二叉树

判断是否为平衡二叉树

function IsBalanced_Solution(pRoot) {
  return balanced(pRoot) != -1;
}

function balanced(node) {
  if (!node) {
    return 0;
  }
  const left = balanced(node.left);
  const right = balanced(node.right);
  if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
    return -1;
  }
  return Math.max(left, right) + 1;
}

1.5 二叉搜索树

正常情况下二叉搜索树时间复杂度为O(log2n), 极端情况下为O(n)故需要AVL树。
二叉搜索树的第k小的节点，即考察中序遍历。

//递归实现
function KthNode(pRoot, k) {
  const arr = [];
  loopThrough(pRoot, arr);
  if (k > 0 && k <= arr.length) {
    return arr[k - 1];
  }
  return null;
}

function loopThrough(node, arr) {
  if (node) {
    loopThrough(node.left, arr);
    arr.push(node);
    loopThrough(node.right, arr);
  }
}

1.6 AVL树

AVL树，也称平衡二叉搜索树，AVL是其发明者姓名简写。AVL树属于树的一种，而且它也是一棵二叉搜索树，不同的是他通过一定机制能保证二叉搜索树的平衡，平衡的二叉搜索树的查询效率更高。

特点

AVL树是一棵二叉搜索树。
AVL树的左右子节点也是AVL树。
AVL树拥有二叉搜索树的所有基本特点。
每个节点的左右子节点的高度之差的绝对值最多为1，即平衡因子为范围为[-1, 1]。

image.png

旋转

image.png

相关代码

/**
 * AVL树节点的构造函数
 * @constructor
 */
function AVLTreeNode(key) {
    this.key = key;
    this.leftChild = null;
    this.rightChild = null;
    this.parent = null;
}

/**
 * AVL树的构造函数。如果没有传有效的keyName，使用data进行比较；否则使用data[keyName]进行比较
 *
 * @param {string} [keyName] - 可选参数。关键码在data中的字段名
 * @constructor
 */
function AVLTree(keyName) {

    this.root = null;

    //这是我们计算当前节点的高度的方法,递归计算
    let getHeight = function (node) {
        // 如果没有那就为0
        if(node === null) {
            return 0;
        } else {
            return Math.max(getHeight(node.leftChild),getHeight(node.rightChild)) + 1;
        }
    };
    //向左的单旋转
    let rotateLL = function (node) {
        let tmp = node.rightChild;
        node.rightChild = tmp.leftChild;
        tmp.leftChild = node;
        return tmp;
    };

    //向右的单旋转
    let rotateRR = function (node) {

        let tmp = node.leftChild;
        node.leftChild = tmp.rightChild;
        tmp.rightChild = node;
        return tmp;
    };

    //先左后右双旋转
    let rotateLR = function (node) {
        node.leftChild = rotateLL(node.leftChild);
        return rotateRR(node);
    };

    //先右后左双旋转
    let rotateRL = function (node) {
        node.rightChild = rotateRR(node.rightChild);
        return rotateLL(node);
    };
    //方法保证 整颗树平衡
    function checkIsBalance(node) {
        if (node == null) {
            return node;
        }
        // 左子树高度比右子树高度大   父节点平衡因子为-2  
        if (getHeight(node.leftChild) - getHeight(node.rightChild) > 1) {
            if (getHeight(node.leftChild.leftChild) >= getHeight(node.leftChild.rightChild)) {
                // 如果左子树的左子树高度大于等于左子树的右子树高度  左子节点为-1和0
                // 直接进行右单旋
                node = rotateRR(node);
            } else {
                //如果左子节点为1，需要先左后右双旋
                node = rotateLR(node);
            }
            // 右子树高度比左子树高度大1以上  父节点平衡因子为2
        } else if (getHeight(node.rightChild) - getHeight(node.leftChild) > 1) {
            if (getHeight(node.rightChild.rightChild) >= getHeight(node.rightChild.leftChild)) {
                // 如果右子树的右子树高度大于等于右子树的左子树高度
                // 直接进行左单旋
                node = rotateLL(node);
            } else {
                // 否则需要右左双旋
                node = rotateRL(node);
            }
        }
        return node;
    }
  //插入方法：
    let insertNode = function(node, newNode){

        if (node == null){
            node = newNode;
            return node;
        } else if (newNode.key < node.key){
         // 在左子树里插入 同搜索二叉树一致
            if (node.leftChild === null){
                node.leftChild = newNode;
                return node;
            } else {
                node.leftChild = insertNode(node.leftChild, newNode);
                //更新整棵树
                node = checkIsBalance(node);
            }
        } else if (newNode.key > node.key){
            //右子树里插入
            if (node.rightChild === null){
                node.rightChild = newNode;
                return node;
            } else {
                node.rightChild = insertNode(node.rightChild, newNode);
                node = checkIsBalance(node);
            }
        }
        return node;
    };

    this.insert = function (data) {
        let newNode = new AVLTreeNode(data);
        this.root = insertNode(this.root, newNode);
    };

    this.delete = function (data) {
        this.root = deleteData(this.root, data);
    };
    //删除制定节点
    function deleteData(node, data) {
        if( node === null){
            return null;
        }
        //如果小于就在左子树中删除
        if(data < node.key){
            node.leftChild =  deleteData(node.leftChild, data);
            node = checkIsBalance(node);

            return node
        }else if(data > node.key){
            node.rightChild = deleteData(node.rightChild, data);
            node = checkIsBalance(node);

            return node
        }else{
            //删除的data等于node.key

            //如果此节点有两个子节点
            if(!!node.leftChild && !!node.rightChild){
                let tempNode = node.rightChild;

                while ( null !== tempNode.leftChild){
                    //找到右子树中最小的节点
                    tempNode = tempNode.leftChild;
                }
                
                //右子树中最小的节点赋值给当前节点
                node.key =  tempNode.key ;
                //删除右子树中最小值的节点
                node.rightChild = deleteData(node.rightChild, tempNode.key);
                node = checkIsBalance(node);

                return node;

            }else {
                //只有一个或者是叶节点
                //叶节点
                if( null === node.leftChild && null === node.rightChild){
                    node = null;
                    return node;
                }
                //只有右
                if( null === node.leftChild){
                    node = node.rightChild;
                    return node;
                }else if( null === node.rightChild){
                    //只有左
                    node = node.leftChild;
                    return node;
                }
            }

        }
    }
    this.print = function () {
        console.log(this.root);
        debugger
    }

}

/**
*打印
*/
const avl = new AVLTree();

const existData = [];
for (let len = 10; len > 0; len--) {
    const data = ~~(100 * Math.random());
    if (-1 === existData.indexOf(data)) {
        existData.push(data);
        avl.insert(data);
    } else {
        len++;
    }
}

existData.forEach(item => avl.insert(item));

console.log('existData:', existData.map(item => item));
avl.print();

const deletedData = [];
for (let len = 3; len > 0; len--) {
    const index = ~~(Math.random() * existData.length);
    deletedData.push(existData[index]);
    avl.delete(existData.splice(index, 1));
}

console.log('deletedData: ', deletedData.map(item => item));

avl.print();
/*
————————————————
版权声明：本文为CSDN博主「Funfction_Zero」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wf00334814/java/article/details/84103036
*/

总结

二叉搜索树的不稳定性，就有可能退化为近似链或链，查询时间复杂度就退化为 O(n)。当 n 很大的时候，性能就大大降低，达不到折半的效果。因此，我们需要一个平衡的二叉搜索树。

平衡二叉树是通过对树节点的左旋和右旋来保证树的平衡性，也就是保证左右子树的高度差不超过 1。
在对树进行左旋和右旋时，有四种形态分别是：左左，左右，右右，右左。因此，平衡二叉树的查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。

1.7 红黑树

虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。

显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树，红黑树具有如下特点：

节点是红色或黑色。
根节点是黑色。
每个叶子节点都是黑色的空节点（NIL节点）。

4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

下图中这棵树，就是一颗典型的红黑树：

image.png

红黑树自平衡的实现

红黑树节点的插入和删除可能会破坏上述红黑树的性质并打破它的平衡，因此需要进行调整从而让红黑树重新恢复平衡；调整分两种方式：旋转以及变色。

旋转又分为左旋转和右旋转两种形式：

左旋：如下图所示以 P 为旋转支点，旋转支点 P 的右子节点 R 变为父节点，其右子节点 R 的左子节点 RL 变为旋转支点 P 的右子节点；左旋之后左子树的节点相对旋转之前要多出一个节点，也就是左子树从右子树借用一个节点；

image.png

/**
 * 左旋示例代码：
 *       P                   R
 *      / \                 / \
 *     L   R     ====>     P  RR
 *        / \             / \
 *       RL RR           L  RL
 * @param node 旋转支点
 */
 rotateLeft(node) {
  // R
  const rchild = node.right;
  // P.right = RL
  node.right = rchild.left;
  // RL.parent = P;
  if (rchild.left) {
    rchild.left.parent = node;
  }
  // R.parent = P.paretn
  rchild.parent = node.parent;
  // 根节点情况，
  if (!node.parent) {
    this.root = rchild;
  } else {
    if (node === node.parent.right) {
      // node 是父节点的右节点，
      node.parent.right = rchild;
    } else {
      // node 是父节点的左节点，
      node.parent.left = rchild;
    }
  }
  // R.left = P
  rchild.left = node;
  // P.parent = R;
  node.parent = rchild;
}

右旋：如下图所示以 R 为旋转支点，旋转支点 R 的左子节点 P 变为父节点，而左子节点 P 的右子节点 RL 变为旋转支点 R 的左子节点；右旋之后右子树的节点相对旋转之前要多出一个节点，也就是右子树从左子树借用一个节点；

image.png

/**
 * 右旋示例代码：
 *       R                 P
 *      / \               / \
 *     P  RR   ====>     L   R
 *   /  \                   / \
 *  L   RL                 RL RR
 * @param node 旋转支点
 */
 rotateRight(node) {
  // P
  const lchild = node.left;
  // R.left = RL ;
  node.left = lchild.right;
  // RL.parent = R
  if (lchild.right) {
    lchild.right.parent = node;
  }
  // P.parent = R.parent;
  lchild.parent = node.parent;
  // 根节点情况，
  if (!lchild.parent) {
    this.root = lchild;
  } else {
    if (node === node.parent.right) {
      // node 是父节点的右节点，
      node.parent.right = lchild;
    } else if (node === node.parent.left) {
      // node 是父节点的左节点，
      node.parent.left = lchild;
    }
  }
  // P.right = R;
  lchild.right = node;
  // R.parent = P;
  node.parent = lchild;
}

变色就是由黑色节点变成红色节点或者红色节点变成黑色节点

image.png

节点插入

具体到实际应用中，红黑树的节点是不能随意旋转和变色的，红黑树的旋转和变色有方式方法，首先需要先找到插入节点的父节点位置，与红黑树查找方式类似。本文以插入的节点为红色为例，当然也可以用黑色节点作为插入节点，但会更复杂。另外本文中所有节点中提的值都指的是 Key ，实际上节点还存在其它属性。

image.png

节点定义：

/**
 * 节点
 */
class Node {
  constructor(key, value, color = COLOR.RED) {
    this.key = key;
    this.value = value;
    this.color = color;

    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

节点插入及插入平衡操作

/**
 * 插入key, value
 */
insert(key, value) {
  if (this.root) {
    // 红黑树为非空场景
    let parent;
    let node = this.root;
    const newNode = new Node(key, value, COLOR.RED);
    // 查找插入位置
    while (node) {
      parent = node;
      if (key === node.key) {
        // 场景二： 插入节点key已存在
        newNode.color = node.color;
        this.update(node, newNode);
        return;
      } else if (key < node.key) {
        node = node.left;
      } else {
        node = node.right;
      }
    }
    newNode.parent = parent;
    if (key < parent.key) {
      parent.left = newNode;
    } else {
      parent.right = newNode;
    }
    this.balanceInsertion(newNode);
  } else {
    // 场景一：红黑树为空树场景
    this.root = new Node(key, value, COLOR.BLACK);
  }
}

// 插入节点平衡修正
balanceInsertion(node) {
  // 场景三：插入节点的父节点为黑色节点，无需修正
  while (node.parent != null && node.parent.color === COLOR.RED) {
    let uncle = null;
    // 父节点是祖父节点左节点
    if (node.parent === node.parent.parent.left) {
      uncle = node.parent.parent.right;
      // 场景四：叔叔节点为红色
      if (uncle != null && uncle.color === COLOR.RED) {
        // 父节点、叔叔节点变成黑色，祖父节点变成红色，以祖父节点当作需要新节点继续调用修正方法；
        node.parent.color = COLOR.BLACK;
        uncle.color = COLOR.BLACK;
        node.parent.parent.color = COLOR.RED;
        node = node.parent.parent;
        continue;
      }
      // 场景五：叔叔节点为空节点或者是黑色节点；
      // 场景5.2 插入节点是父节点的右节点，先进行左旋转换到场景5.1
      if (node === node.parent.right) {
        // 左旋之后，原插入节点的父节点变成新插入节点；
        node = node.parent;
        this.rotateLeft(node);
      }
      // 场景5.1 插入节点是父节点的左节点；
      // 父节点变成黑色、祖父节点变成红色
      node.parent.color = COLOR.BLACK;
      node.parent.parent.color = COLOR.RED;
      // 对祖父节点右旋
      this.rotateRight(node.parent.parent);
    } else {
      // 父节点是祖父节点右子节点
      uncle = node.parent.parent.left;
      // 场景四：叔叔节点为红色
      if (uncle != null && uncle.color === COLOR.RED) {
        // 父节点、叔叔节点变成黑色，祖父节点变成红色，以祖父节点当作需要新节点继续调用修正方法；
        node.parent.color = COLOR.BLACK;
        uncle.color = COLOR.BLACK;
        node.parent.parent.color = COLOR.RED;
        node = node.parent.parent;
        continue;
      }
      // 场景5.4 插入节点是父节点的左节点，先进行右旋转换到场景5.3
      if (node === node.parent.left) {
        // 右旋之后，原插入节点的父节点变成新插入节点；
        node = node.parent;
        this.rotateRight(node);
      }
      // 场景5.3插入节点是父节点的右节点；
      // 父节点变成黑色、祖父节点变成红色
      node.parent.color = COLOR.BLACK;
      node.parent.parent.color = COLOR.RED;
      // 对祖父节点左旋
      this.rotateLeft(node.parent.parent);
    }
  }
  this.root.color = COLOR.BLACK;
}

红黑树删除

红黑树删除操作包括两部分，一是查找到删除节点，二是删除节点以及删除之后的自平衡。查找节点与二叉树的查找方式一样。而删除操作，当删除节点不存在时，结束本次删除操作；当删除节点存在时，删除节点，然后找到一个节点替换已删除的节点位置，重新连接上已删除节点的父节点与孩子节点。

总结

红黑树最吸引人的是它的所有操作在最差情况下可以保证 O(logN) 的时间复杂度，稳定且高效。例如要在10 万条(2^20)数据中查找一条数据，只需要 20 次的操作就能完成。但这些保证有一个前置条件，就是数据量不大，且数据可以完全放到内存中。在数据量比较大时，因为红黑树的深度比较大造成磁盘 IO 的频繁读写，会导致它的效率低下。

二、链表

2.1 反转链表

//以链表的头部节点为基准节点
//将基准节点的下一个节点挪到头部作为头节点
//当基准节点的next为null，则其已经成为最后一个节点，链表已经反转完成

 var reverseList = function (head) {
      let currentNode = null;
      let headNode = head;
      while (head && head.next) {
        currentNode = head.next;
        head.next = currentNode.next;
        currentNode.next = headNode;
        headNode = currentNode;
      }
      return headNode;
    };

2.2 复杂链表的复制

function Clone(pHead) {
  if (pHead === null) {
    return null;
  }
  cloneNodes(pHead);
  cloneRandom(pHead);
  return reconnetNodes(pHead);
}

function cloneNodes(pHead) {
  var current = pHead;
  while (current) {
    var cloneNode = {
      label: current.label,
      next: current.next
    };
    current.next = cloneNode;
    current = cloneNode.next;
  }
}

function cloneRandom(pHead) {
  var current = pHead;
  while (current) {
    var cloneNode = current.next;
    if (current.random) {
      cloneNode.random = current.random.next;
    } else {
      cloneNode.random = null;
    }
    current = cloneNode.next;
  }
}

function reconnetNodes(pHead) {
  var cloneHead = pHead.next;
  var cloneNode = pHead.next;
  var current = pHead;
  while (current) {
    current.next = cloneNode.next;
    current = cloneNode.next;
    if (current) {
      cloneNode.next = current.next;
      cloneNode = current.next;
    } else {
      cloneNode.next = null;
    }
  }
  return cloneHead;
}

2.3 合并链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

function Merge(pHead1, pHead2) {
  if (!pHead1) {
    return pHead2;
  }
  if (!pHead2) {
    return pHead1;
  }
  let head;
  if (pHead1.val < pHead2.val) {
    head = pHead1;
    head.next = Merge(pHead1.next, pHead2);
  } else {
    head = pHead2;
    head.next = Merge(pHead1, pHead2.next);
  }
  return head;
}

2.4 链表环的入口节点

function EntryNodeOfLoop(pHead) {
  if (!pHead || !pHead.next) {
    return null;
  }
  let P1 = pHead.next;
  let P2 = pHead.next.next;
  // 1.判断是否有环
  while (P1 != P2) {
    if (P2 === null || P2.next === null) {
      return null;
    }
    P1 = P1.next;
    P2 = P2.next.next;
  }
  // 2.获取环的长度
  let temp = P1;
  let length = 1;
  P1 = P1.next;
  while (temp != P1) {
    P1 = P1.next;
    length++;
  }
  // 3.找公共节点
  P1 = P2 = pHead;
  while (length-- > 0) {
    P2 = P2.next;
  }
  while (P1 != P2) {
    P1 = P1.next;
    P2 = P2.next;
  }
  return P1;
}

三、栈、队列

栈：先进后出
队列：先进先出

四、哈希表|散列表

哈希的基本原理是将给定的键值转换为偏移地址来检索记录。

哈希表在不出现哈希碰撞的基础下时间复杂度是O(1), 出现哈希冲突解决方式有链式存储、二度哈希

键转换为地址是通过一种关系（公式）来完成的，这就是哈希（散列）函数。

虽然哈希表是一种有效的搜索技术，但是它还有些缺点。两个不同的关键字，由于哈希函数值相同，因而被映射到同一表位置上。该现象称为冲突。发生冲突的两个关键字称为该哈希函数的同义词。

image

如何设计哈希函数以及如何避免冲突就是哈希表的常见问题。好的哈希函数的选择有两条标准：

1. 简单并且能够快速计算
1. 能够在址空间中获取键的均匀人分布

五、堆

堆的底层实际上是一棵完全二叉树，可以用数组实现

每个的节点元素值不小于其子节点 - 最大堆
每个的节点元素值不大于其子节点 - 最小堆

堆在处理某些特殊场景时可以大大降低代码的时间复杂度，例如在庞大的数据中找到最大的几个数或者最小的几个数，可以借助堆来完成这个过程。

5.1 堆的构建

大顶堆

function ajustMaxHeap(array, index, length) {
  for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {
    if (i + 1 < length && array[i + 1] > array[i]) {
      i++;
    }
    if (array[index] >= [array[i]]) {
      break;
    } else {
      [array[index], array[i]] = [array[i], array[index]];
      index = i;
    }
  }
}

function createMaxHeap(arr, length) {
  for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
    ajustMaxHeap(arr, i, length);
  }
  return arr;
}

小顶堆

function ajustMinHeap(array, index, length) {
  for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {
    if (i + 1 < length && array[i + 1] < array[i]) {
      i++;
    }
    if (array[index] < [array[i]]) {
      break;
    } else {
      [array[index], array[i]] = [array[i], array[index]];
      index = i;
    }
  }
}

function createMinHeap(arr, length) {
  for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
    ajustMinHeap(arr, i, length);
  }
  return arr;
}

5.2 堆的插入

/*
由于堆属于优先队列，只能从末尾添加
添加后有可能破坏堆的结构，需要从下到上进行调整
如果元素小于父元素，上浮
*/
function minHeapAdd(array = [], element) {
  array.push(element);
  if (array.length > 1) {
    let index = array.length - 1;
    let target = Math.floor((index - 1) / 2);
    while (target >= 0) { array[target]);
      if (array[index] < array[target]) {
        [array[index], array[target]] = [array[target], array[index]]
        index = target;
        target = Math.floor((index - 1) / 2);
      } else {
        break;
      }
    }
  }
  return array;
}

5.3 堆的移除

/*
由于堆属于优先队列，只能从头部移除
移除头部后，使用末尾元素填充头部，开始头部下沉操作
以小顶堆为例：
*/
function minHeapPop(array = []) {
  let result = null;
  if (array.length > 1) {
    result = array[0];
    array[0] = array.pop();
    ajustMinHeap(array, 0, array.length);
  } else if (array.length === 1) {
    return array.pop();
  }
  return result;
}

六、图

6.1什么是图?

图（graph），它表明了物件与物件之间的“多对多”的一种复杂关系。图包含了两个基本元素：顶点（vertex, 简称V）和边（edge, 简称E）。

有向图与无向图

如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，从一个顶点出发的边数称为该点的出度，而指向一个顶点的边数称为该点的入度。相反，边没有方向的图称为无向图。

有权图与无权图

如果图中的边有各自的权重，得到的图是有权图。比如地铁路线图，连接两站的边的权重可以是距离，也可以是价格，或者其他。反之，如果图的边没有权重，或者权重都一样（即没有区分），称为无权图。

连通图

如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。无向图中的一个极大连通子图称为其的一个连通分量。有向图中，如果对任意两个顶点Vi与Vj都存在i到j以及j到i的路径，则称其为强连通图，对应有强连通分量的概念。

图的存储

常用的存储方式有两种：邻接矩阵和邻接表。

邻接矩阵

image.png

采用一个大小为V*V的矩阵G，对于有权图，Gij可以表示Vi到Vj的边的权重，如果是无权图，则可设为1表示存在边，0表示不存在边。因此邻接矩阵的表示相当的直观，而且对于查找某一条边是否存在、权重多少非常快。但其比较浪费空间，对稠密图（E>>V）来说，会比较适合。

image.png

邻接表

G[N]为指针数组，对应矩阵每行一个链表，只存非零元素。

image.png

6.2 图的遍历

图的遍历最常用的有两种：深度优先搜索（Depth-first Search, DFS）和广度优先搜索（Breadth-First Search, BFS。

深度优先搜索DFS

类似于树的前序遍历，即从一个选定的点出发，选定与其直接相连且未被访问过的点走过去，然后再从这个当前点，找与其直接相连且未被访问过的点访问，每次访问的点都标记为“已访问”，就这么一条道走到黑，直到没法再走为止。没法再走怎么办呢？从当前点退回其“来处”的点，看是否存在与这个点直接相连且未被访问的点。重复上述步骤，直到没有未被访问的点为止。

image.png

广度优先搜索BFS

类似于树的层序遍历，从一个选定的点出发，将与其直接相连的点都收入囊中，然后依次对这些点去收与其直接相连的点。重复到所有点都被访问然后结束。

image.png

6.3 最短路径问题

在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径

这条路径就是两点之间的最短路径（Shortest Path）
第一个顶点为源点（Source）
最后一个顶点为终点（Destination）

问题主要分为：
单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径。
多源最短路径问题：求任意两顶点间的最短路径。

单源最短路径问题

无权图的单源最短路算法，可以借助BFS算法。

image.png

对于有向图而言, 可以借助Dijkstra算法。
Dijkstra算法的核心在于：从起点（或者说源点）开始，将其装进一个“袋子”里，然后不断往这个袋子里搜罗顶点，当顶点收进去后，能保证从源点到该顶点的当前最短路径是确定的。每次收录的顶点是在未收录的集合里寻找最短路径最小的点（即离源点最近的点），然后将与收进去的顶点直接相连的点的最短路径进行更新。

image.png

多源最短路径

image.png

void Floyd()
{
  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
    {
      D[i][j] = G[i][j];
      path[i][j] = -1;
    }
  for (k = 0; k < N; k++)
    for (i = 0; i < N; i++)
      for (j = 0; j < N; j++)
        if (D[i][k] + D[k][j] < D[i][j])
        {
          D[i][j] = D[i][k] + D[k][j];
          path[i][j] = k;
        }
}
// T =O(|V|^3)

参考

http://www.conardli.top/docs/
https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/tree/avl-tree
https://juejin.im/post/5dff59cb6fb9a0163c53ce1d#heading-11
https://zhuanlan.zhihu.com/p/37673101
https://www.icourse163.org/course/ZJU-93001