美国留学生Python项目作业与答案:Graphs图,判断图是树和数孤岛数量

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

以下全是问题描述,需要答案请联系博客微信pythonxia

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?
很好,可是我们如何显示图呢? 我们还能玩些啥?
Let’s first of all add a method .show() that will enable us to look at a graph; this uses the library networkx.
让我们添加一个show方法看看图到底长啥样,使用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()

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 𝑣 .
作为求解的第一步,我们希望通过沿着一条边,一步计算从𝑣可到达的顶点集;我们称这些顶点为𝑣的后继顶点。
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:
编写一个函数g.successivers(u)来返回一组𝑢的后续顶点非常简单。请注意,代码直接模拟了数学定义:
Successors(𝑢)={𝑣∈𝑉∣(𝑢,𝑣)∈𝐸}.

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),
这有个问题就是,上面的方法遍历了所有的顶点,由于self.edges是个集合,用哈希表来存储的,
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.
from collections import defaultdict

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。下面写了一个可视化的函数,可以显示。

import matplotlib.pyplot as plt
def color_draw(g, vopen, vclosed):
    gg = nx.DiGraph()
    gg.add_nodes_from(g.vertices)
    gg.add_edges_from([(u, v) for u in g.vertices for v in g.successors(u)])
    node_colors = ''.join([('r' if v in vopen else 'g' if v in vclosed else 'b')
                           for v in g.vertices])
    nx.draw(gg, with_labels=True, node_color=node_colors)
    plt.show()

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()
    color_draw(g, vopen, vclosed)
    while len(vopen) > 0:
        u = vopen.pop()
        vclosed.add(u)
        vopen.update(g.successors(u) - vclosed)
        color_draw(g, vopen, vclosed)
    return vclosed

reachable(g, 'a')

