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))