【026-week3】算法训练营第三周学习总结 #163

本周主要练习图、堆和排序、DFS、BFS相关的算法

1. 关于图的一些特性和总结
   1. 图按照有无方向分为有向图和无向图
   2. 无向图顶点的边数叫做度
   3. 有向图顶点分入度和出度
   4. 图中顶点间存在路径则说明是联通的，如果路径最终回到到起始点则存在环
2. 关于堆的一些特性和总结
   1. 堆实际上是一颗完全二叉树，满足父节点大于或小于子节点的特性
   2. 当父节点大于子节点时，为大顶堆或最大堆
   3. 当父节点小于子节点时，为小顶堆或最小堆
   4. 堆排序的时间复杂度是O(nlogn)
   5. python的heapq中只有小顶堆，所以存入时取负数则为大顶堆
3. 深度优先遍历
   1. 通常使用递归的方式
4. 广度优先遍历
   1. 逐层遍历节点即可，可使用数组记录当前行的节点，或者使用deque记录添加即将需要遍历的节点