一種用來(lái)解決最短路徑的算法怠噪。這個(gè)最短不是時(shí)間或者距離的最短而是邊最少复局。歡聚話(huà)說(shuō)就是做地鐵的時(shí)候換乘最少。
圖簡(jiǎn)介
圖有節(jié)點(diǎn)和邊組成沾乘，一個(gè)節(jié)點(diǎn)可能有很多節(jié)點(diǎn)與之相連，它們成為鄰居浑测。
查找最短路徑
我們現(xiàn)在加入你想找個(gè)朋友幫忙代購(gòu)一臺(tái)電腦翅阵，于是你就在朋友圈里尋找，然后求助你的朋友讓他們?cè)诟髯缘呐笥讶湍悴檎摇Ｓ谑侵勒业綖槟愦?gòu)的人掷匠。你的朋友就是一維關(guān)系读慎，你朋友的朋友屬于二維關(guān)系，等等槐雾。當(dāng)然離你越近的說(shuō)明路徑就最短夭委，關(guān)系就最近，越能幫你代購(gòu)東西募强。
圖.jpg
設(shè)計(jì)思路
我們先把自身的一維關(guān)系列出來(lái)株灸，這里是bill的一維關(guān)系是jack ,robin, calm,然后分別找出他們?nèi)齻€(gè)的一維關(guān)系也就是bill的二維關(guān)系。
代碼實(shí)現(xiàn)
class Friend:
def __init__(self, name, canBuy):
self.name = name
self.canBuy = canBuy
robin = Friend('robin', True)
jack = Friend('jack', False)
calm = Friend('calm', False)
jessica = Friend('jessica', True)
rose = Friend('rose', False)
calvin = Friend('calvin', True)
graph = {}
graph['bill'] = [robin, jack, calm]
graph['robin'] = [calvin]
graph['jack'] = []
graph['calm'] = [jessica]
graph['jessica'] = []
graph['rose'] = []
graph['calvin'] = []
def searchName(name):
searchQue = graph[name]
searched = []
while searchQue:
person = searchQue.pop(0)
if person not in searched:
if person.canBuy:
return person
else:
name = person.name
searchQue += graph[name]
searched.append(person)
print searchName('bill').name
特點(diǎn)
- 廣度優(yōu)先搜索是否有從A-B的路徑擎值，有的話(huà)是找出最短路徑
- 需要按加入順序檢查搜索列表中的人慌烧，否則找到的不是最短路徑
- 對(duì)于檢查過(guò)的節(jié)點(diǎn)不要在去檢查，否則會(huì)造成循環(huán)鸠儿。
