基于python模擬bfs和dfs代碼實(shí)例
更新時(shí)間：2020年11月19日 10:43:43 作者：Neaya
這篇文章主要介紹了基于python模擬bfs和dfs代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
BFS
"""
# @Time : 2020/11/8
# @Author : Jimou Chen
"""
# 廣搜
def bfs(graph, start):
queue = [start] # 先把起點(diǎn)入隊(duì)列
visited = set() # 訪問國的點(diǎn)加入
visited.add(start)
while len(queue):
vertex = queue.pop(0)
# 找到隊(duì)列首元素的連接點(diǎn)
for v in graph[vertex]:
if v not in visited:
queue.append(v)
visited.add(v)
# 打印彈出隊(duì)列的該頭元素
print(vertex, end=' ')
if __name__ == '__main__':
graph = {
'A': ['B', 'D', 'I'],
'B': ['A', 'F'],
'C': ['D', 'E', 'I'],
'D': ['A', 'C', 'F'],
'E': ['C', 'H'],
'F': ['B', 'H'],
'G': ['C', 'H'],
'H': ['E', 'F', 'G'],
'I': ['A', 'C']
}
bfs(graph, 'A')
A B D I F C H E G
Process finished with exit code 0
DFS
"""
# @Time : 2020/11/8
# @Author : Jimou Chen
"""
# 深搜
def dfs(graph, start):
stack = [start]
visited = set()
visited.add(start)
while len(stack):
vertex = stack.pop() # 找到棧頂元素
for v in graph[vertex]:
if v not in visited:
stack.append(v)
visited.add(v)
print(vertex, end=' ')
if __name__ == '__main__':
graph = {
'A': ['B', 'D', 'I'],
'B': ['A', 'F'],
'C': ['D', 'E', 'I'],
'D': ['A', 'C', 'F'],
'E': ['C', 'H'],
'F': ['B', 'H'],
'G': ['C', 'H'],
'H': ['E', 'F', 'G'],
'I': ['A', 'C']
}
dfs(graph, 'E')
E H G F B A I D C
Process finished with exit code 0
總結(jié)
很明顯一個(gè)用了隊(duì)列，一個(gè)用了棧
利用python語言優(yōu)勢，只需改動(dòng)pop即可
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了Python3讀取文件常用方法,以實(shí)例形式較為詳細(xì)的分析了Python一次性讀取、逐行讀取及讀取文件一部分的實(shí)現(xiàn)技巧,需要的朋友可以參考下2015-05-05
python實(shí)現(xiàn)定時(shí)播放mp3
這篇文章主要介紹了python實(shí)現(xiàn)定時(shí)播放mp3，程序非常簡單，功能很實(shí)用，主要是使用python實(shí)現(xiàn)了一首mp3歌每半小時(shí)播放一次，有需要的小伙伴可以參考下。2015-03-03
global關(guān)鍵字用來在函數(shù)或其他局部作用域中使用全局變量， nonlocal聲明的變量不是局部變量,也不是全局變量,而是外部嵌套函數(shù)內(nèi)的變量。這篇文章主要介紹了Python中 Global和Nonlocal的用法,需要的朋友可以參考下2020-01-01
Pandas DataFrame操作數(shù)據(jù)增刪查改
我們在用 pandas 處理數(shù)據(jù)的時(shí)候，經(jīng)常會(huì)遇到用其中一列數(shù)據(jù)替換另一列數(shù)據(jù)的場景。這一類的需求估計(jì)很多人都遇到，當(dāng)然還有其它更復(fù)雜的。解決這類需求的辦法有很多，這里我們來推薦幾個(gè)，這篇文章主要介紹了Pandas DataFrame操作數(shù)據(jù)的增刪查改2022-10-10
使用python的turtle函數(shù)繪制一個(gè)滑稽表情
Turtle庫是Python語言中一個(gè)很流行的繪制圖像的函數(shù)庫，今天通過實(shí)例代碼給大家分享使用python的turtle函數(shù)繪制一個(gè)滑稽表情，一起看看吧2020-02-02
Python:二維列表下標(biāo)互換方式(矩陣轉(zhuǎn)置)
今天小編就為大家分享一篇Python:二維列表下標(biāo)互換方式(矩陣轉(zhuǎn)置)，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
Python基于回溯法子集樹模板解決數(shù)字組合問題實(shí)例
這篇文章主要介紹了Python基于回溯法子集樹模板解決數(shù)字組合問題,簡單描述了數(shù)字組合問題并結(jié)合實(shí)例形式分析了Python回溯法子集樹模板解決數(shù)字組合問題的具體步驟與相關(guān)操作技巧,需要的朋友可以參考下2017-09-09
python 用opencv實(shí)現(xiàn)圖像修復(fù)和圖像金字塔
這篇文章主要介紹了python 如何用opencv實(shí)現(xiàn)圖像修復(fù)和圖像金字塔，幫助大家更好的理解和使用python處理圖片，感興趣的朋友可以了解下2020-11-11
關(guān)于Python OS模塊常用文件/目錄函數(shù)詳解
os模塊是操作系統(tǒng)接口模塊，提供了一些方便使用操作系統(tǒng)相關(guān)功能函數(shù)，這里介紹下os模塊中對于文件/目錄常用函數(shù)和使用方法。感興趣的朋友跟隨小編一起看看吧2021-06-06
這篇文章主要介紹了python計(jì)算文本文件行數(shù)的方法,涉及Python針對文本文件的讀取與行數(shù)統(tǒng)計(jì)相關(guān)技巧,需要的朋友可以參考下2015-07-07