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程序设计有所帮助。

相关文章

Django-Model数据库操作(增删改查、连表结构)详解

Django-Model数据库操作(增删改查、连表结构)详解

一、数据库操作 1、创建model表 基本结构 from django.db import models class userinfo(models.Model): #如果没...

python生成指定长度的随机数密码

复制代码 代码如下:#!/usr/bin/env python# -*- coding:utf-8 -*- #导入random和string模块import random, string...

深入浅析Python中join 和 split详解(推荐)

python join 和 split方法简单的说是:join用来连接字符串,split恰好相反,拆分字符串的。 .join()   join将 容器对象 拆分并以指定的字符将列表内的元...

numpy中实现ndarray数组返回符合特定条件的索引方法

numpy中实现ndarray数组返回符合特定条件的索引方法

在numpy的ndarray类型中,似乎没有直接返回特定索引的方法,我只找到了where函数,但是where函数对于寻找某个特定值对应的索引很有用,对于返回一定区间内值的索引不是很有效,...

pytorch实现focal loss的两种方式小结

我就废话不多说了,直接上代码吧! import torch import torch.nn.functional as F import numpy as np from torch...