python數(shù)據(jù)結(jié)構(gòu)之圖的實現(xiàn)方法

更新時間：2015年07月08日 14:36:51 作者：yupeng

這篇文章主要介紹了python數(shù)據(jù)結(jié)構(gòu)之圖的實現(xiàn)方法,實例分析了Python圖的表示方法與常用尋路算法的實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了python數(shù)據(jù)結(jié)構(gòu)之圖的實現(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è)計有所幫助。

您可能感興趣的文章:

相關(guān)文章

Python調(diào)用實現(xiàn)最小二乘法的方法詳解
所謂線性最小二乘法，可以理解為是解方程的延續(xù)，區(qū)別在于，當未知量遠小于方程數(shù)的時候，將得到一個無解的問題。本文主要和大家分享Python調(diào)用實現(xiàn)最小二乘法的方法，需要的可以參考一下
2023-04-04
python可視化大屏庫big_screen示例詳解
提到數(shù)據(jù)可視化，我們會想到 Plotly、Matplotlib、Pyecharts等可視化庫，或者一些商用軟件Tableau、FineBI等等。如果你希望操作更簡單、展現(xiàn)效果更強大，那么這款工具 big_screen 更適合
2021-11-11
Python實用小技巧之判斷輸入是否為漢字/英文/數(shù)字
這篇文章主要給大家介紹了關(guān)于Python實用小技巧之判斷輸入是否為漢字/英文/數(shù)字的相關(guān)資料,文中通過實例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
2023-06-06
幾個關(guān)于python Pdf 技巧的分享
這篇文章主要介紹了python使用技巧Pdf的詳細內(nèi)容，PyPDF2是一個純Python的開源庫，能夠分割或合并PDF文件，也可以裁剪或轉(zhuǎn)換PDF文件中的頁面，下面關(guān)于文章主題內(nèi)容將詳細介紹，需要的小伙伴可以參考一下
2022-02-02
這篇文章主要介紹了簡述Python中的面向?qū)ο缶幊痰母拍?面向?qū)ο缶幊淌荘ython的重要特性,需要的朋友可以參考下
2015-04-04