Dijkstra（迪杰斯特拉算法）的实现(C，C++，Matlab)
Dijkstra一.算法背景Dijkstra 算法（中文名：迪杰斯特拉算法）是由荷兰计算机科学家 Edsger Wybe Dijkstra 提出。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。二.算法描述算法思想设G=(V,E)是一个带权有向图，把图中顶点集合V分为两组，第一组....
C++实现排序 - 03 计数排序、桶排序和基数排序
写在前面：今天我们继续来整理与 O(n+k) 有关的三个排序算法，即计数排序、桶排序和基数排序。排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性计数排序O(n+k)O(n+k)O(n+k)O(k)稳定桶排序O(n+k)O(n+k)O(n^2^)O(n+k)稳定基数排序O(n×k)O(n×k)O(n×k)O(n+k)稳定计数排序计数排序是去统计每个值在数组中的数量，然后依次放在它们应该在的位....
C++实现排序 - 02 归并排序、快速排序和堆排序
写在前面：今天我们继续来整理平均时间复杂度为 O(nlogn) 的三个排序算法，即归并排序、堆排序和快速排序。排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(nlogn)O(n^2^)O(nlogn)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定归并排序归并排序采用了....
C++实现排序 - 01 冒泡、选择、插入和希尔排序
写在前面：从这一讲开始，我们整理一下常见的十大排序算法，可以按照它们的时间复杂度进行大致的分类。今天先来讲讲平均时间复杂度为 O(n^2^) 的四个排序算法。排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性冒泡排序O(n^2^)O(n)O(n^2^)O(1)稳定选择排序O(n^2^)O(n^2^)O(n^2^)O(1)不稳定插入排序O(n^2^)O(n)O(n^2^)O(1)稳定希尔排序O....
C++实现查找 - 顺序、二分和哈希查找
写在前面：前面我们其实已经涉及到了查找算法，比如二叉排序树和平衡二叉树等。这一讲我们来补充一下其它常见的查找算法，下面我会依次讲解并实现顺序查找、二分查找和哈希查找算法。顺序查找大家看到顺序查找可能第一时间会想到从前往后遍历，遇到与关键值相等的就输出其下标。这里我们来优化一下，让数组从下标为 1 的地方开始存储元素，然后将下标为 0 的地方放入查找关键值作为哨兵位。这样的好处就是不用去担心数组越....
C++实现图 - 06 关键路径
写在前面：我们上一讲详细的讲述了拓扑排序的实现，为了就是给这一讲打下基础，因为这一讲我们将会讲关键路径，它就要用到拓扑排序的知识。什么是关键路径？关键路径和最短路径不同，它反而去找最长路径，这种意义何在呢，我们来看个例子。假设小明小王小李参与一个大项目，这个大项目需要他们三个共同完成，也就是说这三人缺一人这项目都完成不了。现在这个大项目上面规定他们在半年内完成，假如小明小李分到的任务比较轻，在截....
C++实现图 - 05 拓扑排序
写在前面：今天来讲另一个非常重要的知识点 —— 拓扑排序。咋一看好像是一个排序算法，然而它和排序扯不上半点关系，它可以用于判断我们的图中是否存在有向环。什么是有向无环图？听名字应该很好理解，就是图中存在有向环，我们先看一个有向无环图。我们只需要改动上图一条边，它就成为了一个有环图。拓扑排序算法思想拓扑排序就是对一个有向无环图构造拓扑序列的过程，听起来可能不知道从何下手，其实算法步骤很简单：在有向....
C++实现图 - 04 最短路径
写在前面：今天我们来看看图论中另一个非常重要的问题 —— 最短路径，正如其名就是要再图中找到起点到终点的最短路径，这就需要不断地去比较每条边的权值。这一讲我们将会具体介绍迪杰斯特拉算法和弗洛伊德算法的实现。迪杰斯特拉算法迪杰斯特拉算法是一个单源点的一个最短路径算法，也就是说，我们这个算法会求得从一个顶点到其所有顶点的最短路径。这个算法需要用到邻接矩阵来存储所有边值，并且需要一个辅助数组来更新最短....
C++实现图 - 03 最小生成树
写在前面：这一讲来讲一个图中非常重要的内容 —— 最小生成树，在此之前我们先来回顾一下生成树的概念。生成树的定义一个连通图的生成树是一个极小的连通子图，它包含图中全部的 n 个顶点，但只有构成一棵树的 n-1 条边。说人话就是我要用最少的边将所有结点连接起来，直接上图：而这个原图的生成树就有一下三个：由此可以知道对于包含 n 个顶点的无向完全图最多包含 n 的 n-2 次方颗生成树。最小生成树最....
C++实现图 - 02 图的遍历（DFS、BFS）
写在前面：上一讲我们对图有了一个大概的了解，但是只讲了如何存储图，还没有讲如何遍历图。这一讲我们来介绍图的遍历方式，一共分为深度优先搜索（DFS）和宽度优先搜索（BFS）。深度优先搜索深度优先搜索 ，简称为 DFS 。事实上，我们在树的遍历中早已涉及 DFS ，层、前序遍历、中序遍历和后序遍历都属于深度优先遍历的方式，因为这些遍历方式本质上都归结于栈。为了方便大家理解，我们还是以画图的方式来呈现....
本页面内关键词为智能算法引擎基于机器学习所生成，如有任何问题，可在页面下方点击"联系我们"与我们沟通。
开发与运维
集结各类场景实战经验，助你开发运维畅行无忧
+关注