2021-06-26图

概念

一种非线性数据结构，比树复杂。

分类

• 有向图
• 无向图
• 带权图

存储

• 邻接矩阵法：

  1. 缺点：浪费存储空间。
  2. 优点：存储方式简单、直接、方便计算。
  3. 应用：Floy-Warshall算法

• 邻接表法：

  1. 查询效率没有邻接矩阵存储方式高。

  2. 如果链过长，可以将链表转换成其他更高效的数据结构，比如平衡二叉查找树。

  3. 实际开发中，用红黑树或其他动态数据结构，比如跳表、散列表等，更快速地找到两个顶点之间是否存在边。

  4. 将链表改为有序动态数组，通过二分查找的方法快速定位两个顶点之间是否存在边。

     逆邻接表

应用场景

• 好友
• 亲密度
• 关注用户
• 粉丝

图上的收搜算法

在图中找到从一个顶点出发，到另一个顶点的路径。

Dijkstra算法 -- 贪心算法

概念

1. 计算一个节点到其他所有节点的最短路径。
2. 一种单源最短路径算法

复杂度

时间复杂度：O(E*logV)

A*算法--动态规划

概念

1. 对Dijkstra算法的优化和改造，可以更加快速找到从起点到终点的路线。
2. 一种启发式搜索算法。
   • 启发式搜索算法有：IDA*算法、蚁群算法、遗传算法、模拟退火算法等。

和Dijkstra算法代码的3点区别

1. 优先级队列构建的方式不同
2. A算法在更新dist值的时候，同步更新f值*。//TODO
3. 循环结束的条件不一样。

应用场景

地图、游戏中的地图