P9-前缀树和贪心算法

图的存储方式 1）邻接表：表的每一行存储该行的直接相邻 2）邻接矩阵

如何表达、生成图？

图的算法比较简单，但是表达图的数据结构是有很多的，怎么使用不同的方式合理的表达图，是复杂的。 即有一些特殊的图，可能会有一种特殊的表达方式。上面说的两种是通用的方式。

而解决这些问题的方法是用自己最喜欢的图结构的表示方式去做，自己只需要在每场面试中解决从特殊的图结构到自己喜欢的图结构的转换，这样就不会在特殊的图结构下进行思考，而在自己喜欢的图结构上进行。

一个点的入度：有多少点指向该点 一个点的出度：该点指向多少点 对于一个无向图来说，点的入度和出度一样

课程中，老师对于一个图，是如下的结构体

图的宽度优先遍历，

要有检查去重的机制

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

图的深度优先遍历

1. 利用栈实现
2. 从源节点开始把节点按照深度放入栈，然后弹出
3. 每弹出一个点，将该点的邻接节点（还没进栈）的放入栈
4. 直到栈空

目标：逮着没走过的路走到黑，所以找到路了就 break 重点是把当前的节点和邻居节点都压回去，这样栈里就会一直保存了当前的路径

拓扑排序

适用范围：要求有向图，且有入度为 0 的节点，且没有环 可以用来判断一个有向图是不是有向无环图。

1. 先找到这个有向图中找到入度为 0 的节点（可能不止一个），那么该点就会在拓扑排序中排在前面。
2. 然后擦掉该节点和从该点出去的边
3. 重复上面的步骤，依次排序

代码部分

Kruskal 算法

适用范围：要求无向图 常用来生成最小生成树

从边的角度出发，对边排序后，依次选择最小的边。

看到这了

Prim 算法