最短路径:从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径。 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.实体型:用实体名及其属性名集合来抽象和刻画同类实 […]

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

第 14 页,共 30 页« 最新...5...1213141516...202530...最旧 »