概念
一种非线性数据结构，比树复杂。
分类
- 有向图
- 无向图
- 带权图
存储
邻接矩阵法：
- 缺点：浪费存储空间。
- 优点：存储方式简单、直接、方便计算。
- 应用：Floy-Warshall算法
邻接表法：
查询效率没有邻接矩阵存储方式高。
如果链过长，可以将链表转换成其他更高效的数据结构，比如平衡二叉查找树。
实际开发中，用红黑树或其他动态数据结构，比如跳表、散列表等，更快速地找到两个顶点之间是否存在边。
将链表改为有序动态数组，通过二分查找的方法快速定位两个顶点之间是否存在边。
逆邻接表
应用场景
- 好友
- 亲密度
- 关注用户
- 粉丝
图上的收搜算法
在图中找到从一个顶点出发，到另一个顶点的路径。
Dijkstra算法 -- 贪心算法
概念
- 计算一个节点到其他所有节点的最短路径。
- 一种单源最短路径算法
复杂度
时间复杂度：O(E*logV)
A*算法--动态规划
概念
- 对Dijkstra算法的优化和改造，可以更加快速找到从起点到终点的路线。
- 一种启发式搜索算法。
- 启发式搜索算法有：IDA*算法、蚁群算法、遗传算法、模拟退火算法等。
和Dijkstra算法代码的3点区别
- 优先级队列构建的方式不同
- A算法在更新dist值的时候，同步更新f值*。//TODO
- 循环结束的条件不一样。
应用场景
地图、游戏中的地图
网友评论