Note.Markdown MachineLearning Algorithm Skill Tool Other From Easy On, Just Do It

Graph 图论 since 2013-15-15

  1. 基本概念
    • 顶点 Vertext, 边 Edge
    • 有向 Directed, 邻接 Adjacent, 圈 cycle, 无圈 acyclic
    • 有向无环图 DAG
    • 连通关系
      • 无向图任意两个顶点间存在路径，则为联通的
      • 有向图任意两个顶点间存在路径，则为强联通
      • 有向图去掉方向后是联通的，则称为弱联通的
      • 无向图中去掉任一条边还是联通的，则成为双联通
    • 完全图 Complete Graph: 任意两个顶点间存在边
  2. 图的表示
    • 邻接矩阵(Adjacent Matrix) 空间复杂度O( V ^2 ) 适用于稠密图
    • 邻接表(Ajacent List) 空间复杂度O( E + V ) 适用于稀疏图，实际中常见
  3. 拓扑排序
    • 对有向无环图的顶点的一种排序
    • 基本方法，每次从图中取出入度为0的顶点v排序队列中,删除v及其边，不断重复该操作直到图为空
    • 偏序 vs 全序
  4. 最短路径算法
    • 单源最短路径问题
      • 无权最短路径问题：从S开始，广度优先遍历图，每个节点深度即为最短路径长度
      • 带权最短路径问题：Dijkstra(贪婪)算法，初始化访问集合S={s0}，每次从S集合的所有邻接点中选取一个距s0最短的加入S，直到所有点都在S中
        • 如果权重含有负数(s0->s1=2;s0->s2=1;s1->s2=-3)，普通的Dijkstra就挂了，改进：
          1. 将S视为一个队列，初始S0入队
          2. Si出队，更新Si邻接到的点Sj距S0的距离，如果小于Sj的当前值，将Si再次入队
          3. 重复步骤2,知道队列为空
        • 如果图中不含还有环，可以改进Dijkstra算法: 关键路径分析
          1. 不含有环，其实就是一个工序流程图，常见的是计算最早完成时间，或关键路径
          2. 手工算从后往前；写程序从前往后，广度优先遍历
    • 所有点之间的最短路径问题
      • 进行 V 次Dijkstra算法
      • Floyd算法 TODO
  5. 最大流问题
    • 有向图G，s是出发点，t是结束点，每条边 Cvw 表示v节点到w节点的最大流量，最大流问题就是确定s到t的最大流量
    • TODO
  6. 最小生成树
    • 在保证连通的前提下，去掉无向连通图中的多余边，使权重最小
    • Prime算法：和Dijkstra算法类似，适用于稠密图
      1. 初始话访问集合S={s0}
      2. 每次从S集合的所有邻接点中找一个距离S最短的加入S
      3. 重复2，直到所有点都在S中
    • Kruskal算法：也很贪婪，适用于稀疏图
      1. 将所有边放入优先队列中(小根堆)，初始化连通集合S为空
      2. 最小边出队，两个顶点不全在S中的情况下，将顶点加入S
      3. 重复步骤2，直到所有边在S中
  7. 深度优先搜索(DFS)
    • 对二叉树先序遍历的推广
    • 判断无向图是否连通(从某节点出发，DFS可以遍历到所有节点，则无向图连通)
    • 判断无向图是否双连通(TODO)
    • 判断无向图是否存在欧拉回路(欧拉回路问题的解决标志着图论的诞生)
      • 欧拉回路: 从某点出发，一次性走完所有边，每条边只走一次
      • 最终回到出发点的欧拉回路问题的充要条件: 连通图且每个顶点的度为偶数
      • 最终不回到出发点的‘欧拉回路’称为欧拉环游，当且仅当连通图中有且仅有两个顶点的度为奇数，并且从度为奇数的点出发
TOP