20220606数据结构绿皮书读书笔记

 

 

 

20220606数据结构绿皮书读书笔记

12 图

不建议沉浸于算法实现的细节,而是要理解算法的核心思想

12.1 数学背景

图G由顶点集合V和不同顶点之间的关系集E组成,E的元素称为边。对于边e=(v,w),称v,w lie on e,e incident with v,w。如果关系是无序的则G称之为无向图反之为有向图,不加修饰的图通常指无向图

12.2 计算机表示

所有都存,顶点集合+邻接矩阵(二维数组)
只存边,顶点集合+邻接表(基于数组或链表)

12.3 图的遍历

深度优先,用栈
广度优先,用队列

12.4 拓扑排序

从入度为0的节点开始遍历

12.5 最短路径

有向加权图上搜索最短路径
增广算法、染色算法?
不知道怎么翻译,思路是使用距离表记录中间结果,总之每轮尝试尽可能扩大路径的范围,选取总和最小的结果

12.6 最小生成树

Prim算法

12.7 图的数据结构

抽象定义,同之前的结构,只要能记录原始数据,就能表示一个图,不宜拘泥于物理结构

这本书后面就是波兰式的应用了,上学时候做过了科学计算器,这里不再继续读了
最后一张是数学基础,如有穷无穷数列的和、对数函数、排列组合之类的数学基础

结束啦~~~~
下一本书看现代密码学

 

0 Comments
Leave a Reply