CSE 30 Fall 2021 – Homework 10 Graphs图的Python作业答案

Python海龟宝典含200多个原创的用turtle模块制作的创意程序,原名《Python趣味编程200例》。准备参加全国创意编程与智能设计大赛的同学们可以用来做参考。

以下关于Graphs图的作业已完成,需要请联系本人微信scratch8(李兴球, 406273900@qq.com)

本人提供国内外大学生Python作业辅导,Python作业答疑,C语言作业辅导与答疑,大中小学生编程培训服务。

以下蓝色*线以下文本格式请忽视, 只是为了搜索引擎抓取的需要,及让您知道,本人已经解决了这问题。

*************************************************************************************

Before you turn this problem in, make sure everything runs as expected. First, restart the kernel (in the menubar, select Kernel      Restart) and then run all cells (in the menubar, select Cell                                                                       Run All).

Make sure you fill in any place that says YOUR CODE HERE or “YOUR ANSWER HERE”, as well as your name and collaborators below:

NAME = “” COLLABORATORS = “”

CSE 30 Fall 2021 – Homework 10 家庭作业10

Graphs 图

Instructions  介绍

Please disregard the YOUR NAME and COLLABORATORS above. They are put there atomatically by the grading tool. You can find instructions on how to work on a homework on Canvas. Here is a short summary:

Submitting your work 提供你的作业

To submit your work:

First, click on “Runtime > Restart and run all”, and check that you get no errors. This enables you to catch any error you might have introduced, and not noticed, due to your running cells out of order.

Second, download the notebook in .ipynb format (File > Download .ipynb) and upload the

.ipynb file to this form.

You can submit multiple times; the last submission before the deadline is the one that counts.

Homework format  家作格式

For each question in this notebook, there is: 每个问题

A text description of the problem. 都有一个描述

One or more places where you have to insert your solution. You need to complete every place marked:  在下面的位置写上你的代码

# YOUR CODE HERE

and you should not modify any other place.

One or more test cells. Each cell is worth some number of points, marked at the top. You should not modify these tests cells. The tests pass if no error is printed out: when there is a statement that says, for instance:

assert x == 2

then the test passes if x has value 2, and fails otherwise. You can insert a print(x) (for this case!) somewhere if you want to debug your work; it is up to you.

Notes:

Your code will be tested both according to the tests you can see (the assert statements you can see), and additional tests. This prevents you from hard-coding the answer to the particular questions posed. Your code should solve the general intended case, not hard-code the particular answer for the values used in the tests.

Please do not delete or add cells! The test is autograded, and if you modify the test by adding or deleting cells, even if you re-add cells you delete, you may not receive credit.

Please do not import modules that are not part of the standard library. You do not need any, and they will likely not available in the grading environment, leading your code to fail.

If you are inactive too long, your notebook might get disconnected from the back-end. Your work is never lost, but you have to re-run all the cells before you continue.

You can write out print statements in your code, to help you test/debug it. But remember: the code is graded on the basis of what it outputs or returns, not on the basis of what it prints.

TAs and tutors have access to this notebook, so if you let them know you need their help, they can look at your work and give you advice.

Grading

Each cell where there are tests is worth a certain number of points. You get the points allocated to a cell only if you pass all the tests in the cell. 每个单元有提供一些测试的地方,你可以自己测试下自己的代码能不能通过。

The tests in a cell include both the tests you can see, and other, similar, tests that are used for grading only. Therefore, you cannot hard-code the solutions: you really have to solve the essence of the problem, to receive the points in a cell.

Code of Conduct

Work on the test yourself, alone.  你可以自己单独测试

You can search documentation on the web, on sites such as the Python documentation sites, Stackoverflow, and similar, and you can use the results. 你可以在网上搜索文档资料,例如Python的文档站,或Stackoverflow及相似的网站,使用相关的结果。

You cannot share your work with others or solicit their help.

一个有向图G=(V,E)由一系列的顶点和边组成。

