Python数据结构与算法之图的基本实现及迭代器实例详解

本文实例讲述了Python数据结构与算法之图的基本实现及迭代器。分享给大家供大家参考,具体如下:

这篇文章参考自《复杂性思考》一书的第二章,并给出这一章节里我的习题解答。

(这书不到120页纸,要卖50块!!,一开始以为很厚的样子,拿回来一看,尼玛。。。。。代码很少,给点提示,然后让读者自己思考怎么实现)

先定义顶点和边

class Vertex(object):
 def __init__(self, label=''):
  self.label = label
 def __repr__(self):
  return 'Vertex(%s)' % repr(self.label)
 # __repr__返回表达式, __str__返回可阅读信息
 __str__=__repr__ # 使其指向同一个函数
class Edge(tuple):
 # 继承自建tuple类型并重写new方法
 def __new__(cls, e1, e2):
  return tuple.__new__(cls, (e1,e2))
 def __repr__(self):
  return "Edge(%s, %s)" % (repr(self[0]), repr(self[1]))
 __str__ = __repr__

创建顶点和边的方法如下

if __name__=="__main__":
 # 创建两个顶点一条边
 v = Vertex('v')
 w = Vertex('w')
 e = Edge(v,w)
#  print e
 # 将顶点和边放入图中
 g = Graph([v,w],[e])
#  print g

创建一个基本的图类:

# 通过字典的字典实现图的结构
class Graph(dict):
 def __init__(self, vs=[], es=[]):
  """ 建立一个新的图,(vs)为顶点vertices列表,(es)为边缘edges列表 """
  for v in vs:
   self.add_vertex(v)
  for e in es:
   self.add_edge(e)
 def add_vertex(self,v):
  """ 添加顶点 v: 使用字典结构"""
  self[v] = {}
 def add_edge(self, e):
  """ 添加边缘 e: e 为一个元组(v,w)
   在两个顶点 w 和 v 之间添加成员e ,如果两个顶点之间已有边缘,则替换之 """
  v, w = e
  # 由于一条边会产生两个项目,因此该实现代表了一个无向图
  self[v][w] = e
  self[w][v] = e

练习2-2解答:图的一些基本操作

def get_edge(self,v1, v2):
  """ 接收两个顶点,若这两个顶点之间右边则返回这条边,否则返回None """
  try:
   return self[v1][v2]
  except:
   return None
 def remove_edge(self,e):
  """ 接受一条边,并且删除图中该边的所有引用 """
  v, w = e
  self[v].pop(w)
  self[w].pop(v)
 def vertices(self):
  """ 返回图中所有顶点的列表 """
  return self.keys()
 def edges(self):
  """ 返回图中边的列表 """
  es = set()    # 为了避免返回重复的边,设为集合
  for v1 in self.vertices():
   for v2 in self.vertices():
    es.add(self.get_edge(v2, v1))
  es.discard(None)  # 若集合中存在None元素,则删除
  return list(es)
  """ 利用图的字典结构获得所有边
  es = []
  for v in self.vertices():
   es.extend(self[v].values())
  es = list(set(es))
  return es
  """
 def out_vertices(self,v):
  """ 接受一个Vertex并返回邻近顶点(通过一条边连接到给定节点的节点)的列表 """
  return self[v].keys()
 def out_edges(self,v):
  """ 接受一个Vertex并返回连接到给定节点的边的列表 """
  return self[v].values()
 def add_all_edges(self,vs=None):
  """ 从一个无边的图开始,通过在各个顶点间添加边来生成一个完全图
   输入为目标顶点的列表,如果为None,则对所有的点进行全联结 """
  if vs == None:
   vs = self.vertices()
  for v1 in vs:
   for v2 in vs:
    if v1 is v2 : continue  # 假设不存在单顶点连通
    self.add_edge(Edge(v1,v2))

习题2-3 生成正则图

正则图是指图中每个顶点的度相同,生成正则图需要顶点数和度数满足一定条件,具体算法见注释:

