??實(shí)現(xiàn)、沖突和散列函數(shù)?? 算法圖解：第六章：廣度優(yōu)先搜索
2022-04-29 14:10:13

Hello，大家好我叫是Dream呀，一個有趣的Python博主，小白一枚，多多關(guān)照 ?

入門須知：這片樂園從不缺乏天才，努力才是你的最終入場券！

最后，愿我們都能在看不到的地方閃閃發(fā)光，一起加油進(jìn)步

“一萬次悲傷，依然會有Dream，我一直在最溫暖的地方等你”，唱的就是我！哈哈哈~

第六章：廣度優(yōu)先搜索

• ??6.1圖簡介??
• ??6.2圖是什么??
• ??6.3廣度優(yōu)先搜索??

• ??6.3.1查找最短路徑??
• ??6.3.2隊(duì)列??

• ??6.4實(shí)現(xiàn)圖??
• ??6.5實(shí)現(xiàn)算法??

• ??6.5.1運(yùn)行時間??
• ??6.5.2樹??

• ??6.6小結(jié)??
• ??二級目錄??
• ??三級目錄??
• ??最后的福利??

6.1圖簡介

圖算法：廣度優(yōu)先搜索！

前往某一地點(diǎn)，需要的最短路徑被稱為是：最短路徑問題

解決最短路徑問題的算法被稱作：廣度優(yōu)先搜索

6.2圖是什么

圖模擬一組連接。圖由節(jié)點(diǎn)和邊組成。

一個節(jié)點(diǎn)可以與眾多個節(jié)點(diǎn)直接相連，這些節(jié)點(diǎn)被稱為鄰居。

6.3廣度優(yōu)先搜索

廣度優(yōu)先搜索是一種用于圖的查找算法，可幫助回答兩類問題：

第一類問題：從節(jié)點(diǎn)A出發(fā)，有前往B節(jié)點(diǎn)的路徑嗎？

第二類問題：從節(jié)點(diǎn)A出發(fā)，前往節(jié)點(diǎn)B的哪條路徑最短呢？

拿賣水果的例子來說，如果你的朋友不是經(jīng)銷商的話，就將你的朋友也加入到名單中。這意味著你將在她的朋友、朋友的朋友等中查找。使用這種算法將搜遍你的整個人際關(guān)系網(wǎng)，知道找到水果經(jīng)銷商。這就是廣度優(yōu)先搜索算法。

6.3.1查找最短路徑

首先，拿上文來說，你應(yīng)該先在一度關(guān)系中搜索，確定其沒有芒果銷售商后，才在二度關(guān)系中搜索。

有一個可實(shí)現(xiàn)這種目的的數(shù)據(jù)結(jié)構(gòu)，那就是隊(duì)列。

6.3.2隊(duì)列

隊(duì)列的工作原理和現(xiàn)實(shí)生活中的隊(duì)列完全相同。如果你排在他前面，你將先上車。隊(duì)列類似于棧，你不能隨機(jī)地訪問隊(duì)列的元素。

隊(duì)列只支持兩種操作：入隊(duì)和出隊(duì)

隊(duì)列先進(jìn)先出，而棧后進(jìn)先出！

6.4實(shí)現(xiàn)圖

圖由多個節(jié)點(diǎn)組成，每個節(jié)點(diǎn)都與鄰近節(jié)點(diǎn)相連。

散列表讓你能夠?qū)㈡I映射到值，在這里只需要將節(jié)點(diǎn)映射到其所有鄰居。散列表是無序的，因此添加鍵值對的順序無關(guān)緊要！

關(guān)系單向：有向圖

無向圖沒有箭頭，直接相連的節(jié)點(diǎn)互為鄰居。

6.5實(shí)現(xiàn)算法

首先，創(chuàng)建一個隊(duì)列。在Python中，可使用函數(shù)deque來創(chuàng)建一個雙端隊(duì)列。

from collections import deque
search_queue=deque()
search_queue+=graph["you"]

