夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色
【置顶】维护公告&本站概况&须知&BUG
维护公告 公告 2020年2月27日起,博客页不再作为主页。 本站域名重新分配后,出现了以往博客图片丢失的问题,现已修复完成。 近期维护计划 由于本站服务器性能低下,计划将本站CMS替换为typecho。时间未定,我有时间的时候做。需要停服维护。 待维护项目 暂无 建设中项目 资源站在建,预计要很长时间。 0.致歉 一月底时,本站由于数据库错误崩溃…
《数据结构》期末提纲之拓扑排序
1.拓扑排序简介 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个…
《数据结构》期末提纲之最短路
1.例题 本文以HDU2544为例: 题目大意 给出一个带权无向图,求其从起点到终点的最短路径。 2.Dijkstra算法 算法思路 Dijkstra算法算一种贪心算法,通过不断选择中间点找出起点到各个点的最短路(这个操作被称为松弛)。该算法常用于求单源图的最短路,具体见伪代码。 伪代码 Dijkstra(){ 取邻接表起点行作为最短路记录数组; …
《数据结构》期末提纲之最小生成树
版权声明:本文前两个图片出自这里,图片所属博主允许转载。本文其他部分若未说明即为原创。 1.最小生成树简介 在一给定的无向图G=(V,E)中,(u,v)代表连接顶点u与顶点v的边,而w(u,v)代表此边的权重,若存在T为E的子集且为无循环图,使得图中路径权值和最小,则此T为G的最小生成树。 2.Prim算法 Prim算法相当于将点一个一个增加,算法…
《数据结构》期末提纲之图的连通性问题
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 图的连通性问题 最小生成树 拓扑排…
测试文章
这是一个测试文章哦 咱们用Markdown写 #include<iostream> using namespace std; int main() { cout << "hello world" << endl; return 0; } 可还行!之后会把博客搬运到这里哦~
隐藏
变装