图的存储方式

  • 邻接表
  • 邻接矩阵

如何表达图？生成图？

图的表示方式很多，我们只需要熟练掌握一种，把这些图的代码写熟，以后遇到这种图的题之后，可以把这种图转换为我们熟悉的图结构

重点：用熟悉实现一种图的结构

image-20230628111856007

图的宽度优先遍历

  • 利用队列实现
  • 从源节点开始依次按照宽度进队列，然后弹出
  • 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
  • 知道队列变空

广度优先遍历

  • 利用栈实现
  • 从源节点开始把节点按照深度放入栈，然后弹出
  • 每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
  • 直到栈变空

拓扑排序

  • 先看哪个点是入度为0的点（入度为0的点一定是排在最前面的）
  • 把A和A的边去掉，然后寻找下一个入度为0的点B
  • 依次寻找所有入度为0的点，然后输出

最小生成树

在保证连通性的前提下，总的权值最小

只要我们可以实现一种机制，实现集合的查询和集合的合并，那么就能很轻易的实现最小生成树的生成（并查集）

kruskal算法

适用范围：要求无向图

prim算法

适用范围：要求无向图

Dijkstra算法

适用范围：没有权值为负的边（可以有权值为负数的边，但是不能有权值和为负数的环）

image-20230630121234591

如果存在负数的边，可能导致锁死的记录并不是最短路径，即确定的锁死的记录与实际不符

image-20230711185928428