最小生成树(MST):Prim算法与Kruskal算法

什么是最小生成树 最小生成树是一副连通加权无向图中一棵权值最小的生成树[维基百科] 常见的应用例子有铺设道路连接所有城市、铺设管道等,目标都是使总长度最短。 求解最小生成树的基本原理 Prim算法和Kruskal算法是求解最小生成树的两种经典算法,这两个算法都是贪……

阅读全文

二叉树的遍历(先序遍历,中序遍历,后序遍历,层次遍历)

二叉树简介 维基百科对二叉树的定义:二叉树(英语:Binary tree)是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序,不能颠倒。 二叉树的遍历有4种方式,先序遍历,中序遍历,后序……

阅读全文

Trie,单词查找树

Trie简介 Trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情……

阅读全文

九种经典排序算法详解(冒泡排序,插入排序,选择排序,快速排序,归并排序,堆排序,计数排序,桶排序,基数排序)

综述 最近复习了各种排序算法,记录了一下学习总结和心得,希望对大家能有所帮助。本文介绍了冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序、计数排序、桶排序、基数排序9种经典的排序算法。针对每种排序算法分析了算法的主要思路,每个算法都附上了伪代码和C+……

阅读全文

单源点最短路径算法:Dijkstra算法

背景知识 图简介 图由节点和边组成,边有方向的图称为有向图,边没有方向的图称为无向图,最短路径算法里可以把无向图视为双向连接的有向图。 边有权重的图称为有权图,边没有权重的图称为无权图,无权图可以视为边的权重均为1的图。 单源点最短路径 给定图中的一个节点,求该节点……

阅读全文

单源点最短路径算法:Bellman Ford算法

背景知识 图简介 图由节点和边组成,边有方向的图称为有向图,边没有方向的图称为无向图,最短路径算法里可以把无向图视为双向连接的有向图。 边有权重的图称为有权图,边没有权重的图称为无权图,无权图可以视为边的权重均为1的图。 单源点最短路径 给定图中的一个节点,求该节点……

阅读全文