A (directed) graph G = (V , E) consists of a set of vertices (or nodes)      , and a set of edges

E ⊆ V × V .

图的一个例子

An example of a graph with V  = {a, b, c, d, e, f, g} and

E = {(a, b), (a, c), (a, d), (b, d), (c, a), (c, e), (d, b), (d, c), (f, g), (g, f)}.

如何表示图呢?  就像真实生活一样,直接用一系列顶点和边表示图就行了。

How should we represent a graph? A general principle of software development — really, of life — is: failing special reasons, always go for the simplest solution. So our first attempt consists in storing a graph exactly according to its definition: as a set of vertices and a set of edges.

class Graph(object):

def   init  (self, vertices=None, edges=None):

# We use set below, just in case somebody passes a list to the initializer. self.vertices = set(vertices or [])

self.edges = set(edges or [])

g = Graph(vertices={‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’},

edges={(‘a’, ‘b’), (‘a’, ‘c’), (‘a’, ‘d’), (‘b’, ‘d’),

(‘c’, ‘a’), (‘c’, ‘e’), (‘d’, ‘b’), (‘d’, ‘c’), (‘f’, ‘g’), (‘g’, ‘f’)})

不错,但是,如何显示图呢?

Great, but, how do we display graphs? And what can we do with them?

我们给图增加show方法,使用networkx这个库来显示图。

Let’s first of all add a method .show() that will enable us to look at a graph; this uses the library

 networkx.

import networkx as nx # Library for displaying graphs.

 

class Graph(object):

def   init  (self, vertices=None, edges=None):

# We use set below, just in case somebody passes a list to the initializer. self.vertices = set(vertices or [])

self.edges = set(edges or [])

def show(self):

g = nx.DiGraph() g.add_nodes_from(self.vertices) g.add_edges_from(self.edges) nx.draw(g, with_labels=True)

 

g = Graph(vertices={‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’},

edges={(‘a’, ‘b’), (‘a’, ‘c’), (‘a’, ‘d’), (‘b’, ‘d’),

(‘c’, ‘a’), (‘c’, ‘e’), (‘d’, ‘b’), (‘d’, ‘c’), (‘f’, ‘g’), (‘g’, ‘f’)})

g.show()

这和我们手工画的图相比还不太完美? 但它确实表明了此图的含义。

Ok, this is not nearly as pretty as what we generated by hand, but it will have to do.

 

One-Step Reachability and Graph  Representations

图的常见操作是什么? 基本操作是增加顶点和增加边。

What are conceivable operations on graphs? There are some basic ones, such as adding a vertex and adding an edge. These are easily taken care of.

 

import networkx as nx # Library for displaying graphs. class Graph(object):

def   init  (self, vertices=None, edges=None):

# We use set below, just in case somebody passes a list to the initializer. self.vertices = set(vertices or [])

self.edges = set(edges or [])

def show(self):

g = nx.DiGraph() g.add_nodes_from(self.vertices) g.add_edges_from(self.edges) nx.draw(g, with_labels=True)

def add_vertex(self, v): self.vertices.add(v)

def add_edge(self, e):

self.edges.add(e)

进一步地说,一张图表示一系列顶点的连接,一个通常的问题是是否一个点能通过一条边或更多的边到达另一个点?

Further, a graph represents a set of connections between vertices, so a very elementary question to ask is the following: if we are at vertex       , can we get to another vertex       by following one or more edges?

As a first step towards the solution, we want to compute the set of vertices reachable from    in one step, by following one edge; we call these vertices the successors of

写一个函数,叫g.successors(u),表示u点的后续顶点。                         .

Writing a function g.successors(u) that returns the set of successors of     is simple enough. Note that the code directly mimicks the mathematical definition:

Successors(u) = {v ∈ V ∣ (u, v) ∈ E} .

import networkx as nx # Library for displaying graphs. class Graph(object):

def   init  (self, vertices=None, edges=None):