Great! Let’s now endow our graph with a method that yields the vertices reachable from any given starting vertex.

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 true iff one can get from vertex v to vertex u by following
        one edge."""
        return self.s[u]

    def __eq__(self, other):
        """We need to define graph equality."""
        if self.vertices != other.vertices:
            return False
        for v, d in self.s.items():
            if d != other.s[v]:
                return False
        return True

    def __repr__(self):
        r = "Graph:"
        for v in self.vertices:
            r += "\n %r : %r" % (v, self.s.get(v))
        return r

    def show(self):
        g = nx.DiGraph()
        g.add_nodes_from(self.vertices)
        g.add_edges_from([(u, v) for u in self.vertices for v in self.s[u]])
        nx.draw(g, with_labels=True)

    def add_vertex(self, v):
        self.vertices.add(v)
        # We must be careful not to overwrite the successor relation
        # in case v might already be present in the graph.
        self.s[v] = self.s.get(v, set())

    def add_edge(self, e):
        """Adds an edge e = (u, v) between two vertices u, v.  If the
        two vertices are not already in the graph, adds them."""
        u, v = e
        self.vertices.update({u, v})
        # Initializes the successor function if needed.
        self.s[u] = self.s.get(u, set()) | {v}
        self.s[v] = self.s.get(v, set())

    def successors(self, u):
        """Returns the set of successors of a vertex u"""
        return self.s[u]

    def reachable(self, v):
        """Returns the set of vertices reachable from an initial vertex v."""
        vopen = {v}
        vclosed = set()
        while len(vopen) > 0:
            u = vopen.pop()
            vclosed.add(u)
            vopen.update(self.s[u] - vclosed)
        return vclosed

Testing the implementation

This seems to be a reasonable implementation. Let us do some tests, to check that everything works as expected. The nose tools are very handy for testing. We have written a _check function that enables us to test whether the definition of a graph is self consistent. Writing such consistency checks is very useful. In development, we may call them often. In production code, we may choose to call them at key points in the code, to prevent the propagation of errors to distant places in the code.

import random
vertices = list('abcdefghilmnopqrstuvz')

def random_vertices():
    """Returns a set of random vertices."""
    return set(random.choices(vertices, k=12))

def random_edges(vs):
    """Returns a set of random edges, given a set of vertices."""
    vxv = [(u, v) for u in vs for v in vs]
    return set(random.choices(vxv, k=min(len(vxv), 50)))

def random_graph():
    vs = random_vertices()
    e = random_edges(vs)
    return Graph(vertices=vs, edges=e)

for _ in range(100):
    g = Graph()
    vs = random_vertices()
    es = random_edges(vs)
    for e in es:
        g.add_edge(e)

for _ in range(100):
    vs = random_vertices()
    es = list(random_edges(vs))
    g1 = Graph(vertices=vs, edges=es)
    g2 = Graph(vertices=vs)
    g3 = Graph(vertices=vs)
    esp = es[:] # Creates a copy.
    random.shuffle(esp)
    for e in es:
        g2.add_edge(e)
    for e in esp:
        g3.add_edge(e)
    assert g1 == g2
    assert g1 == g3

Graph Operations

图的操作
What are useful, general graph operations we may implement? Here are a few.

Union and intersection.
Induced: given a graph 𝐺=(𝑉,𝐸) and a set of vertices 𝑈 , we return the graph with set of vertices 𝑉∩𝑈 and set of edges 𝐸∩(𝑉∩𝑈×𝑉∩𝑈) . This is the portion of the original graph that only involves vertices in V.
Difference: Remove, from a graph 𝐺 , all vertices in a specified set 𝑈 , along with the edges that have an endpoint in 𝑈 .
We will have you implement graph union.

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

    @property
    def edges(self):
        return {(u, v) for u, d in self.s.items() for v in d}

    def successors(self, u):
        """Returns the set of successors of vertex u"""
        return self.s[u]

    def __eq__(self, other):
        """We need to define graph equality."""
        if self.vertices != other.vertices:
            return False
        for v, d in self.s.items():
            if d != other.s[v]:
                return False
        return True

    def __repr__(self):
        r = "Graph:"
        for v in self.vertices:
            r += "\n %r : %r" % (v, self.s.get(v))
        return r

    def show(self):
        g = nx.DiGraph()
        g.add_nodes_from(self.vertices)
        g.add_edges_from([(u, v) for u in self.vertices for v in self.s[u]])
        nx.draw(g, with_labels=True)

    def add_vertex(self, v):
        self.vertices.add(v)
        # We must be careful not to overwrite the successor relation
        # in case v might already be present in the graph.
        self.s[v] = self.s.get(v, set())

    def add_edge(self, e):
        """Adds an edge e = (u, v) between two vertices u, v.  If the
        two vertices are not already in the graph, adds them."""
        u, v = e
        self.vertices.update({u, v})
        # Initializes the successor function if needed.
        self.s[u] = self.s.get(u, set()) | {v}
        self.s[v] = self.s.get(v, set())

    def successors(self, u):
        """Returns the set of successors of a vertex u"""
        return self.s[u]

    def reachable(self, v):
        """Returns the set of vertices reachable from an initial vertex v."""
        vopen = {v}
        vclosed = set()
        while len(vopen) > 0:
            u = vopen.pop()
            vclosed.add(u)
            vopen.update(self.s[u] - vclosed)
        return vclosed

    def __and__(self, g):
        """Returns the intersection of the current graph with a
        specified graph g."""
        return Graph(vertices=self.vertices & g.vertices,
                     edges=self.edges & g.edges)

    def induced(self, vertex_set):
        """Returns the subgraph induced by the set of vertices vertex_set."""
        common_vertices = vertex_set & self.vertices
        gg = Graph(vertices = common_vertices)
        for v in common_vertices:
            gg.s[v] = self.s[v] & common_vertices
        gg._check()
        return gg

Question 1: Is a graph a tree?

问题一,判断图是否是一颗树,需要答案请联系微信pythonxia

A tree is a graph (𝑉,𝐸) 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 property that has value True if the graph is a tree, and has value False otherwise.

#@title Implementation of tree test

def graph_is_tree(self):
    """Returns True iff the graph is a tree."""
    ### YOUR CODE HERE

Graph.is_tree = property(graph_is_tree)
 ### 10 points: Tests for tree. 

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

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

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

g = Graph(vertices=['a', 'b'], edges=[('a', 'b')])
assert g.is_tree

g = Graph(vertices=['a', 'b'], edges=[('a', 'b'), ('b', 'a')])
assert not g.is_tree

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

g = Graph()
assert g.is_tree

g = Graph(vertices=['a', 'b', 'c', 'd'], edges=[('a', 'b'), ('c', 'd')])
assert not g.is_tree

g = Graph(vertices=['a', 'b', 'c', 'd'], edges=[('a', 'b'), ('b', 'c'), ('c', 'd')])
assert g.is_tree

Question 2: Count the Islands

问题2,数孤岛,需要答案请联系博主微信pythonxia
You need to write a function count_the_islands, which counts the islands of 1s in a matrix whose elements can be 0 or 1. Two 1s belong to the same island if they are adjacent horizontally or vertically. For example, the matrix:

000000000
001000001
011110011
001100110
000000000
contains two islands:

………
..1……
.1111….
..11…..
………
and

………
……..1
…….11
……11.
………
As another example, the matrix:

00010000
00001100
00000000
contains two islands, one containing one 1, the other containing two 1s, as being adjacient via the diagonal only does not count.

Your task is simple: write a function that, given as input a numpy matrix containing 0/1, returns an integer, indicating the number of islands. You should not modify the matrix that is passed to you.

Hint
There are two ways to solve this problem.

The first way consists in translating the matrix into a graph, where each node represents a position in the matrix containing a 1. For instance, the second matrix above would be translated into a graph with nodes (0, 3), (1, 4), (1, 5). Edges connect adjacent nodes. You can then use the algorithm for graph reachability to tell which nodes belong to the same island.

The second way consists in implementing the reachability algorithm on top of the matrix directly.

You can choose either way.

Note that if you have a matrix a as above,

np.argwhere(a)
returns the positions in a that are 1.

import numpy as np

# You can define here any auxiliary function you wish. 
### YOUR CODE HERE

def count_the_islands(m):
    """Returns the number of islands in the matrix m."""
    # My solution takes 14 lines of code. 
    ### YOUR CODE HERE
### 4 points: simple tests. 

a = np.array([
    [0, 0, 1, 1, 0, 0],
    [0, 1, 1, 0, 0, 1],
    [0, 1, 0, 0, 1, 1]
])
assert count_the_islands(a) == 2

a = np.zeros((10, 12))
assert count_the_islands(a) == 0

a = np.ones((10, 12))
assert count_the_islands(a) == 1

a = np.array([
    [0, 0, 1, 1, 0, 0],
    [0, 1, 1, 0, 0, 1],
    [0, 1, 0, 0, 1, 1],
    [0, 1, 1, 0, 0, 1],
    [0, 1, 0, 0, 1, 1]

])
assert count_the_islands(a) == 2
assert count_the_islands(1 - a) == 2

a = np.identity(7)
assert count_the_islands(a) == 7
assert count_the_islands(a) == 7
assert (a == np.identity(7)).all()

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

李兴球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少儿编程免费下载集合

夜幕下的霓虹

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

李兴球博客 风火轮编程主页
error: Content is protected !!