- 博客(16)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 二分图最大匹配-匈牙利算法
今天介绍 匈牙利算法 ： 匈牙利算法，是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，由匈牙利数学家Edmonds于1965年提出，因而得名。 先介绍一下增广路径：若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。文字难以理解，看图：...
2018-08-10 23:11:34
607
原创 最小生成树-kruskal
kruskal (克鲁斯卡尔) 算法与前面的 prim（普里姆）算法都是求最小生成树的算法，prim 在没有任何优化的情况下时间复杂度为O（n^2） kruskal 的时间复杂度与使用的排序算法有关 若用快排(qsort) 时间复杂度为 O（N log N） ；两者还有一个区别：prim算法 以点为单位采用迭代的思想逐步生成最小树，kruskal 算法以边为单位 借助并查集的思想和...
2018-08-10 00:54:07
494
原创 最小生成树 - prim 算法
最小生成树 ：在一个有n 个结点的连通图G中，G的一个连通子图中包含原图中的所有 n 个结点，在使边的权之和最小的情况下含有使保持图连通的最少的边。这个连通子图就是 G 的一个最小生成树。 注：最小生成树不唯一，但是边的权之和唯一。 求最小生成树有两个常用的算法 ：kruskal(克鲁斯卡尔）算法 和 prim(普里姆）算法，这一节讲 prim 算法；...
2018-08-09 16:59:23
454
原创 拓扑排序
拓扑排序是将一个有向无环图G的点进行排序形成一个线性序列，这个线性序列满足：对于途中任意一对顶点，若边(u,v) E (G),则再线性序列中 u 一定在v的前面，我们将这样的线性序列称为满足拓扑次序的序列。 算法很简单：1 首先先在所有点中找到入度为 0 的点 将它存在一个名为 T的队列中.2 然后将 T队列中第一个点u所指向的所有点的入度均 减 1 然后将 u 存入 另一...
2018-08-08 12:03:36
226
原创 Floyd 算法----只有5行的算法
与前面写的Dijkstra 都是关于最短路径的算法，但是不同的是Dijkstra算法是计算单源最短路径的算法，也就是只能计算出一个点到其他点的最短路径，Floyd算法是多源最短路径算法，可以计算出任意两点的最短路径。 在讲Floyd之前先想一个问题 假设我们已经存入了一个图(如下)，我们怎么缩短两点之间的距离呢？显而易见只能找中间点来作为转接点，从而达到缩短距离。这个中间...
2018-08-08 01:12:43
176
原创 图的储存--邻接表
我学过的图的存储方式有两种，一种是用邻接矩阵存储，邻接矩阵的优点是可以快速判断两个顶点之间是否存在边，可以快速添加边或者删除边。但是他也有很明显的不足，那就是邻接矩阵的大小只能根据点来定义，若一个图的点较多但是边很少，如果用邻接矩阵来储存会浪费很大多的空间资源，这时我们的邻接表登场了！！！邻接表就是根据边来定义大小的。 介绍一下邻接表，邻接表可以用结构体 + 指针实现 ...
2018-08-07 23:03:30
3914
原创 图论-Dijkstra
Dijkstra-迪杰斯特拉 算法 算法是处理单源最短路径问题常用的算法，虽然时间复杂度(n^2)较高(但是可以优化)，但是编写起来方便在处理小数据时还是很方便的. dijkstra 算法，在使用时需要指定一个起始点 n，因为这是 计算一个点到其它点最短路径的算法，这里需要 3 个数组 S ， U 和flag 来辅助完成，其中 S 数组用来储存 点 i 到 n 的 最短路...
2018-08-07 21:50:24
1990
原创 堆-二叉堆
我们这里说的堆并不是内存中的堆，我们所说的是数据结构-堆，堆 也叫优先队列是一种特殊的完全二叉树，看下图这棵完全二叉树有什么特点？ 他的每个父节点的值都不小于其子节点的值。这称为一个最大堆，最小堆就是父节点的值均不大于字节点的值的完全二叉树。二叉堆有两点性质： ①结构性：堆具有完全树的结构 ②有序性：堆的父节点值一定不小大于（小于）其子节点的值那...
2018-08-06 22:44:19
768
原创 关于C 语言的内存分配问题
我们在做题时开数组经常会出现爆栈问题，那么这是为什么？ 让我们带着问题先来了解一下C语言的内存分区，C语言内存分为五个区：代码区：顾名思义这里是用来存储代码编译后的二进制机器码；堆区：用于动态内存分配，一般由程序员分配或释放，如果程序员没有在程序运行中手动释放，那么会在程序结束后释放。栈区：编译器自动分配和释放，一般用来存放局部变量、函数参数。全局初始化数...
2018-08-05 22:14:05
202
原创 常量指针 与 指针常量
今天偶然想到了一个问题那就是：const* int p 与 int const* P 两者之间有什么区别？去网上搜索了一下指针常量 和 常量指针的区别：指针常量： 指针常量是，首先它是一个常量用指针来修饰它。定义形式为 type* const name其中 name 只能指向一个地址然后不能改变，但是可以 修改它所指向地址的内容。常量指针： ...
2018-08-05 00:15:29
136
原创 并查集 和 路径压缩
并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其特点是看似并不复杂，但数据量极大并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。 并查集通常包含两个常用的函数 : find() 和 join() ，find()函数是用来查看某个体祖先...
2018-08-04 11:01:07
1881
原创 广度优先搜索
广度优先搜索与前面的深度优先搜索是两种特别常用图的搜索算法，广度优先搜索，是在搜索的把当前能到的点全部用队列储存起来，然后在进行队列中下一个点的搜索，知道把图搜索完成或达到了某个特定条件再结束。看一道简单例题：给定一张地图，求里面的连通块个数输入：在第一行中输入两个整数 r, c分别 表示地图的宽度和长度，接下来 r 行 c 列 将地图输入。输出：在一行中输出地图的连通快个...
2018-08-03 23:36:22
3141
原创 深度优先搜索及奇偶剪枝
深度优先搜索实现方式有很多种，我学习的是借助于递归来完成的，先讲一个简单的例子：给定一个整数 n，输出n的全排列；先用深搜实现一下：#include<stdio.h>int book[100] ,a[100],sum = 0; 用a数组来储存n的排列，用book数组记录a数组中有哪些元素void dfs(int n,int step){ int i; if (...
2018-08-03 19:26:17
450
原创 单调队列
单调队列是通过维护队列严格单调来解决问题，先看一个问题（北大OJ 2823）:分析一下问题：这是一个滑动窗口问题，题意是(英语菜鸡的翻译)：给你一个大小为 n (n<=10^6)的数组，有一个大小为k的滑动窗口从最左边移动到最右边，你只能看到窗口里的k个数字，每次滑动窗口移动一个位置，下面是一个例子(如上图)其中数组是[1 3 -1 -3 5 3 6 7],k 是 3你的任务...
2018-08-01 21:33:00
117
原创 搜索二叉树
今天学到了搜索二叉树赶紧来巩固一下。 简单介绍一下数据结构中的树 ，在《离散数学》中树的定义是：连通无回路的图 。 树（tree）是包含n个结点的有穷集，其中 每个元素称为节点，树中边的条数 为 n - 1。 相关术语： 节点的度：一个节点含有的子树的个数称为该节点的度； 叶节点或终端节点：度为0的节点称为叶节点；...
2018-07-31 20:58:05
3083
原创 初遇数论
这是我写的第一份博客，以后会坚持写下去。我是一只菜鸟，不求能写出精致的文章，只是想借助CSDN这个载体把自己学到的知识在这里记录一下顺便巩固一下； 这是我暑假留校的第二周，第一周学习的是C语言进阶，第二周学习的是数论的部分知识，感觉数论的知识难以理解，因此在这里重点写一下数论的知识，顺序是学长所讲内容的从后往前写；好了步入正题：在讲算法之前先总结一下需要提前掌握的概念：...
2018-07-30 11:08:34
139
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人