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

yipeiwu_com6年前Python基础

本文实例讲述了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']}

找到一条路径:

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程序设计有所帮助。

相关文章

python连接MySQL数据库实例分析

python连接MySQL数据库实例分析

本文实例讲述了python连接MySQL数据库的方法。分享给大家供大家参考。具体实现方法如下: import MySQLdb conn = MySQLdb.connect(host=...

python中日期和时间格式化输出的方法小结

本文实例总结了python中日期和时间格式化输出的方法。分享给大家供大家参考。具体分析如下: python格式化日期时间的函数为datetime.datetime.strftime();...

python中dict字典的查询键值对 遍历 排序 创建 访问 更新 删除基础操作方法

字典是另一种可变容器模型,且可存储任意类型对象。 字典的每个键值(key=>value)对用冒号(:)分割,每个对之间用逗号(,)分割,整个字典包括在花括号({})中 ; 字典值可...

在Pycharm中修改文件默认打开方式的方法

在Pycharm中修改文件默认打开方式的方法

新下载了一个Pycharm,建了个小demo,期间产生了一个sqlite3文件,由于是第一次打开,就弹出选择打开方式的对话框,手一块直接点了个Text,然后就乱码了: 那我们不小心操作...

Django实现微信小程序的登录验证功能并维护登录态

Django实现微信小程序的登录验证功能并维护登录态

这次自己做了一个小程序来玩,在登录方面一直有些模糊,网上看了很多文档后,得出以下一种解决方案。 环境说明: 1、小程序只需要拿到openid,其他信息不存储。 2、Django自带的Us...