python数据结构之图的实现方法-Tutoriel Python-php.cn

python数据结构之图的实现方法

WBOY

Libérer： 2016-06-10 15:09:43

original

1171 Les gens l'ont consulté

本文实例讲述了python数据结构之图的实现方法。分享给大家供大家参考。具体如下：

下面简要的介绍下：

比如有这么一张图：

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

可以用字典和列表来构建

graph = {'A': ['B', 'C'],
       'B': ['C', 'D'],
       'C': ['D'],
       'D': ['C'],
       'E': ['F'],
       'F': ['C']}

Copier après la connexion

找到一条路径：

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

Copier après la connexion

找到所有路径：

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

Copier après la connexion

找到最短路径：

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

Copier après la connexion

希望本文所述对大家的Python程序设计有所帮助。

Étiquettes associées：

python 图数据结构

source：php.cn

Article précédent：python基于BeautifulSoup实现抓取网页指定内容的方法 Article suivant：Python抓取百度查询结果的方法

Déclaration de ce site Web

Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Derniers articles par auteur