本文實例講述了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))