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)方法。分享給大家供大家參考。具體如下：

下面簡要的介紹下：

比如有這么一張圖：

    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

希望本文所述對大家的Python程序設(shè)計(jì)有所幫助。

您可能感興趣的文章:

相關(guān)文章

rhythmbox中文名亂碼問題解決方法
在使用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的開源庫,旨在簡化數(shù)據(jù)可視化的創(chuàng)建過程,本文將為新手朋友詳細(xì)介紹如何使用Holoviews創(chuàng)建復(fù)雜的可視化布局,感興趣的可以了解下
2024-11-11
python庫Celery異步發(fā)送電子郵件定時(shí)生成報(bào)告實(shí)戰(zhàn)示例
這篇文章主要介紹了python庫Celery異步發(fā)送電子郵件定時(shí)生成報(bào)告實(shí)戰(zhàn)示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
2024-01-01
Python?變量教程字節(jié)對象與字符串
這篇文章主要介紹了Python變量教程字節(jié)對象與字符串，字節(jié)對象是字節(jié)序列，而字符串是字符序列，字節(jié)對象在內(nèi)部是機(jī)器可讀的形式，字符串只是人類可讀的形式
2022-08-08
Python小進(jìn)度條顯示代碼
今天小編就為大家分享一篇關(guān)于Python小進(jìn)度條顯示代碼，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧
2019-03-03
Python基于OpenCV實(shí)現(xiàn)人臉檢測并保存
這篇文章主要介紹了Python基于OpenCV實(shí)現(xiàn)人臉檢測并保存，具有一定的參考價(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ù)庫字段的技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
2015-03-03
如何使用Selenium實(shí)現(xiàn)簡單的網(wǎng)絡(luò)自動(dòng)化操作指南
Selenium是一個(gè)用于Web應(yīng)用測試的工具,Selenium測試直接運(yùn)行在瀏覽器中,就像真正的用戶在操作一樣,這篇文章主要給大家介紹了關(guān)于如何使用Selenium實(shí)現(xiàn)簡單的網(wǎng)絡(luò)自動(dòng)化操作的相關(guān)資料,需要的朋友可以參考下
2024-03-03