第八讲：图（下） 8.1 最小生成树问题 8.1.1 最小生成树（Minimum Spanning Tree） 如图1所示。   图1 它是一棵树：无回路；|V|个顶点一定有|V|-1条边； 它是生成树：包含全部顶点；|V|-1条边都在图里。在图1中，第2/3/4个图都是图1的生成树，可以看出，生成树中任加一条边都一定构成回路。 最小：边的权重和最小。 显然可以得出，最小生成树存在<->图连通。 8.1.2 贪心算法 贪：每一步都要最好的。好：权重最小的边。 需要约束：只能用图里有的边；只能正…

第七节：最短路径问题 7.1 概述 最短路径问题的抽象： 在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。这条路径就是两点之间的最短路径。第一个顶点称为源点，最后一个顶点为终点。 问题分类： （1）单源最短路径问题：从某固定源点触发，求其到所有其他顶点的最短路径。又分为（有无向）有权图和（有无向）无权图两种。 （2）多源最短路径问题：求任意两顶点间的最短路径。 7.2 无权图的单源最短路 按照递增（非递减）的顺序找出到各个顶点的最短路。例如图1：   图1 我们以v3作为源点，与v…

第四周：网络爬虫之框架 第一讲：Scrapy爬虫框架 1.安装 执行pip install scrapy命令。 安装后小测：执行scrapy -h 2.Scrapy爬虫框架结构 爬虫框架是实现爬虫功能的一个软件结构和功能组件集合。爬虫框架是一个半成品，能够帮助用户实现专业网络爬虫。 Scrapy爬虫包括5+2个结构，如图1所示。   图1 它包括三条主要的数据流路径如图中的箭头所示： （1）从SPIDERS发送REQUESTS到ENGINE模块，然后到SCHEDULER，SCHEDULER负责对请求进行调…

第三周：网络爬虫之实战 第一节：Re（正则表达式）库入门 正则表达式是用来简洁表达一组字符串的表达式。它可以用来表达文本类型的特征。 正则表达式编译：将符合正则表达式语法的字符串转换成正则表达式特征。 1.正则表达式的语法 例如： P(Y|YT|YTH|YTHO)?N 正则表达式语法由字符和操作符构成。正则表达式的常用操作符见表1.1所示。 表1.1 正则表达式的常用操作符 操作符 说明 实例 . 表示任何单个字符 [] 字符集，对单个字符给出取值范围 [abc]表示a,b,c，[a-z]表示a到z单个字符 [^]…

第八周：程序设计方法学 8.1 实例13：体育竞技分析 1.自顶向下（设计） 它是解决复杂问题的有效方法，它将一个总问题表达为若干个小问题的组成形式，使用同样的方法进一步分解小问题，直至小问题可以用计算机简单明了解决。 2.自底向上（执行） 分单元测试，逐步组装，按照自顶向下相反的路径操作，直至系统各部分以组装的思路都经过测试和验证。 3.程序总体框架及步骤 （1）打印程序的介绍性信息式 （2）获得程序运行参数：proA，proB，n （3）利用球员A和B的能力值，模拟n局比赛。 （4）输出球员A和B获胜比赛的场次…

第七周：文件和数据格式化 7.1 文件的使用 1.文件的类型 文件是数据的抽象和集合：文件是存储在辅助存储器上的数据序列；文件是数据存储的一种形式；文件展现形态有文本文件和二进制文件。最根本上是二进制文件。 （1）文本文件：由单一特定编码组成的文件，如UTF-8编码。由于存在文件，也被看成存储着的长字符串。 （2）二进制文件：文件直接由比特0和1组成，没有统一字符编码。一般存在二进制0和1的组织结构，即文件格式。 2.文件的打开和关闭 文件处理步骤：打开-操作-关闭。 在不打开文件的时候，文件处于存储状态。当我们需…

第六节：图（上） 6.1 图 1.关于图 图表示的是“多对多”的关系。它包含： （1）一组顶点：通常用V（Vertex）表示顶点集合。 （2）一组边：通常用E（Edge）表示边的集合，表示顶点与顶点的关系： ①边是顶点对：(v,w)∈E，其中v,w∈V。这是一个双向的。 ②有向边：<v,w>，表示从v指向w的边（单行线）。 ③不考虑重边和自回路。 其抽象数据类型为： 类型名称：图（Graph） 数据对象集：一非空的顶点集合Vertex和一个边集合Edge，每条边用对应的一对顶点表示。 操作集：对于任意的…