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

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

2021-02-20 00:16chengqiuming Python

这篇文章主要介绍了Python数据结构之图的应用,结合实例形式分析了Python数据结构中图的定义与遍历算法相关操作技巧,需要的朋友可以参考下

本文实例讲述了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数据结构之图的应用示例