def add_regular_edges(self,k):
  """ 从一个无边的图开始不断添加边,使得每个顶点都有相同的度k
   一个节点的度指的是连接到它的边的数量 """
  n = len(self.vertices())
  assert n > 1
  if k==1:
   vs = self.vertices()
   for i in range(n-1):
    self.add_edge(Edge(vs[i],vs[i+1]))
   return True
  if n < k+1:
   print "Cannot create regular graph"
   return False
  if n == k+1:
   self.add_all_edges()
   return True
  """
   设度数为k,图的阶数(顶点个数)为n
   利用归纳方法生成边的个数
   偶数度 当k=2m,m>=1时
   递归过程:
   0. 假设n>k+1,因为当n=k+1时,只要生成全连接即可,当n<k+1,则不能生成正则图
   1. 当n>k+1时:先从原图中前k+1个顶点(v1,v2,...,v2m-1,v2m, v2m+1)生成完全图
    此时,该k+1个顶点的度数均为k
   2. 现添加一个顶点vx,x=2m+2该顶点的度为0
   3. 删除m条不相连的边,如(v1,v2),(v3,v4),(v5,v6),...,(v2m-1,v2m),这时顶点v1,v2,...v2m的度为k-1
    记录下这m条边的顶点
   4. 联结 (v1,vx),(v2,vx),...,(v2m-1,vx),(v2m,vx),使得v1,v2,...,v2m,v2m+2的度=k
   5. 对新加入的点,重复3,4
   奇数度 当k=2m+1,m>=1时
   递归过程:
   设图G是有n个顶点的k正则图,且k=2m+1,m>=1,按照下面法则生成新图G1
   0. 假设n>k+1,因为当n=k+1时,只要生成全连接即可,当n<k+1,则不能生成正则图
   1. 在图G中任取m条顶点不同的边(x1,x2),(x3,x4),(x5,x6),...,(x2m-1,x2m) 记为组es1
    再另取m条顶点不同的边 (y1,y2),(y3,y4),(y5,y6),...,(y2m-1,y2m) 记为组es2
    其中xi和yj可以存在相同,但是两组中的所有边都不相同
    此时,该k+1个顶点的度数均为k
   2. 在图G中去掉m条边(x1,x2),(x3,x4),(x5,x6),...,(x2m-1,x2m),增加新的顶点v1,并增加2m条新边
    (v1,x1),(v1,x2),...,(v1,x2m-1),(v1,x2m)
   3. 在图G中去掉m条边(y1,y2),(y3,y4),(y5,y6),...,(y2m-1,y2m),增加新的顶点v2,并增加2m条新边
    (v2,y1),(v2,y2),...,(v2,y2m-1),(v2,y2m)
   4. 增加新边 (v1,v2)
   5. 对新的点v3,v4,重复1,2,3,4
   增加的顶点和边保证了v1,v2和x1,x2,...,x2m,y1,y2,...,y2m的度数为2m+1其余顶点度数不变
  """
  if k%2==0:
   # 选取前k+1个点,先构造完全图
   vs = self.vertices()
   self.add_all_edges(vs[:k+1])
   for i in range(k+1,n):   # 对之后的点进行遍历
    vsdel = []     # 记录删除过边的顶点
    for e in self.edges():
     # 获得边的两个顶点
     v1,v2 = e[0],e[1]
     if v1 not in vsdel and v2 not in vsdel:
      vsdel.append(v1)
      vsdel.append(v2)
      # 删除不相连的边
      self.remove_edge(e)
     # 当已删除的边数为k/2,即共k个非邻近点时,退出循环
     if len(vsdel)==k:
      break
    # 将新的点与记录的点进行连接
    for v in vsdel:
     self.add_edge(Edge(v,vs[i]))
  else:
   if n%2==0 and n>k+1: # 由上述法则可知,n必须为偶数
    # 选取前k+1个偶数点,先构造完全图
    vs = self.vertices()
    self.add_all_edges(vs[:k+1])
    for i in range(k+1,n,2): # 之后的点进行两两遍历
     vsdel1 = []    # 记录第1组删除的点
     edel1 = []    # 记录第1组删除的边
     for e in self.edges():
      # 获得边的两个顶点
      v1,v2 = e[0],e[1]
      if v1 not in vsdel1 and v2 not in vsdel1:
       vsdel1.append(v1)
       vsdel1.append(v2)
       # 删除不相连的边
       edel1.append(e)
       self.remove_edge(e)
      # 当已删除的边数为m,即共k-1个非邻近点时,退出循环
      if len(vsdel1)==k-1:
       break
     vsdel2 = []    # 记录第2组删除的点
     edel2 = []    # 记录第2组删除的边
     for e in self.edges():
      # 获得边的两个顶点
      v1,v2 = e[0],e[1]
      # 点可以和第一组相同,但边不可以
      if v1 not in vsdel2 and v2 not in vsdel2 and e not in edel1:
       vsdel2.append(v1)
       vsdel2.append(v2)
       # 删除不相连的边
       edel2.append(e)
       self.remove_edge(e)
      # 当已删除的边数为m,即共k-1个非邻近点时,退出循环
      if len(vsdel2)==k-1:
       break
     # 分别连接两组边
     for v in vsdel1:
      self.add_edge(Edge(v,vs[i]))
     for v in vsdel2:
      self.add_edge(Edge(v,vs[i+1]))
     self.add_edge(Edge(vs[i],vs[i+1]))
   else:
    print "Cannot create regular graph"
    return False
  return True