# We use set below, just in case somebody passes a list to the initializer. self.vertices = set(vertices or [])

self.edges = set(edges or [])

 

def show(self):

g = nx.DiGraph() g.add_nodes_from(self.vertices) g.add_edges_from(self.edges) nx.draw(g, with_labels=True)

def add_vertex(self, v): self.vertices.add(v)

def add_edge(self, e): self.edges.add(e)

def successors(self, u):

“””Returns the set of successors of vertex u”””

return {v for v in self.vertices if (u, v) in self.edges}

g = Graph(vertices={‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’},

edges={(‘a’, ‘b’), (‘a’, ‘c’), (‘a’, ‘d’), (‘b’, ‘d’),

(‘c’, ‘a’), (‘c’, ‘e’), (‘d’, ‘b’), (‘d’, ‘c’), (‘f’, ‘g’), (‘g’, ‘f’)})

g.successors(‘a’)

 

But there’s a rub. The method successors, as written, requires us to loop over the whole set of vertices. Because self.edges is a set, represented as a hash table, once we have a pair (u, v), checking

(v, u) in self.edges

is efficient. But typically, graphs have a locality structure, so that each node is connected only to a small subset of the total vertices; having to loop over all vertices to find the successors of a vertex is a great waste. It is as if I asked you to what places you can get from San Francisco with a direct flight, and to answer, you started to rattle off all of the world’s cities, from Aachen, Aalborg, Aarhus,

…, all the way to Zürich, Zuwarah, Zwolle, and for each city you checked if there’s a flight from San Francisco to that city! Clearly not the best method.

Given that our main use for graphs is to answer reachability-type questions, a better idea is to store the edges via a dictionary that associates with each vertex the set of successors of the vertex. The vertices will simply be the keys of the dictionary.

 

import networkx as nx # Library for displaying graphs. class Graph(object):

def init (self, vertices=None, edges=None): self.s = {u: set() for u in vertices or []} for u, v in (edges or []):

self.add_edge((u, v))

def show(self):

g = nx.DiGraph() g.add_nodes_from(self.s.keys())

g.add_edges_from([(u, v) for u in self.s for v in self.s[u]]) nx.draw(g, with_labels=True)

def add_vertex(self, v): if v not in self.s:

self.s[v] = set()

def add_edge(self, e): u, v = e self.add_vertex(u) self.add_vertex(v) self.s[u].add(v)

@property

def vertices(self):

return set(self.s.keys())

def successors(self, u):

“””Returns the set of successors of vertex u””” return self.s[u]

g = Graph(vertices={‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’},

edges={(‘a’, ‘b’), (‘a’, ‘c’), (‘a’, ‘d’), (‘b’, ‘d’),

(‘c’, ‘a’), (‘c’, ‘e’), (‘d’, ‘b’), (‘d’, ‘c’), (‘f’, ‘g’), (‘g’, ‘f’)})

g.show() print(g.successors(‘a’))

Graph Reachability 图的可到达性

 

We now come to one of the fundamental graph algorithms, in fact, perhaps the most fundamental algorithm for graphs: computing the set of vertices reachable from a given starting vertex.

Exploring what is reachable from a graph vertex is a truly basic task, and variations on the algorithm can be used to answer related questions, such as whether a vertex is reachable from a given starting vertex.

The algorithm keeps two sets of vertices:  这个算法包括两个顶点的集合。

The set of open vertices: these are the vertices that are known to be reachable, and whose successors have not yet been explored.

The set of closed vertices: these are the vertices that are known to be reachable, and whose successors we have already explored.

Intially, the set of open vertices contains only the starting vertex, and the set of closed vertices is empty, as we have completed no exploration. Repeatedly, we pick an open vertex, we move it to the closed set, and we put all its successor vertices — except those that are closed already — in the open set. The algorithm continues until there are no more open vertices; at that point, the set of

reachable vertices is equal to the closed vertices.

If there is one graph algorithm that you must learn by heart, and that you should be able to write even when you hang upside down from monkeybars, this is it.

