返回

数据结构(八)基于图的其它算法

拓扑排序 Topological Sorting

  1. 当一组数据间存在两两依赖关系,并且数据间不存在循环依赖的关系。如果要对这组数据进行排序,则可以使用拓扑排序
  2. 拓扑排序是基于有向无环图的算法
  3. 需要通过局部顺序来推导出全局顺序的,使用拓扑排序来实现

拓扑排序的实现方式

  1. Kahn 算法

    • 如果 s 先于 t 执行,则添加一条 从 s 指向 t 的边
    • 若某个顶点的入度为 0,说明没有任何一个顶点需要先于此顶点执行,则此顶点可以先执行
    • 在图中找出入度为 0 的顶点,输出并在图中删除此顶点,也就是把这个顶点可达的顶点的入度都 - 1
    • 若输出的顶点个数少于图中的顶点个数,并且图中还存在入度不为 0 的顶点,则说明此图中存在环
  2. DFS 深度优先遍历算法

    • 构造逆邻接表,如果 s 先于 t 执行,则添加一条 从 t 指向 s 的边
    • 递归的处理每个顶点,先输出这个顶点可到达的顶点后,再输入此顶点

Dijkstra 最短路径算法

  1. 单源最短路径算法,即 求一个顶点到另一个顶点的最短路径
  2. Dijkstra 是基于有向有权图
  3. Dijkstra 的时间复杂度为 O(E * logV),E 表示边的个数,V 表示顶点个数

Dijkstra 算法的实现

  1. 使用邻接表(邻接矩阵)来表示有向有权图
    • 每个结点包括起始顶点 s 、结束顶点 t 、权重 w,即 s -> t
  2. 使用一个数组来表示从顶点 s 到此顶点 n 的最小距离
    • 每个结点包括起始顶点 s 、当前顶点 n 、s 到 n 的最小距离 dist
    • 初始起点顶点的 dist 为 0,其余顶点的初始 dist 的值为无限大
  3. 根据 dist 构造一个小顶堆,每次优先获取 dist 最小的顶点
    • 初始 dist 小顶堆只有起始顶点,遍历其余顶点时不断更新 dist 小顶堆
    • dist 小顶堆中存放的是已经遍历过且计算出 dist 的顶点
  4. 使用一个数组来表示此顶点是否已经被遍历过
    • 如果已经遍历过,且发现到达此顶点的更短路径,则更新 dist 的小顶堆
    • 如果没遍历过,将此顶点加入到 dist 的小顶堆中
  5. 使用一个数组来表示最短路径,记录每个顶点的前驱顶点

Dijkstra 的优化

  1. 当在较大的地图上,计算两点之间的最短路径时
    • 如果两点间的距离较近,可以在整个大地图中划分出一个小的区块,这个小区块可以覆盖这两个点,但是区域不会太大
    • 如果两点间的距离较远,可以把两点所在的大区域当作一个点,先计算两个大区域的路线,然后再细化每个阶段的小路线
  2. 计算两点间所用最少时间
    • 将边的权重改为经过这段路所需要的时间
  3. 计算两点之间所经过最少红绿灯
    • 将每条边的权重值改为 1,或者直接使用广度优先搜索算法

Dijkstra 算法的变形和应用

  1. 背景

    • 单词经过翻译系统后,得到单词对应的释义及分数,分数代表翻译的可信程度。将句子中的单词翻译后相加,可以得到整句的翻译分数。希望求得翻译得分的 TOP k
      Dijkstra
      Dijkstra
  2. 实现

    • 回溯算法
      • 穷举所有的排列组合情况,选取得分最高的前 k 个翻译结果
      • 时间复杂度为 O(mn),m 表示每个单词的平均可选翻译个数,n 表示单词数
    • Dijkstra 算法
      • 首先可以得到得分最高的一个组合,基于此组合来进行扩展,将每个单词的翻译分别替换成下一个得分最高的翻译。假设为 a0b0c0,扩展后为:a1b0c0、a0b1c0、a0b0c1
      • 每次从优先级队列(大顶堆)中取出
© Licensed Under CC BY-NC-SA 4.0