习题2-4:判断一个图是否连通,可以用BFS实现:

def is_connect(self):
  """ 判断一个图是否连通的
   从任意顶点开始进行一次BFS,将所有到达的节点都标记上,然后检查是否所有的节点都被标记上 """
  pass
  vs = self.vertices() # 获得所有顶点
  q, s = [], set()  # 搜索队列,标记集合
  q.append(vs[0])   # 从第1个顶点开始搜索
  while q:    # 当队列非空
   v = q.pop(0)  # 从队列中删除移一个顶点
   s.add(v)   # 并标记当前顶点
   # 搜索当前顶点的连接点,如果这些连接点没有被标记
   # 则将其添加到队列中
   for w in self.out_vertices(v):
    if w not in s:
     q.append(w)
  # 当队列为空时完成搜索,检查标记过的顶点是否等于图的顶点数
  if len(s)==len(vs):
   return True
  else:
   return False

测试代码:需要用到作者书中网页提供的GraphWorld.py实现可视化功能

from GraphWorld import CircleLayout,GraphWorld
from Graph import Graph,Vertex,Edge
import string
def test(n,k):
 # create n Vertices
 labels = string.ascii_lowercase + string.ascii_uppercase
 vs = [Vertex(c) for c in labels[:n]]
 # create a graph and a layout
 g = Graph(vs)
 g.add_regular_edges(k)
 layout = CircleLayout(g)
 # draw the graph
 gw = GraphWorld()
 gw.show_graph(g, layout)
 gw.mainloop()
if __name__ == '__main__':
 test(n=10,k=3)

以下为生成10个结点,度为3的正则图:

生成随机图,继承上面的Graph类:

from Graph import Graph,Vertex,Edge
from random import randint
class RandomGraph(Graph):
 """ 随即图 """
 def add_random_edges(self,p):
  """ 从一个·无边图开始随机生成边
   使得任意两个节点间存在边的概率为p (0<=p<=1) """
  for v1 in self.vertices():
   for v2 in self.vertices():
    if v1 is v2: continue
    if randint(0,100) < p*100 :
     self.add_edge(Edge(v1,v2))

测试一下:

from GraphWorld import CircleLayout,GraphWorld
import string
def test(n,p):
 # create n Vertices
 labels = string.ascii_lowercase + string.ascii_uppercase
 vs = [Vertex(c) for c in labels[:n]]
 # create a graph and a layout
 g = RandomGraph(vs)
 g.add_random_edges(p)
 print "connect?:",g.is_connect()
 layout = CircleLayout(g)
 # draw the graph
 gw = GraphWorld()
 gw.show_graph(g, layout)
 gw.mainloop()
if __name__ == '__main__':
 test(p=0.2,n=5)

迭代器部分代码:

# 迭代器
class AllTrue(object):
 def next(self):
  return True
 def __iter__(self):
  return self
# 使用AllTrue之类的迭代器可以表现无限序列
print zip('abc',AllTrue())
# 通过编写生成器函数创建一个迭代器
def generate_letters():
 for letter in 'abc':
  yield letter
iter = generate_letters()
import string
# 带有无限循环的生成器会返回一个不会终止的迭代器
def alphabet_cycle():
 while True:
  for i in range(1,10):
   for c in string.lowercase:
    yield c+str(i)