Let us write the algorithm as a function first.

def reachable(g, v):

“””Given a graph g, and a starting vertex v, returns the set of states reachable from v in g.”””

vopen = {v} vclosed = set()

while len(vopen) > 0: u = vopen.pop() vclosed.add(u)

vopen.update(g.successors(u) – vclosed) return vclosed

 

print(reachable(g, ‘a’))

print(reachable(g, ‘g’))

 

To visualize the algorithm, let us write a version where at each iteration, open vertices are drawn in red and closed ones in green

def reachable(g, v):

“””Given a graph g, and a starting vertex v, returns the set of states reachable from v in g.”””

vopen = {v} vclosed = set()

while len(vopen) > 0: u = vopen.pop() vclosed.add(u)

vopen.update(g.successors(u) – vclosed) return vclosed

 

reachable(g, ‘a’)

 

Breadth-First and Depth-First Search 宽度和深度优先搜索

Breadth First  广度优先搜索

In breadth-first search, we explore in concentric circles emanating from the starting point: first all vertices at distance 1, then all vertices at distance 2, and so on. In general, we explore all vertices at distance ≤ n before we explore vertices at distances    .

To implement breadth-first search, we store the open vertices vopen as a list rather than a set. We then explore vertices in the order they have been added to vopen : this ensures that vertices closer to the search origin are explored earlier than farther-away vertices.

The difference in code between reachability search, and its specialized breadth-first version, is minimal.

 

def breath_first(g, v):

“””Given a graph g, and a starting vertex v, returns the set of states reachable from v in g.”””

# vopen is a FIFO: first in, first out. Like a normal queue.

# we add elements from the end, and pop them from the beginning. vopen = [v]

vclosed = set()

while len(vopen) > 0:

u = vopen.pop(0) # Pop from the beginning vclosed.add(u)

# vopen.update(g.successors(u) – vclosed) for w in g.successors(u) – vclosed:

if w not in vopen:

vopen.append(w) # Add to the end return vclosed

gg = Graph(vertices={},

edges={(‘a’, ‘b’), (‘b’, ‘c’), (‘c’, ‘d’),

(‘a’, ‘u’), (‘u’, ‘v’), (‘v’, ‘w’), (‘u’, ‘z’)})

breath_first(gg, ‘a’)

We see that we explore    and      before any of their successors are explored, and similarly, we explore  ,            , and   before or             .

Depth-First Search   深度优先搜索

In depth-first search, we follow a path as long as possible, and only when we come to an end do we explore other nodes. In depth-first search, the most recent visited vertex, the one added last to the list of open vertices, is the one that will be explored first.

The difference in code from breadth-first search is minimal. In breadth-first search, the vertex to be explored next is the oldest among the open ones:

u = vopen.pop(0)

In depth-first search, it will be the newest among the open ones:

 

u = vopen.pop()

That’s the whole difference.

 

def depth_first(g, v):

“””Given a graph g, and a starting vertex v, returns the set of states reachable from v in g.”””

# vopen is a stack / LIFO: last in, first out. Like a stack.

# we add elements from the end, and pop them from the end. vopen = [v]

vclosed = set()

while len(vopen) > 0:

u = vopen.pop() # THIS is the difference: there is no 0 in the parentheses. vclosed.add(u)

# vopen.update(g.successors(u) – vclosed) for w in g.successors(u) – vclosed:

if w not in vopen: vopen.append(w)

return vclosed

depth_first(gg, ‘a’)

 

We see how in depth-first search we explore completely one side of the successors of   , consisting

 

z

of u, v, w,

, before exploring the other side b, c, d.

 

 

Problem 1: Returning the edges 第一个问题,返回所有边

 

In our latest implementation, we do not have direct access to the edges of the graph. In other words, for a graph g, we cannot do:

for (u, v) in g.edges:

 

We ask you to write an iterator over edges, to make the above code work. The iterator should yield the edges of the graph, one by one.

 

 

