图
- 做题方法：选一个模板，实现所有的算法，遇到具体题目的时候，转化为自己熟悉的结构
拓扑排序
- 找到入度为0的点进队
- 每出队一个点，就把该点的影响消除，把nexts的入度减一
最小生成树
无向图，连通且权值和最小
krusal算法
从边来找——>最小的边min
看最小的边加上后是否成环
Q：如何判断是否成环
A：看边连接的两个点是否属于两个集合 哈希map（点，点所在的集合）
prim算法
- 最小生成堆
- 每次从解锁的边里选最短的，并且点to未访问
- 将边cur加入结果，点to加入visited，将点to相邻的边加入小顶堆
最小路径—Dijkstra算法
- 初始化
- distanceMap <node* ,int>：指定点到每一个点的距离
- 先加入<head,0>
- selectedNodes <node*>：已经访问过的点，即距离已确定，无需再修改
- distanceMap <node* ,int>：指定点到每一个点的距离
- 从distanceMap里选择距离最小且未访问的——>minnode
- 遍历Minnie的边集（从minnode出来的边）
- 如果distanceMap里没有点to的记录，就加入（点to，distance+weight）
- 如果有的话，就加入（点to，min{distance+weight，点to的距离}）
- 把minnode加入selected
- 找minnode，循环
- 遍历Minnie的边集（从minnode出来的边）