闫鲜森-CSDN博客

原创最小生成树之克鲁斯卡尔（kruskal）算法

Kruskal算法前面讲了最小生成树的Prim算法的实现思路是，通过顶点的扩展不断地寻找最小权重的生成树，而Kruskal算法是查找最小权值的边，然后逐渐把连通分量变为一个联结全部顶点的最小生成树。不同于 Prim算法，这次用边集数组结构来实现 Kruskal算法结构很简单，包括权值，边的弧起点和终点的下标将前面Prim例子中的图转化为边集数组，并且按照权值升序排列储存为 edges...

2019-02-12 16:24:13 963

原创（原创）最小生成树之Prim（普里姆）算法+代码详解，最懂你的讲解

Prim算法（哈欠）在创建最小生成树之前，让我们回忆一下什么是最小生成树。最小生成树即在一个待权值的图（即网结构）中用一个七拐八绕的折线串连起所有的点，最小嘛，顾名思义，要权值相加起来最小，你当然可以拿起笔来就算你脑中的每一种可能，但是如果你了解了这种算法，你就能跟我一样，一次画出完美答案。上个栗子：我先说一哈这个算法的方法论，然后我们来代码实现一下，在讲解开始之前，敲黑板，记得我们要生成...

2019-02-09 16:33:16 1406 1

BFS算法上一篇文章讲解了DFS深度优先遍历的算法，我们说 DFS 顾名思义DEEPTH FIRET，以深度为第一标准来查找，以不撞南墙不回头的态度来发掘每一个点，这个算法思想get到了其实蛮简单。那么 BFS 和DFS有什么相同点和不同点呢？我觉得有一种比喻对于 DFS 和 BFS 从方法论的角度解释很到位，DFS 就像是小明要在家里找到钥匙，因为对位置的不确定，所以一间一间的来找，深度遍历...

2019-02-08 14:50:13 566

原创（原创）不过如此的 DFS 深度优先遍历

DFS 深度优先遍历DFS算法用于遍历图结构，旨在遍历每一个结点，顾名思义，这种方法把遍历的重点放在深度上，什么意思呢？就是在访问过的结点做标记的前提下，一条路走到天黑，我们都知道当每一个结点都有很多分支，那么我们的小人就沿着每一个结点走，定一个标准，比如优先走右手边的路，然后在到达下一个结点前先敲敲门，当一个结点的所有门都被敲了个遍都标记过，那么就走回头路，再重复敲门，直到返回起点，这样的方式...

2019-02-07 17:06:45 465

原创（原创）像极了爱情的详解排序二叉树，一秒get

排序二叉树（建立、查找、删除）二叉树我们已经非常熟悉了，但是除了寻常的储存数据、遍历结构，我们还能用二叉树做什么呢我们都知道不同的遍历方式会对相同的树中产生不同的序列结果，排序二叉树就是利用二叉树的遍历特征实现的特殊树种，也叫二叉查找树1. 排序二叉树从根结点起的每一个结点的左子树元素均小于其自身，右子树元素值均大于其自身2. 即任何结点的值均大于其左子树所有元素，均小于其右子树所有元素...

2019-02-06 17:30:15 151

原创（原创）线索二叉树那点小破事

线索二叉树二叉树的基本定义结构我们都很熟悉，节点数据加上孩纸指针，左孩子指娘家，右孩子指婆家，我们来看这个例子：我们会发现，有些孩子并没有地方可以去，例子中的树一共十个结点，十一个空闲指针，由此引出我们对于空闲指针的计算公式：一个有 n 个结点的二叉树有 2n 个指针域，而 n 个结点会产生 n-1 个分支，每个分支对应其指向孩子的指针域，所以空闲指针数： 2n - (n-1) = n+1 ，...

2019-02-04 21:54:54 691

原创（原创）大白话KMP算法，秒懂模式匹配（续）

第二章：KMP改良算法第一章里面我们讲完了KMP算法的next数组实现法，回忆一下其实最重要的内容无非就是一、理解 i 指针无用回溯的意义，二、理解 j 指针的定位和模式串中每个元素重复度的关系，三、对next数组从观察到代码实现一条蛇式的理解掌握。 ps：文末有彩蛋哦。自从BF暴力算法下岗之后呢，KMP算法就开始大行其道，当然也难怪，因为他大幅减少了算法的时间复杂度，而且还和朴素BF算法达到...

2019-02-03 12:14:55 108

原创（原创）大白话KMP算法，秒懂模式匹配

引子：BF暴力算法KMP算法知名度相当高，燃鹅其理解难度以及代码实现对于初学数据结构和算法的同学并不友好，经过两天的总结，详细总结KMP算法如下：初学串的模式匹配时，我们都会接触到，或者说应该能想到作为教学引子的BF暴力算法，那么先来简单了解一哈：我有一个大串是"abccabca",小串是"bca",现在要找到小串在大串中的位置,战斗开始①引子：BF暴力算法KMP算法知名度相当高，燃鹅其...

2019-02-03 12:07:48 125

qq_41682108的博客