作者: van_fantasy

老二次元了

55 篇文章

《数据结构》期末提纲之图的连通性问题
1.无向图的连通分量 直接说概念有点抽象,直接举例子:(如图所示) 如果对上图进行遍历,无论采用何种遍历方式,都会遍历两轮,形成{A,B,C,D}与{E,F,G}两个点集。实质上是对两个点集构成的的两个“子图”进行遍历,这两个“子图”就是该非连通图的两个连通分量。 求一个图的连通分量个数很简单,对每个点进行DFS或BFS,边遍历便标记,完成一次遍历…
《数据结构》期末提纲之DFS与BFS
1.广度优先搜索(BFS) 简介 宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,…
《数据结构》期末提纲之图的存储
1.图的简介 图(Graph)是表示物件与物件之间的关系的数学对象,是图论的基本研究对象。一个不带权图中若两点不相邻,邻接矩阵相应位置为0,对带权图(网),相应位置为∞。对于一个拥有n个顶点的无向连通图,它的边数一定多于n-1条。若从中选择n-1条边,使得无向图仍然连通,则由n个顶点及这 n-1条边(弧)组成的图被称为原无向图的生成树。(百度百科)…
《数据结构》期末提纲之Huffman树
1.名词解释 路径与权 从起始节点到目标节点所经过的分支序列为路径,所经分支数目为路径长,若给节点赋值,则称此值为权。 节点的带权路径长 节点的带全路径唱等于该节点的权与根节点到该节点的路径长之积。 树的带权路径长(WPL) 树的带权路径长为所有叶子节点的带权路径长之和。 图示(今天带了数位板就直接用笔画了(懒)) 2.Huffman树简介 给定n…
《数据结构》期末提纲小结
1.线性表 顺序表(跳转CSDN,考后搬运回来) 链表(跳转CSDN,考后搬运回来) 2.栈与队列 栈(跳转CSDN,考后搬运回来) 队列(跳转CSDN,考后搬运回来) 3.树与二叉树 二叉树(跳转CSDN,考后搬运回来) 树与森林(跳转CSDN,考后搬运回来) Huffman树 4.图 图的存储 BFS与DFS 图的连通性问题 最小生成树 拓扑排…
隐藏
变装