python數(shù)據(jù)結(jié)構(gòu)之圖的實(shí)現(xiàn)方法
更新時(shí)間：2015年07月08日 14:36:51 作者：yupeng
這篇文章主要介紹了python數(shù)據(jù)結(jié)構(gòu)之圖的實(shí)現(xiàn)方法,實(shí)例分析了Python圖的表示方法與常用尋路算法的實(shí)現(xiàn)技巧,需要的朋友可以參考下
本文實(shí)例講述了python數(shù)據(jù)結(jié)構(gòu)之圖的實(shí)現(xiàn)方法。分享給大家供大家參考。具體如下：
下面簡(jiǎn)要的介紹下：
比如有這么一張圖：
A -> B
A -> C
B -> C
B -> D
C -> D
D -> C
E -> F
F -> C
可以用字典和列表來構(gòu)建
graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']}
找到一條路徑：
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath: return newpath
return None
找到所有路徑：
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not graph.has_key(start):
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
找到最短路徑：
def find_shortest_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
shortest = None
for node in graph[start]:
if node not in path:
newpath = find_shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
希望本文所述對(duì)大家的Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
在使用rhythmbox過程中，出現(xiàn)了，如果是中文名則會(huì)出現(xiàn)亂碼，下面的方法即可解決2008-09-09
Python基于pywinauto實(shí)現(xiàn)的自動(dòng)化采集任務(wù)
這篇文章主要介紹了Python基于pywinauto實(shí)現(xiàn)的自動(dòng)化采集任務(wù),模擬了輸入單詞, 復(fù)制例句, 獲取例句, 清空剪切板, 然后重復(fù)這個(gè)操作,需要的朋友可以參考下2023-04-04
Python使用Holoviews創(chuàng)建復(fù)雜的可視化布局
Holoviews是一個(gè)基于Python的開源庫(kù),旨在簡(jiǎn)化數(shù)據(jù)可視化的創(chuàng)建過程,本文將為新手朋友詳細(xì)介紹如何使用Holoviews創(chuàng)建復(fù)雜的可視化布局,感興趣的可以了解下2024-11-11
python庫(kù)Celery異步發(fā)送電子郵件定時(shí)生成報(bào)告實(shí)戰(zhàn)示例
這篇文章主要介紹了python庫(kù)Celery異步發(fā)送電子郵件定時(shí)生成報(bào)告實(shí)戰(zhàn)示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2024-01-01
這篇文章主要介紹了Python變量教程字節(jié)對(duì)象與字符串，字節(jié)對(duì)象是字節(jié)序列，而字符串是字符序列，字節(jié)對(duì)象在內(nèi)部是機(jī)器可讀的形式，字符串只是人類可讀的形式2022-08-08
今天小編就為大家分享一篇關(guān)于Python小進(jìn)度條顯示代碼，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-03-03
Python基于OpenCV實(shí)現(xiàn)人臉檢測(cè)并保存
這篇文章主要介紹了Python基于OpenCV實(shí)現(xiàn)人臉檢測(cè)并保存，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-07-07
python獲取一組數(shù)據(jù)里最大值max函數(shù)用法實(shí)例
這篇文章主要介紹了python獲取一組數(shù)據(jù)里最大值max函數(shù)用法,實(shí)例分析了max函數(shù)的使用技巧,需要的朋友可以參考下2015-05-05
pymongo實(shí)現(xiàn)控制mongodb中數(shù)字字段做加法的方法
這篇文章主要介紹了pymongo實(shí)現(xiàn)控制mongodb中數(shù)字字段做加法的方法,涉及Python使用pymongo模塊操作mongodb數(shù)據(jù)庫(kù)字段的技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-03-03
如何使用Selenium實(shí)現(xiàn)簡(jiǎn)單的網(wǎng)絡(luò)自動(dòng)化操作指南
Selenium是一個(gè)用于Web應(yīng)用測(cè)試的工具,Selenium測(cè)試直接運(yùn)行在瀏覽器中,就像真正的用戶在操作一樣,這篇文章主要給大家介紹了關(guān)于如何使用Selenium實(shí)現(xiàn)簡(jiǎn)單的網(wǎng)絡(luò)自動(dòng)化操作的相關(guān)資料,需要的朋友可以參考下2024-03-03