广度优先搜索

解决最短路径问题的算法被称为广度优先搜索(breadth-first search,BFS)。

广度优先搜索(breadth-first search,BFS)让你能够找出两样东西之间的最短距离,不过最短距离的含义很多!使用广度优先搜索可以:

  1. 编写国际跳棋AI,计算最少走多少步可以获胜。
  2. 编写拼写检查器,计算最少编辑多少个地方就可以将错拼的单词改成正确的单词,如将READED改为READER需要编辑一个地方。
  3. 根据你的人际关系网络找到关系最近的医生。

使用广度优先搜索解决问题需要两个步骤:

  1. 使用图来建立问题模型。
  2. 使用广度优先搜索解决问题。

图是什么:

图是由节点和边组成。一个节点可能与众多节点直接相连,这些节点被称为‘邻居’。

广度优先搜索

广度优先搜索是一种用于图的查找算法,课帮助回答两类问题:

  1. 第一类问题:从节点A出发,有前往节点B的路吗?
  2. 第二类问题:从节点A出发,前往节点B的路哪条路径最短。

比如说你需要找到一位芒果经销商,你首先检查你自己的朋友有没有是芒果经销商,检查完发现没有,那么开始检查你朋友的朋友有没有是芒果经销商。这种按添加顺序进行查找的数据结构叫做队列(queue)

队列

队列的工作原理与现实生活中的队列完全相同。假如你与朋友一起在公交车站排队,如果你排在他前面,你将先上车。队列的原理榆次相同。队列类似于栈,你不能随机访问队列中的元素。队列只支持两种操作:入队和出队

如果你将两个元素加入队列,先加入的元素将在后加入的元素之前出队。这样,先加入的人将先出队并先被检查。

队列是一种先进先出的数据结构,而栈是一种后进先出的数据结构。

 

小结

  • 广度优先搜索指出是否有从A到B的路径。
  • 如果有,广度优先搜索将找出最短路径。
  • 面临类似于寻找最短路径的问题时,可尝试使用图来建立模型,再使用广度优先搜索来解决问题。
  • 有向图中的边为箭头,箭头的方向指定了关系的方向。
  • 无向图中的边不带箭头,其中的关系是双向的。
  • 队列是先进先出。
  • 栈是后进先出。
  • 你需要按加入顺序检查搜索列表中的人,否则找到的就不是最短路径,因此搜索列表必须是队列。
  • 对于检查过的人,务必不要再去检查,否则可能导致无限循环。

python代码示例

#广度优先搜索
graph = {}
graph['you'] = ['alice', 'bob', 'claire']
graph['alice'] = ['anuj', 'peggy']
graph['claire'] = ['thom', 'jonny']
graph['anuj'] = []
graph['peggy'] = []
graph['thom'] = []
graph['jonny'] = []

# print(graph)
# exit()

from collections import deque

#该函数是判断该人是不是销售商
def person_is_seller(name):
    return name[-1] == 'm'

#该函数是找出是销售商的那个人
def search(name) :
     search_queue = deque() #先创建一个队列
     #判断有没有这个人
     if name in graph.keys() :
         search_queue += graph[name] #将你的朋友都放在这个搜索队列中来
         searched = []  #这个是已经搜索过的
         while search_queue: #只要队列不为空

             person = search_queue.popleft()  #就取出其中的第一个人  先进先出

             if not person in searched :

                 if person_is_seller(person):  # 判断是不是芒果果销售商
                     print(person + ' is a mango seller!')
                     return True
                 else:
                     #判断键值存在不存在
                     if person in graph.keys():
                         search_queue += graph[person]  # 如果不是芒果销售商  将这个人的朋友都放进队列来
                     searched.append(person)  # 然后将检查过的人放进已检查列表
     return False


print(search('you'))

php写法

<?php
/**
 * php队列算法
 */
class data {
 //数据
 private data;

 public function __construct(data){
 this->data=data;
 echo data.":哥进队了!<br>";
 }