### An iterator for the set of edges

def graph_edges(self):

“””Yields the edges of the graph, one by one. Each edge is yielded as a pair of vertices (source, destination). “””

# YOUR CODE HERE

Graph.edges = property(graph_edges)

# YOUR CODE HERE

Here are some tests.

### 10 points: simple tests e = [(1, 2), (1, 3), (2, 3)]

g = Graph(vertices=[1, 2, 3], edges=e) assert set(g.edges) == set(e)

import types

# You need to build a generator, one of those things with the yield statement. assert isinstance(g.edges, types.GeneratorType)

Here are some randomized test.

### 10 points: random tests import random

for _ in range(10):

num_vertices = random.randint(4, 10)

num_edges = random.randint(1, num_vertices * num_vertices) vertices = random.sample(range(0, 1000), num_vertices)

edges = {(random.choice(vertices), random.choice(vertices)) for _ in range(num_edges)} g = Graph(vertices=vertices, edges=edges)

assert set(g.edges) == edges

Problem 2: Is a graph a tree?   第二个问题,图是一棵树吗?

A tree is a graph (V , E) with two special properties: Every vertex has at most one incoming edge.

Either there are no vertices, or there is a vertex with no incoming edges, called the root, from which all other vertices are reachable.

If the second property does not hold, incidentally, the graph is called a forest.

Write an is_tree function such that is_tree(g) returns True if the graph g is a tree, False otherwise.

### Implementation of tree test

 

def is_tree(g):

“””Returns True iff the graph is a tree.”””

# YOUR CODE HERE

### 10 points: Tests for `is_tree`

 

g = Graph(vertices=[1, 2, 3], edges=[(1, 2), (1, 3)])
assert is_tree(g)
g = Graph(vertices=[1, 2, 3], edges=[(1, 2), (2, 3), (1, 3)])
assert not is_tree(g)
g = Graph(vertices=[1, 2, 3], edges=[(1, 3), (2, 3)])
assert not is_tree(g)

### 10 points: More tests for `is_tree`

 

g = Graph() assert is_tree(g)

Problem 3: Reachability using either of two  graphs 第三个问题,两图的可到达性。

In this problem, you are given two graphs g1 , g2 , that share the same set of vertices. You have to write a function can_reach(v, g1, g2, w) , which returns True iff you can go from vertex v to vertex w using either edges of g1 or g2 . Note that to go from v to w , you can use one or more edges from g1 and one or more edges of g2 , mixed in any way you like. To solve the problem, you have to modify the reachability algorithms so that edges from either graph can be used.

Hint: Modify the reachability algorithm.

 

def can_reach(v, g1, g2, w):

“””Given two graphs g1, g2 that share the same vertices, and two verteces v, w, returns True if you can go from v to w using edges of either g1 or g2 (mixed any way you want) and False otherwise.”””

# YOUR CODE HERE

### 10 points: simple tests for can_reach

vertices = {1, 2, 3, 4, 5, 6, 7}

g1 = Graph(vertices=vertices, edges=[(1, 2), (3, 4)])

g2 = Graph(vertices=vertices, edges=[(2, 3), (4, 5), (6, 7)]) assert can_reach(1, g1, g2, 2)

assert can_reach(1, g1, g2, 3) assert can_reach(1, g1, g2, 4) assert can_reach(1, g1, g2, 5) assert not can_reach(1, g1, g2, 6) assert not can_reach(1, g1, g2, 7)

### 10 points: more advanced tests for can_reach vertices = set(range(100))

# g1 edges go from n to 2n, g2 edges go from n to 3n.

g1 = Graph(vertices=vertices, edges=[(n, 2 * n) for n in range(100) if 2 * n < 100]) g2 = Graph(vertices=vertices, edges=[(n, 3 * n) for n in range(100) if 3 * n < 100]) assert can_reach(1, g1, g2, 6)

