Python数据结构之图的应用示例

yipeiwu_com7年前Python基础

本文实例讲述了Python数据结构之图的应用。分享给大家供大家参考,具体如下:

一、图的结构

二、代码

# -*- coding:utf-8 -*-
#! python3
def searchGraph(graph,start,end):
  results =[]
  generatePath(graph,[start],end,results)
  results.sort(key =lambda x:len(x))
  return results
def generatePath(graph,path,end,results):
  state = path[-1]
  if state == end:
    results.append(path)
  else:
    for arc in graph[state]:
      if arc not in path:
        generatePath(graph,path +[arc],end ,results)
if __name__ =='__main__':
  Graph={'A':['B','C','D'],
  'B':['E'],
  'C':['D','F'],
  'D':['B','E','G'],
  'E':[],
  'F':['D','G'],
  'G':['E']}
  r = searchGraph(Graph,'A','E')
  print("******************")
  print(' path A to E')
  print("******************")
  for i in r:
    print(i)

三、运行结果

******************
  path A to E
******************
['A', 'B', 'E']
['A', 'D', 'E']
['A', 'C', 'D', 'E']
['A', 'D', 'B', 'E']
['A', 'D', 'G', 'E']
['A', 'C', 'D', 'B', 'E']
['A', 'C', 'D', 'G', 'E']
['A', 'C', 'F', 'D', 'E']
['A', 'C', 'F', 'G', 'E']
['A', 'C', 'F', 'D', 'B', 'E']
['A', 'C', 'F', 'D', 'G', 'E']

运行效果图如下:

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

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

相关文章

Python实现快速排序和插入排序算法及自定义排序的示例

一、快速排序     快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要...

python实现通过shelve修改对象实例

本文实例讲述了python实现通过shelve修改对象的方法,分享给大家供大家参考。 具体实现方法如下: import shelve she = shelve.open('try.s...

解决python selenium3启动不了firefox的问题

解决python selenium3启动不了firefox的问题

selenium3.0之后的版本的就不支持直接打开火狐浏览器,启动火狐浏览器报错,如下图,要想运行就需要我们单独装上驱动。 3.0之前的版本,是可以直接打开火狐浏览器的。 解决办法:...

解决python3中自定义wsgi函数,make_server函数报错的问题

#coding:utf-8 from wsgiref.simple_server import make_server def RunServer(environ, start_...

Python时间获取及转换知识汇总

 时间处理是我们日常开发中最最常见的需求,例如:获取当前datetime、获取当天date、获取明天/前N天、获取当天开始和结束时间(00:00:00 23:59:59)、获取...