最短路径：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径。 1.单源点到其余各顶点的最短路径 给定带权有向图G和源点v，求从v到G中其余各顶点的最短路径。 迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法。 Dijkstra算法： 基本思想：这个算法的过程有比prim算法的过程稍微多一点点步骤，但是思想确实巧妙的，也是贪心原理，它的目的 […]

一、拓扑排序 什么是拓扑排序？简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。 回顾离散数学中关于偏序和全序的定义： 若集合X上的关系R是自反的，反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序，如果对每个x，y∈X必有xRy或yRx，则称R是集合X上的全序关系。 直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较下 […]

一、最小生成树的概念 生成树：所有顶点均由边连接在一起，但不存在回路的图叫该图的生成树。 一个图可以有许多棵不同的生成树。 所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图   最小生成树：生成树的每条边上的权值之和最小。 构成最小生成树可以有多种算法。其中多数算法利用了最小生成树的下列一种简称为MST的性质：假设N=(V,{E})是一个连通图， […]

广度优先搜索(Breadth-First-Search)和深度优先搜索(Deep－First－Search)是搜索策略中最经常用到的两种方法,特别常用于图的搜索.其中有很多的算法都用到了这两种思想,比如:Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。 一、DFS算法 DFS的思想： 顾名思义，深度优先搜索所遵循的策略就是尽可能“深”的在图中进行搜索，对于 […]

一、哈夫曼树的概念 先来理解几个概念： 路径：树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路径长度：路径上的分支数目称作路径长度。 树的路径长度：从树根到每一个结点的路径长度之和。、 结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和。 通常记作：   公式中，Wk为第k个叶子结点的权值；Lk为该结点 […]

已知一棵二叉树的先序遍历为： ABDGCEFH 中序遍历为： DGBAECHF 求二叉树后序遍历。 分析：先序遍历序列的第一个字符为根结点。对于中序遍历，根结点在中序遍历序列的中间，左边部分是根结点的左子树的中序遍历序列，右边部分是根结点的右子树的中序遍历序列。   先序：ABDGCEFH  →  A   BDG   CEFH […]

字符串匹配是我们经常遇到的问题，就是在原字符串中查找子串在原字符串中首次出现的位置。 1. Brute force. 首先我们能想到的，也是最传统的做法就是暴力搜索。 利用计数指针i和j指示主串S和模式串T中当前正待比较的字符位置，从主串S的第pos个字符起和模式的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较。直到模式T中的每个字符依次和主串S中的 […]

● 初识计算机网络computer network 1.概念： 简单定义就是一些相互连接的、自治的计算机的集合。 目前对计算机网络的定义是：计算机网络是指把若干台地理位置不同且具有独立功能的计算机，通过通信设备和线路相互连接起来，以实现数据传输和资源共享的一种计算机系统。 2.组成元素： 网络的组成元素主要分为两大类，即网络节点(又称网络单元)和通信链路。网络节点又分为端节点和转接节点。通信链路是 […]

有些东西就直接略过了，有的打算另开篇幅来分析。 ● 数据模型 第一类是概念模型。第二类是逻辑模型和物理模型。 数据模型通常由数据结构、数据操作和完整性约束组成。 概念模型： 1.实体：客观存在并可相互区别的事物称为实体。 2.属性：实体所具有的某一特征称为属性。 3.码：唯一标识实体的属性集称为码。 4.域：域是一组具有相同数据类型的值的集合。 5.实体型：用实体名及其属性名集合来抽象和刻画同类实 […]

1

　　Sublime text是开发代码编辑的神器 ，编辑器界面优美，操作速度快速。而且Sublime Text是一款跨平台的编辑器，再也不用为换平台而找不到合适的、熟悉的编辑器担忧了。 　　Sublime Text 是一款具有代码高亮、语法提示、自动完成且反应快速的编辑器软件，不仅具有华丽的界面，还支持插件扩展机制，用她来写代码，绝对是一种享受。     & […]