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