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进阶教程之函数参数的多种传递方法

我们已经接触过函数(function)的参数(arguments)传递。当时我们根据位置,传递对应的参数。我们将接触更多的参数传递方式。 回忆一下位置传递: 复制代码 代码如下: def...

通过pycharm使用git的步骤(图文详解)

通过pycharm使用git的步骤(图文详解)

前言 使用git+pycharm有一段时间了,算是稍有点心得,这边整理一下,可能有的方法不是最优,欢迎交流,可能还是习惯敲命令去使用git,不过其实pycharm已经帮忙做了很多了,我们...

在python win系统下 打开TXT文件的实例

如下所示: fr=open("E:\Python\Test\datingTestSet.txt") arrayOLines = fr.readlines() open:打开文件 r...

python中hashlib模块用法示例

我们以前介绍过一篇Python加密的文章:Python 加密的实例详解。今天我们看看python中hashlib模块用法示例,具体如下。 hashlib hashlib主要提供字符加密...

一个计算身份证号码校验位的Python小程序

S = Sum(Ai * Wi), i=0,.......16 (现在的身份证号码都是18位长,其中最后一位是校验位,15位的身份证号码好像不用了) Ai对应身份证号码,Wi则为用于加权...