 public function getData(){
 returnthis->data;
 }
 public function __destruct(){
 echo this->data.":哥走了!<br>";
 }
}
class queue{
 protectedfront;//队头
 protected rear;//队尾
 protectedqueue=array('0'=>'队尾');//存储队列
 protected maxsize;//最大数

 public function __construct(size){
 this->initQ(size);
 }
 //初始化队列
 private function initQ(size){this->front=0;
 this->rear=0;this->maxsize=size;
 }
 //判断队空
 public function QIsEmpty(){
 returnthis->front==this->rear;
 }
 //判断队满
 public function QIsFull(){
 return (this->front-this->rear)==this->maxsize;
 }
 //获取队首数据
 public function getFrontDate(){
 return this->queue[this->front]->getData();
 }
 //入队
 public function InQ(data){
 //先判断队列中是不是已经满了
 if(this->QIsFull()) {
 echo data.":我一来咋就满了!(队满不能入队,请等待!)<br>";
 } else {this->front++;
 //让队列中的元素都向前移动一位
 for(i =this->front; i>this->rear; i--){
 //echodata;
 if(this->queue[i]) {
 unset(this->queue[i]);
 this->queue[i]=this->queue[i-1];
 }
 }
 this->queue[this->rear+1]=new data(data);
 //print_r(this->queue);
 //echo this->front;
 echo '入队成功!<br>';
 }
 }
 //出队
 public function OutQ(){
 if(this->QIsEmpty()) {
 echo "队空不能出队!<br>";
 }
 else{
 //让队列中的元素都向后移动一位
 unset(this->queue[this->front]);
 this->front--;
 //print_r(this->queue);
 //echo this->front;
 echo "出队成功!<br>";
 }
 }
}q=new queue(3);
q->InQ("小苗");q->InQ('马帅');
q->InQ('溜冰');q->InQ('张世佳');
q->OutQ();q->InQ("周瑞晓");
q->OutQ();q->OutQ();
q->OutQ();q->OutQ();

评论

  1. 3年前
    2018-11-30 10:33:28

    111

  2. 3年前
    2019-2-05 23:25:36

    Cialis 20 Ou Acheter priligy venta en chile Sildenafil 50mg Tablets To Buy Online Free Sample Viagra Canada Amoxicillin Diaper Rash Online Pharmacy Order In Png Ist Viagra Rezeptpflichtig Cialis Levitra Nombre Droga Generica Viagra levitra achat Seroquel No Prescription Pharmacy Ph And Amoxicillin Cialis Es Efectivo Ou Acheter Kamagra En France online cialis How To Take Amoxicillin Propecia Generica De Farmacias buy cialis Healthy Man Pills Comprar Cialis Generico Por Internet Zithromax Dosage For Bronchitis Drugs cialis Diclofenac Buy Online Wirkt Nicht Cialis Levitra Priligy Necesita Receta Medica H Pylori And Cephalexin generic cialis Us Cheap Viagra Dapoxetina In Natura Buy Xenical No Prescription Uk

  3. 3年前
    2019-3-16 3:41:31

    How To Buy Fucidin Cream Cialis Alternative Over The Counter online pharmacy Levitra Potenz Global Pharmacy Canada Viagra Per Cani

  4. 3年前
    2019-3-18 21:38:41

    Hello, after reading this remarkable article i am too happy to share my
    familiarity here with colleagues.

  5. 3年前
    2019-4-06 4:11:36

    Hmm is anyone else experiencing problems with the images
    on this blog loading? I’m trying to find out if its a problem on my end or if it’s the blog.
    Any feedback would be greatly appreciated.

    • ezreal_rao 博主
      3年前
      2019-4-11 10:27:12

      i don’t konw what you speak.

  6. 3年前
    2019-4-18 1:04:15

    Puedo Comprar Cialis Sin Receta cialis for sale Cheap Flagyl Keflex

    • ezreal_rao 博主
      3年前
      2019-4-18 22:13:34

      fuck! gun

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