算法与数据结构学习笔记(7)

1、图

图由包含数据的顶点(Vertex)以及代表数据间关系的边(Edge)组成。现实中许多问题都可以用图表示。

  • 图有有向图、无向图、加权图等类型
  • 边可用邻接矩阵(Adjecency Matrix)或邻接表(Adjecency Matrix)表示
  • 图的主要遍历方法有深度优先搜索(DFS)、广度优先搜索(BFS)两种
  • 深度优先搜索使用栈实现,广度优先搜索使用队列实现
  • 最小生成树为连接所有顶点最少所需的边
  • 最小生成树中边的数量为顶点数量-1,且不能有循环
  • 可使用DFS建立最小生成树
  • 拓扑排序(Topological sorting)是把有向无循环图(Directed Acyclic Graph)的顶点按照出现顺序排序

2、加权图(Weighted Graph)

加权图的每条边都有一个权重(Weight),可用于表示距离、时间、价格等。

  • 最小生成树为连接所有顶点的总权重最低的边集合
  • 最小生成树建立方法:任选一个顶点为当前顶点,把所有边以权重作为优先级放入优先队列,从优先队列删除两端顶点均已在最小生成树中连接的边,再取出权重最小的边加入最小生成树。移动到新连接的顶点。重复直到所有顶点均已连接或所有边都测试过。
  • 最短路径问题可用Dijkstra算法解决

Leave a Reply

Your email address will not be published. Required fields are marked *