辅助数组

记录哪些点访问过

深度优先

  1. 从某一起始顶点开始后，优先访问没有访问过的点
  2. 到某一点的所有邻点都被访问后，回退，看看上一个点有没有没有访问的邻点
  3. 进行与前述相似的访问逻辑

时间效率

邻接矩阵时间复杂度为O(n**2)，适合访问稠密图

邻接表时间复杂度O(n+e)，适合访问稀疏图。

广度优先

从起始点开始，访问他的一级邻居，然后访问他的二级邻居，以此类推。

时间效率

与深度优先相同。

最小生成树

生成树：不存在回路的连通图

无向图的生成树：遍历时通过的边组成的集合

最小生成树：在一个网络中，在所有生成树中，使得各边权值之和最小的生成树，也叫最小代价生成树。

MST性质

普利姆算法

构建最小生成树的方法，使用贪心算法，每次总是选择两个集合之间权值最小的边，一步步构筑最小生成树。

时间复杂度：O(n**2)

克鲁斯卡尔算法

更直接的贪心算法

直接叫所有顶点组成一个集合，在所有的边中从小到大添加到集合中，若形成环则跳过这个边，直到所有的顶点都联通。

时间复杂度O(e)