算法（Algorithms）二

12.广度优先算法：一种图算法，解决最短（空间）路径算法问题

1.建立图问题模型

2.使用广度优先搜索：一级圆扩散到多级圆，使用队列实现，FIFO（先进先出）

3.栈：LIFO，后进先出

4.图映射：每个节点向外扩散一级到对应的下一级连接的数组集合

5.有向图：单向    无向图：双向

6.实现图：

1.创建一个队列deque

2.从队列中弹出一个人

3.检查这个人是否满足要求 是  否

4.否，将这个人的邻居加入队列，返回第二步

5.队列为空，说明没有目标

               7.树是图的子集，因此树都是图

1. 狄克斯特拉算法（仅适用于有向无环图）：找出最快（事件）路径算法

   （1）找到最便宜的节点

   （2）找到这个节点开销最少的邻节点

   （3）重复找邻节点，直到最终节点

   （4）计算最终路径

   （5）实现：

   
   

2. 权重：每条边的开销，带开销数字的称为加权图，不带开销数字称为非加权图

   
   

3. 贝尔曼-福德算法：在狄克斯特拉算法不能计算负权边的基础上改进，可以计算图的负权边最快路径（可以是其他变量）

#编写散列表graph