维护公告 公告 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，边遍历便标记，完成一次遍历…

1.广度优先搜索（BFS） 简介 宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，…

1.图的简介 图（Graph）是表示物件与物件之间的关系的数学对象，是图论的基本研究对象。一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为∞。对于一个拥有n个顶点的无向连通图，它的边数一定多于n-1条。若从中选择n-1条边，使得无向图仍然连通，则由n个顶点及这 n-1条边（弧）组成的图被称为原无向图的生成树。（百度百科）…

1.名词解释 路径与权 从起始节点到目标节点所经过的分支序列为路径，所经分支数目为路径长，若给节点赋值，则称此值为权。 节点的带权路径长 节点的带全路径唱等于该节点的权与根节点到该节点的路径长之积。 树的带权路径长(WPL) 树的带权路径长为所有叶子节点的带权路径长之和。 图示（今天带了数位板就直接用笔画了（懒）） 2.Huffman树简介 给定n…

1.线性表 顺序表（跳转CSDN，考后搬运回来） 链表（跳转CSDN，考后搬运回来） 2.栈与队列 栈（跳转CSDN，考后搬运回来） 队列（跳转CSDN，考后搬运回来） 3.树与二叉树 二叉树（跳转CSDN，考后搬运回来） 树与森林（跳转CSDN，考后搬运回来） Huffman树 4.图 图的存储 BFS与DFS 图的连通性问题 最小生成树 拓扑排…