Python数据结构与算法之图的基本实现及迭代器实例详解
作者:hanahimi 发布时间:2023-03-22 12:22:42
标签: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程序设计有所帮助。
来源:http://www.cnblogs.com/hanahimi/p/4693260.html
0
投稿
猜你喜欢
- 最近Google Code推出了一个面向网站开发者的 * Google DocType。它来自于网站开发者同时又面
- 现在Ajax是一个相当火的东西,那么Ajax是什么呢?我的理解Ajax就是一个工具,就是一个客户端的技术,不管用何种服务器端技术都可以用Aj
- 本节重点让学生了安装上Python,配置好环境变量Python目前已支持所有主流操作系统,在Linux,Unix,Mac系统上自带Pytho
- 继续Mootools常用方法扩展,依然还是String类的扩展。方法:unescapseHTML说明:这个上次忘了,和escapseHTML
- 今天有朋友问我 Turtle的安装问题,在这里简单说在github上我们可以看到Turtle这个库很久没有更新了,里面还有一些python3
- 0、前言评判一个算法的好坏的标准:时间复杂度空间复杂度1、归并排序算法是什么?冒泡排序(Bubble Sort)是一种建立在归并操作上面的一
- Microsoft SQL Server 2000复制的概念:在数据库之间对数据和数据库对象进行复制和分发并进行同步以确保其一致性的一组技术
- 有时在处理不规则数据时需要提取文本包含的时间日期。dateutil.parser模块可以统一日期字符串格式。datefinder模块可以在字
- 一、起源 因子分析的起源是这样的:1904年英
- 对角矩阵scipy中的函数在scipy.linalg中,通过tri(N, M=None, k=0, dtype=None)可生成N&
- 安装pyecharts1.8.0版本后导入pyecharts模块绘图时报错: “所有图表类型将在 v1.9.0 版本开始强制使用 Chart
- 各位大哥: 在javascript中如何取整?比如: var
- 前言format语法格式:str.format()str是指字符串实例对象,常用格式为‘ ’.for
- 目录需求分析进一步分析再进一步分析代码实现我们在写爬虫的过程中,除了研究反爬之外,几乎全部的时间都在写解析逻辑。那么,生命苦短,为什么我们不
- 本文实例讲述了Python判断有效的数独算法。分享给大家供大家参考,具体如下:一、题目判断一个 9x9 的数独是否有效。只需要根据以下规则,
- 背景在校园里认证上网很麻烦需要web输入账号密码有时还会忘记web地址此时就需要一个人或者程序帮我们实现,这时我想到用python制作这个程
- 上期回顾上一次的图像清晰度评价没有成功,主要的原因是那几张图像清晰度评价函数都实际都采用了梯度求解,不同的场景灰度的明暗不同,梯度可能会很大
- pygame鼠标进行拖拽移动图片、缩放、以及按钮响应 案例# -*- coding: UTF-8 -*-#!/usr/bin/env pyt
- 国外纷纷传言IE8将是Internet Explorer的最后一个版本,这个猜测来源于Microsoft的CEO Steve
- python的requests它是python的一个第三方库,处理URL比urllib这个库要方便的多,并且功能也很丰富。【可以先看4,5表