《我的第一本算法书》阅读笔记 4-2 广度优先搜索

浅浅的花香味﹌ 2022-10-22 05:29 23阅读 0赞

广度优先搜索是一种对图进行搜索的算法。假设我们一开始位于某个顶点（即起点），此 时并不知道图的整体结构，而我们的目的是从起点开始顺着边搜索，直到到达指定顶点（即终 点）。在此过程中每走到一个顶点，就会判断一次它是否为终点。广度优先搜索会优先从离起点 近的顶点开始搜索。

--------------------

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

A为起点，G为终点。一开始我们在起点A上，此时并不知道G在哪里。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

将可以从A直达的 三 个 顶 点B、C、D 设为下一步的候补 顶点。

![20210404164607600.png][]

从候补顶点中选出一个顶点。优先选择最早成 为候补的那个顶点，如果多个顶点同时成为候补，那么可以随意选择其中一个。

![20210404164629233.png][]

此处 B、C、D 同时成为候补，所以我们随机选择了最左边的顶点B。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

移动到选中的顶点B上。此时我们在B上， 所以B变为红色，同时将已经搜索过的顶点变为橙色。

此处，候补顶点是用“先入先出”（FIFO）的方式来管理的，因此可以使用“队列”这个 数据结构。

![20210404164731744.png][]

将可以从B直达的两个顶点E和F设为候补 顶点。

![2021040416474747.png][]

此时，最早成为候补顶点的是C和D，我们选择了左边的顶点C。

![20210404164759584.png][]

移动到选中的顶点C上。

![2021040416490266.png][]

将可以从C直达的顶点H设为候补顶点。

![20210404164912981.png][]

重复上述操作直到到达终点，或者所有的顶点都被遍历为止。

![20210404164931533.png][]

这个示例中的搜索顺序为 A、B、C、D、E、F、 H、I、J、K。

![20210404165000651.png][]

完成了从A到I的搜索，现在在顶点J处。

![2021040416501133.png][]

到达终点G，搜索结束。

--------------------

广度优先搜索的特征为从起点开始，由近及远进行广泛的搜索。因此，目标顶点离起点越近，搜索结束得就越快。

### 补充说明 ###

为了方便说明，这次讲解用的是没有闭环①的图。不过，如果图中有闭环，其搜索步骤也是一样的。像示例那样的没有闭环的图叫作“树”。

![闭环如图所示 起点和终点是同一个顶点][20210404165100792.png] 　闭环如图所示，起点和终点是同一个顶点。

《我的第一本算法书》  \[日\]石田保辉 宫崎修一/著    张贝/译

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20221022/9c7b4539d9e6490cbbefff729906cb81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20221022/993944e9e48e49569d16d38f5e05bc62.png
[20210404164607600.png]: /images/20221022/0e1ff232abbf41e3809dea3099c6d528.png
[20210404164629233.png]: /images/20221022/d2537840a411414ab2c7d160dbf1e2ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: /images/20221022/6853c5a5942745218de13f81bfeb1fd9.png
[20210404164731744.png]: /images/20221022/72aaf408b1f64610bf7fae880c0ea939.png
[2021040416474747.png]: /images/20221022/03c866e707f24881a471de8ddb0c9233.png
[20210404164759584.png]: /images/20221022/01fbafea72174a8b962b14af4d70576d.png
[2021040416490266.png]: /images/20221022/85cf342432ba4e9d819b7d9f3e376b68.png
[20210404164912981.png]: /images/20221022/d4ee74bcc24e4618b70c05e8ca99f0de.png
[20210404164931533.png]: /images/20221022/84d07db08ac047b884e0a0b4996523fb.png
[20210404165000651.png]: /images/20221022/4d735d177e044277b71e762cfaacb146.png
[2021040416501133.png]: /images/20221022/3e50d1bf57664719858ffc38cc6b033c.png
[20210404165100792.png]: /images/20221022/a96016aa372c4927a32144a19a0c1adc.png