iter_ac = alphabet_cycle()
print iter_ac.next()

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

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

(0)

相关推荐

  • Python数据结构与算法之列表(链表,linked list)简单实现

    Python 中的 list 并不是我们传统(计算机科学)意义上的列表,这也是其 append 操作会比 insert 操作效率高的原因.传统列表--通常也叫作链表(linked list)--通常是由一系列节点(node)来实现的,其每一个节点(尾节点除外)都持有一个指向下一个节点的引用. 其简单实现: class Node: def __init__(value, next=None): self.value = value self.next = next 接下来,我们就可使用链表的结构来

  • Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

    本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法).分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法--通过边实现松弛 # 指定一个点到其他各顶点的路径--单源最短路径 # 初始化图参数 G = {1:{1:0, 2:1, 3:12}, 2:{2:0, 3:9, 4:3}, 3:{3:0, 5:5}, 4:{3:4, 4:0, 5:13, 6:15}, 5:{5:0, 6:4}, 6:{6:0}} # 每次找到离源点最近的一个顶

  • 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': [

  • python数据结构之图深度优先和广度优先实例详解

    本文实例讲述了python数据结构之图深度优先和广度优先用法.分享给大家供大家参考.具体如下: 首先有一个概念:回溯 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 深度优先算法: (1)访问初始顶点v并标记顶点v已访问. (2)查找顶点v的第一个邻接顶点w. (3)若顶点v的邻接顶点w存在,则继续执行:否则回

  • Python实现的数据结构与算法之链表详解

    本文实例讲述了Python实现的数据结构与算法之链表.分享给大家供大家参考.具体分析如下: 一.概述 链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接. 根据结构的不同,链表可以分为单向链表.单向循环链表.双向链表.双向循环链表等.其中,单向链表和单向循环链表的结构如下图所示: 二.ADT 这里只考虑单向循环链表ADT,其他类型的链表ADT大同小异.单向循环链表ADT(抽象数据类型)一般提供以下接口: ① SinCycLin

  • Python数据结构与算法之图结构(Graph)实例分析

    本文实例讲述了Python数据结构与算法之图结构(Graph).分享给大家供大家参考,具体如下: 图结构(Graph)--算法学中最强大的框架之一.树结构只是图的一种特殊情况. 如果我们可将自己的工作诠释成一个图问题的话,那么该问题至少已经接近解决方案了.而我们我们的问题实例可以用树结构(tree)来诠释,那么我们基本上已经拥有了一个真正有效的解决方案了. 邻接表及加权邻接字典 对于图结构的实现来说,最直观的方式之一就是使用邻接列表.基本上就是针对每个节点设置一个邻接列表.下面我们来实现一个最简

  • Python实现的数据结构与算法之快速排序详解

    本文实例讲述了Python实现的数据结构与算法之快速排序.分享给大家供大家参考.具体分析如下: 一.概述 快速排序(quick sort)是一种分治排序算法.该算法首先 选取 一个划分元素(partition element,有时又称为pivot):接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分).划分元素pivot.right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上:然后分别对left和right两个部分进行 递归排序. 其中

  • Python实现的数据结构与算法之双端队列详解

    本文实例讲述了Python实现的数据结构与算法之双端队列.分享给大家供大家参考.具体分析如下: 一.概述 双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构.双端队列也拥有两端:队首(front).队尾(rear),但与队列不同的是,插入操作在两端(队首和队尾)都可以进行,删除操作也一样. 二.ADT 双端队列ADT(抽象数据类型)一般提供以下接口: ① Deque() 创建双端队列 ② addFront(item) 向队首插入项 ③ addRe

  • Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

    本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表

  • Python实现的数据结构与算法之队列详解

    本文实例讲述了Python实现的数据结构与算法之队列.分享给大家供大家参考.具体分析如下: 一.概述 队列(Queue)是一种先进先出(FIFO)的线性数据结构,插入操作在队尾(rear)进行,删除操作在队首(front)进行. 二.ADT 队列ADT(抽象数据类型)一般提供以下接口: ① Queue() 创建队列 ② enqueue(item) 向队尾插入项 ③ dequeue() 返回队首的项,并从队列中删除该项 ④ empty() 判断队列是否为空 ⑤ size() 返回队列中项的个数 队

随机推荐