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实现按长宽比缩放图片

使用python按图片固定长宽比缩放图片到指定图片大小,空白部分填充为黑色。 代码 # -*- coding: utf-8 -*- from PIL import Image c...

python中将两组数据放在一起按照某一固定顺序shuffle的实例

有的时候需要将两组数据,比如特征和标签放在一起随机打乱, 但是又想记录这种打乱的顺序,那么该怎么做呢?下面是一个很好的方法: b = [1, 2,3, 4, 5,6 , 7,8 ,9...

ActiveMQ:使用Python访问ActiveMQ的方法

ActiveMQ:使用Python访问ActiveMQ的方法

Windows 10家庭中文版,Python 3.6.4,stomp.py 4.1.21 ActiveMQ支持Python访问,提供了基于STOMP协议(端口为61613)的库。 Act...

mvc框架打造笔记之wsgi协议的优缺点以及接口实现

mvc框架打造笔记之wsgi协议的优缺点以及接口实现

前言: 又是WSGI ,这是我曾经比较熟悉的协议,以前针对实现了wsgi server的unicorn和uwsgi都写过源码解析的文章。  其实他们的实现也很简单,就是给fla...

浅谈Python traceback的优雅处理

刚接触Python的时候,简单的异常处理已经可以帮助我们解决大多数问题,但是随着逐渐地深入,我们会发现有很多情况下简单的异常处理已经无法解决问题了,如下代码,单纯的打印异常所能提供的信息...