计算思维与算法入门

(副标题)：无 ;

(作者): 赵军（夏非彼签 ;

内容简介：

​ 2.8　图简介
树结构用于描述节点与节点之间“层次”的关系，而图结构却是讨论两个顶点之间“连通与否”的关系，在图中连接两个顶点的边，如果填上加权值（也可以称为成本），这类图就被称为“网络”。图在生活中的应用非常普遍，如图2-68所示。

图2-68　图的应用在生活中非常普遍
图除了应用在算法和数据结构的最短路径搜索、拓扑排序中之外，还能应用在系统分析中以时间为评审标准的性能评审技术（Performance Evaluation and Review Technique，PERT），或者像“IC电路设计”“交通网络规划”等应用。注意：在图论中，图的定义有特定的含义。
城市地铁路线的规划就是图的应用之一，如图2-69所示。

图2-69　城市地铁路线的规划就是图的应用之一
图的理论（简称图论）起源于1736年，是一位瑞士数学家欧拉（Euler）为了解决“哥尼斯堡”问题所想出来的一种理论，就是著名的“七桥问题”。简单来说，就是有7座横跨4个城市的大桥。欧拉所思考的问题是这样的，“是否有人在每一座桥梁只经过一次的情况下，能够把所有地方都走过一次且回到原点。”图2-70所示为“七桥问题”的示意图。

图2-70　“七桥问题”示意图
欧拉当时使用的方法是以图结构来进行分析。他先以顶点表示城市，以边表示桥梁，把连接每个顶点的边数称为该顶点的度数。我们将以如图2-71所示的简图来表示“七桥问题”。

图2-71　以图的抽象方式表示七桥问题——欧拉环
最后欧拉得出一个结论：“当所有顶点的度数都为偶数时，才能从某顶点出发，经过每条边一次，再回到起点。”也就是说，在图2-71中，每个顶点的度数都是奇数，所以欧拉思考的问题是不可能发生的。这个理论就是有名的“欧拉环”（Eulerian Cycle）理论。
但是，如果条件改成从某顶点出发，

目录预览：

​ 计算思维与算法入门
第1章 程序设计与计算思维
1.1 认识计算思维
1.1.1 分解
1.1.2 模式识别
1.1.3 模式概括与抽象
1.1.4 算法
1.2 算法的条件
1.3 课后习题
第2章 常用数据结构与算法
2.1 认识数据结构
2.2 常见的数据结构
2.3 矩阵与深度学习
2.3.1 稀疏矩阵
2.3.2 矩阵相加算法
2.3.3 矩阵相乘算法
2.3.4 转置矩阵
2.4 链表
2.4.1 单向链表的串接算法
2.4.2 单向链表节点的删除算法
........