最短路径：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径。 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中的 […]