別忘了，這里的graph[‘you’]是一個數(shù)組，其中包含了你的所有鄰居，如[‘a(chǎn)lice’,‘bob’,‘claire’]。這些鄰居都將加入到搜索隊(duì)列里。

while search_queue:
    person=search_queue.popleft()
    if person_is_seller(person):
        print(person + 'is seller')
        return True
    else:
        search_queue+=graph[person]
return False

最后你還需要編寫函數(shù)來判斷一個人是不是經(jīng)銷商，如下所示：

def person_is_seller(name):
        return name[-1]=='m'

檢測這個人的名字是否以m結(jié)尾：如果是，他就是經(jīng)銷商。這種方法有點(diǎn)搞笑，但就這個實(shí)例而言是可行的。

這個算法將不斷執(zhí)行，直到滿足以下條件之一：

1.找到一位經(jīng)銷商

2.隊(duì)列為空，這將意味著你的人際關(guān)系網(wǎng)中沒有經(jīng)銷商。

A既是B的朋友，又是C的朋友，因此他會兩次被加入到隊(duì)列中，這就會導(dǎo)致后手檢測的將變成無用功。

from collections import deque
def search(name):
    search_queue =deque()
    search_queue+=graph[name]
    searched=[]#這個數(shù)組用于記錄檢查過的人
    while search_queue:
        person = search_queue.popleft()
        if person not in searched:#僅當(dāng)這個人沒檢查過時才檢查
            if person_is_seller(person):
                print(person+'is seller')
                return True
            else:
                search_queue+=graph[person]
                searched.append(person)#將這個人標(biāo)記為檢查過
    return False
search("you")

6.5.1運(yùn)行時間

如果你的整個人際關(guān)系網(wǎng)中搜索芒果銷售商，就意味著你將沿著每條邊前行，因此運(yùn)行時間至少O（邊數(shù)）

你還使用了一個隊(duì)列，其中包含要檢查的每個人。將一個人添加到隊(duì)列需要的時間是固定的，即為O（1），因此對每個人都這樣做需要的總時間為O（人數(shù)）。所以，廣度優(yōu)先搜索的運(yùn)行時間為O（人數(shù)加邊數(shù)），通常記作O（V+E），其中V為頂點(diǎn)數(shù)，E為邊數(shù)。

6.5.2樹

有一種圖由節(jié)點(diǎn)和邊組成，但沒有往上指的箭頭，這種圖被稱為樹，樹是一種特殊的圖！

6.6小結(jié)

1.廣度優(yōu)先搜索指出是否有從A到B的路徑；

2.如果有，廣度優(yōu)先搜索將找出最短路徑；

3.面臨類似于尋找最短路徑的問題時，可以嘗試使用圖來建立模型，再使用廣度優(yōu)先搜索來解決問題；

4.有向圖的邊為箭頭，箭頭的方向指定了關(guān)系的方向；

5.無向圖的邊不帶箭頭，其中關(guān)系是雙向的。

6.隊(duì)列是先進(jìn)先出的；

7.棧是后進(jìn)先出的

8.你需要按加入順序檢查搜索列表中的人，否則找到的就不是最短路徑，因此搜索列表必須是隊(duì)列。

9.對于檢查過的人，務(wù)必不要再去檢查，否則可能導(dǎo)致無限循環(huán)。

二級目錄

三級目錄

最后的福利

??????最后一點(diǎn)小福利帶給大家：如果想快速上手python的小伙伴們，這個詳細(xì)整理PPT可以迅速幫助大家打牢python基礎(chǔ)，需要的小伙伴們可以下載一下 Python入門基礎(chǔ)教程全套+小白速成+學(xué)不會來找我！

還有自制表白神器，需要自取：

Python表白神器，源碼+解析+各種完美配置+浪漫新穎

好啦，這就是今天要給大家分享的全部內(nèi)容了

如果你喜歡的話，就不要吝惜你的一鍵三連了~