算法 in Golang：Breadth-first search（BFS、广度优先搜索）

算法 in Golang：Breadth-first search

（BFS、广度优先搜索）

最短路径问题 Shortest-path problem

• 从 A 到 F 点有多条路径
  

解决问题的算法 Breadth-first Search（广度优先搜索）

• 将问题建模为图（Graph）
  
• 通过 Breadth-first Search 算法来解决问题
  

图（Graph）是什么？

图是用来对不同事物间如何关联进行建模的一种方式
图是一种数据结构
Breadth-first Search（BFS）广度优先搜索算法

• 作用于图（Graph）
  
• 能够回答两类问题：
  
  
  • 是否能够从节点 A 到节点 B？
    
  • 从 A 到 B 的最短路径是什么？
    
  
  

以社交网络为例

• 直接添加的朋友
  
  
  
  • 朋友的朋友...
    
  • 第一层没找到再找第二层
    
  
  

数据结构 Queue

• 先进来的数据先处理（FIFO）先进先出原则
  
• 无法随机的访问 Queue 里面的元素
  
• 相关操作：
  
  
  
  • enqueue：添加元素
    
  • dequeue：移除元素
    
  
  

例子

找到名为 Tom 的朋友

• 把你所有的朋友都加到 Queue 里面
  
• 把 Queue 里面第一个人找出来
  
• 看他是不是 Tom
  
  
  • 是 结束任务
    
  • 否 把他所有的朋友加到 Queue  重复操作
    
  
  

创建项目

[code]~/Code/go via
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！