图的表示方法 最常用的表示图的方法是邻接矩阵与邻接表。 邻接矩阵表示法 设G是一个有n(n>0)个顶点的图,V(G)={v1, v2, …, vn},则邻接矩阵AG是一个n阶二维矩阵。在该矩阵中,如果vi至vj有一条边,则(i, j)项的值为1,否则为0,即: 邻接矩阵的实现很简单: int edge[n][n]={ 0}; for(...){ ... //无向图的邻接矩阵表示 edge[node1][node2]=1; edge[node2][node1]=1; } 1 2 3 4 5 6 7 8 邻接表表…

2021年5月4日 0条评论 3点热度 阅读全文

 字符串匹配是计算机的基本任务之一。   举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"?   许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。它以三个发明者命名,起头的那个K就是著名科学家Donald Knuth。   这种算法不太容易理解,网上有很多解释,但读起来都很费劲。直到读到Jake Boxer的文章,我才真正理解这种算法。下面,我用自己的语言,试图写一篇比较好懂的KMP算法解释…

2021年5月4日 0条评论 2点热度 阅读全文

1 Dijkstra算法 问题描述:在一个图中,给定指定顶点,求该顶点到其它顶点的最短距离。 如图所示:这是一个有向图,现在要求解从顶点V1到其它顶点的最短距离。以上图为例,利用Dijkstra算法求解最短距离。 步骤: (1)将所有顶点分为两组,一组是未知的即为S,一组是已知的记为W。开始时,S={V1,V2,V3,V4,V5,V6,V7},W={}; (2)首先选择顶点V1到其它顶点中距离最短的顶点为已知顶点。显然V1->v1=0为最小值。这时S={V2,V3,V4,V5,V6,V7},W={V1}; 更…

2021年5月4日 0条评论 2点热度 阅读全文

图的表示方法 最常用的表示图的方法是邻接矩阵与邻接表。 邻接矩阵表示法 设G是一个有n(n>0)个顶点的图,V(G)={v1, v2, …, vn},则邻接矩阵AG是一个n阶二维矩阵。在该矩阵中,如果vi至vj有一条边,则(i, j)项的值为1,否则为0,即: 邻接矩阵的实现很简单: int edge[n][n]={ 0}; for(...){ ... //无向图的邻接矩阵表示 edge[node1][node2]=1; edge[node2][node1]=1; } 1 2 3 4 5 6 7 8 邻接表表…

2021年5月4日 0条评论 1点热度 阅读全文

    动态规划相信大家都知道,动态规划算法也是新手在刚接触算法设计时很苦恼的问题,有时候觉得难以理解,但是真正理解之后,就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章,大多都是叙述概念,讲解原理,让人觉得晦涩难懂,即使一时间看懂了,发现当自己做题的时候又会觉得无所适从。我觉得,理解算法最重要的还是在于练习,只有通过自己练习,才可以更快地提升。话不多说,接下来,下面我就通过一个例子来一步一步讲解动态规划是怎样使用的,只有知道怎样使用,才能更好地理解,而不是一…

2021年5月4日 0条评论 1点热度 阅读全文

应用背景 学生选修课程问题 顶点——表示课程 有向弧——表示先决条件,若课程i是课程j的先决条件,则图中有弧(i,j) 学生应按怎样的顺序学习这些课程,才能无矛盾、顺利地完成学业——拓扑排序 拓扑序列是有向无环图中各顶点构成的有序序列。该序列满足如下条件:如果图中一顶点vi到另一顶点vj存在一条路径,那么vj在此图的拓扑排序序列中位于vi之后。 有向无环图(DAG)和 AOV网 有向无环图”(Directed Acyclic Graph,简称DAG AOV网 (Activity On Vertex network)…

2021年5月4日 0条评论 1点热度 阅读全文

图的遍历 图的遍历(Traversing Graph):从图的某一顶点出发,访遍图中的其余顶点,且每个顶点仅被访问一次。 图的遍历算法是各种图的操作的基础。但图的遍历存在以下特点: ◆ 复杂性:图的任意顶点可能和其余的顶点相邻接,可能在访问了某个顶点后,沿某条路径搜索后又回到原顶点,而有些顶点却还没有被遍历到的情况。 ◆ 解决办法:在遍历过程中记下已被访问过的顶点。设置一个辅助向量Visited1…n,其初值为0,一旦访问了顶点vi后,使Visited[i]为1或为访问的次序号。 图的遍历算法有深度优先搜索算法和广…

2021年5月4日 0条评论 1点热度 阅读全文

前言        字典树又称单词查找树,它是一种树形结构,是一种哈希树的变种,典型应用是用于统计,保存大量的字符串(但不仅限于字符串),统计以是否有以某字符串最为前缀的字符串,有的话有多少,某字符串出现了多少次等,所以经常被搜索引擎系统用于文本词频统计。        它与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,…

2021年5月3日 0条评论 5点热度 阅读全文

自己接触和了解过的查找算法总结起来分为3个吧: 1. 静态查找(主要是二分查找,效率较高) 2. 动态查找(二叉查找树) 3. 哈希表 首先来说二分查找吧! 基本思想:假设在一个已经排好序的有序序列(N个元素,升序排列),首先让序列N中中间的关键字与需要查找的关键字进行比较,如果相等,则查找成功,否则利用中间位置将序列分成两个子序列,如果待查找的关键字小于中间的关键字,则在前一个子序列中同样的方法进一步查找,如果待查找的关键字大于中间的关键字,则在后一个子序列中同样的方法进一步查找,重复以上过程一直到查找结束! 时…

2021年5月3日 0条评论 4点热度 阅读全文

/** *    实验题目: *        实现索引文件建立和查找算法 *    实验目的: *        掌握索引文件的基本操作及其算法设计 *    实验内容: *        编写程序,建立表12.1中学生成绩记录对应的主文件data.dat, *    要求完成以下功能: *    …

2021年5月3日 0条评论 3点热度 阅读全文