assert can_reach(1, g1, g2, 24) assert can_reach(1, g1, g2, 32) assert can_reach(1, g1, g2, 9) assert not can_reach(1, g1, g2, 15) assert not can_reach(1, g1, g2, 60) assert can_reach(5, g1, g2, 15) assert can_reach(5, g1, g2, 30)

 

提供国内外大学生Python作业辅导,Python作业答疑,C语言作业辅导与答疑,有偿服务。

本站所有作品,教程等皆为原创,版权所有。只供个人及单位内部研究使用,对外展示或传播必需经本站同意,且注明来自本站。培训机构等用本站资源培训学生,需经本站授权。一旦付款,表示同意本站知识付费原则:数字商品,不支持退款。亦可直接向微信号scratch8付款购买。入住QQ群:225792826 和爱好者共同交流,并且能下载免费提供的Python资源(需提供真实姓名才可入群)
李兴球的博客_Python创意编程技术前沿_pygame » CSE 30 Fall 2021 – Homework 10 Graphs图的Python作业答案

李兴球Python微信公众号文章列表

Python游戏海龟模块教程说明书与案例若干免费发放

爱的纪念_Python创意情景动画源代码解析

少儿Python编程到底学些什么?这些代码或许回答了问题.

Python编程家长会花絮_萍乡中小学Python家长会现场

火星路上等着你_少儿从小学什么最好呢?

国家大力整顿教育培训机构,Scratch或Python少儿编程还有得教吗?

鸿蒙系统支持Python开发_可视化编程特别兴趣小组

Scratch作品转Python作品_小猴接桃

python海龟数据可视化。第七次全国人口普查历年数据图表

你的孩子Python编程学到哪个阶段了?给孩子报编程的家长,务必仔细一读。

五一神女来对话,看看她们聊什么?赠Python教案等。

五一快乐有大礼,告诉大家我是如何上Python课的。

Python名堂多,趣味到处有,劈开机械手,帧帧是图片。速算达人之猫狮大战正在进行。 逐字动画不独享,自动生成皆有它。2行代码自动生成字幕gif动画。 Python之潮来临,我在安源区教师科技创新能力的Python讲座

小心你的Python程序,它会是你的一面镜子。小方块闯迷宫.py源代码简析。送Scratch算法集。?

铃儿响钉铛_音效怎能忘_Python配音之Pygame混音器

人面桃花相映红_winsound模块简介

《Python昨晚我想你了》_开源的游戏海龟模块实例案例浅析

《八猫联动初体验》_来自游戏海龟模块的问候

喜爱春天的人儿啊 心地纯洁的人_Python逐行像素显示

旋转之三叶炫彩扇_蟒蛇与海龟的表演

彩虹欢迎字幕_三模合体滚图形

《Python海龟宝典》简介

100%错误的算法还在用,明明没有错别字,说我有11个错别字

奇怪的Python代码,谁能帮我解释一下??

人造地球系统让人类文明充满整个宇宙之Python32768版

深夜,是什么把你的大脑搞成一团浆糊!再谈少儿编程!

5线城市萍乡的少儿Python寒假班学的是什么内容?

关于纯少儿编程课程进化的自然选择

Python海龟画图经典作品_国庆中秋双重喜庆源代码免费下载

海龟为什么要自杀!turtle制作游戏秘籍之一

朋友,你是否知道我在仰望着你_Python神笔马良案例集

酷酷的爆炸效果_Python海龟画图不仅仅是画图

虫子满屏爬_三bug多线程示例程序浅析 少儿Python视频课程A级简介

给的gif图片加文字水印_拆帧与合帧(免费下载180个Python创意源码

用Python制作酷炫图形之如意金箍棒_颜色增加模块应用

简单的用Python做酷炫图形与动画

sb3转exe,sb3素材提取器,编程小子apk, 未公开的pygame游戏集/scratch/python少儿编程免费下载集合

夜幕下的霓虹

学本领,探索更大的世界!

李兴球博客 风火轮编程主页