/learn-algorithms

use javascript language learn algorithms

Primary LanguageJavaScript

算法与数据结构入门

  1. 并查集
  2. 图

并查集

  1. 介绍
  2. 操作
  3. 实现
  4. 优化
  5. 路径压缩
  6. 复杂度

并查集介绍

  1. 并查集是一种树形结构
  2. 并查集是为了高效解决连接问题
    • 判断网络中节点间的连接状态， 网络是个抽象概念，用户之间形成的网络
    • 数学中的集合类实现
  3. 连接问题 和 路径问题
    • 比路径问题要回答的问题少
      • 和二分查找做比较
      • 和select做比较
      • 和堆作比较

并查集的操作

  1. 对于一组数据，主要支持两个操作
    • union(p, q)
    • find(p)
  2. 用来回答一个问题
    • isConnected(p, q)

并查集的实现

  1. 并查集的使用普通数组实现

  2. 并查集的使用parent指针数组实现

    • 将每个元素看作是一个节点， 使用指针指向父亲节点的树， 依然使用数组

并查集的优化

  1. 使用size数组优化
  2. 使用rank数组优化

路径压缩（加快find查找）

  1. 节点p 指向 parent[p] 的 父节点 parent[parent[p]]，每次向上走两步
  2. 使用递归，将每个节点不断向上查找parent[p]， 使得 p 指向根节点parent[p]，使得以parent[p]为根节点的高度为 2;

复杂度分析

时间复杂度： 近乎是O(1)

图

  1. 节点

  2. 边

  3. 应用场景

    1. 交通运输
    2. 社交网络
    3. 互联网
    4. 工作安排
    5. 脑区活动
    6. 程序执行状态

  4. 图的分类

    • 从方向看
      1. 无向图 (是一种特殊的有向图)
      2. 有向图
    • 从权来看
      1. 有权图
      2. 无权图

  5. 图的连通性

  6. 简单图

    1. 自环边
    2. 平行边

  7. 图的表示

    • 邻接矩阵， 适合稠密图(完全图)
    • 领接表， 适合稀疏图

  8. 遍历邻边

    • 相邻节点迭代器

  9. 图的遍历

    • 深度优先遍历， 求图中的连通分量， 寻路
    • 广度优先遍历， 最短路径(无权图)

  10. 无权图的应用

  • ps的魔棒，扫雷，（flood fill算法），连通分量
  • 迷宫生成，迷宫本质是生成一棵树
  • 欧拉路径
  • 哈密尔顿路径
  • 二分图
  • 地图填色