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

yipeiwu_com5年前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 ctypes库2_指定参数类型和返回类型详解

python函数的参数类型和返回类型默认为int。 如果需要传递一个float值给dll,那么需要指定参数的类型。 如果需要返回一个flaot值到python中,那么需要指定返回数据的类...

Python编写带选项的命令行程序方法

运行python程序时,有时需要在命令行传入一些参数。常见的方式是在执行时,在脚本名后直接追加空格分隔的参数列表(例如 python test.py arg0 arg1 arg2),然后...

python面试题之列表声明实例分析

python面试题之列表声明实例分析

本文实例讲述了python面试题之列表声明。分享给大家供大家参考,具体如下: 下面程序输出的结果为? val = [['a']*2]*2 print val val[0][1]='b...

python虚拟环境的安装和配置(virtualenv,virtualenvwrapper)

python虚拟环境的安装和配置(virtualenv,virtualenvwrapper)

一、为什么要安装虚拟环境     情景一、项目A需要某个库的1.0版本,项目B需要这个库的2.0版本。如果没有安装虚拟环境,那么当你使用这两个项目时,你就需要来回的卸...

python3+PyQt5图形项的自定义和交互 python3实现page Designer应用程序

python3+PyQt5图形项的自定义和交互 python3实现page Designer应用程序

本文通过Python3+PyQt5实现《python Qt Gui 快速编程》这本书的page Designer应用程序,采用QGraphicsView,QGraphicsScene,Q...