[编程笔记]-Shortest_Circuit_Problem(General)最短路问题总概

[编程笔记]-Shortest_Circuit_Problem(General)最短路问题总概

#前言本篇博客主要是总概整个最短路问题的算法一览，并不包括每个算法解析，如有需要，请看左边侧边栏的同分类下文章，毕竟也不多，自行寻找，谢谢。 概念最短路问题就是求从某点到某点的最短距离。 源点就是起点，汇点就是终点。 单源最短路边权全为正朴素Dijkstra时间复杂度是O(n2)。故多用于稠密图。 堆优化Dijkstra使用堆优化Dijkstra算法，时间复杂度O(mlogn)。故多用于稀疏图。
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #最短路
[编程笔记]-Topo_Sort拓扑排序

[编程笔记]-Topo_Sort拓扑排序

概念拓扑排序，就是对图中的点进行排序。 排序方式如下： 对于每一个点，它指向的点都排在它后面，指向它的点都排在它前面。 所以，图只能是有向图，还得是有向无环图。 实现记录每一个点的入度，把入度为0的点加入队列，然后BFS一遍，每遍历一个点，就把它“删掉”，使其所有相邻点入度减一，然后再把入度为0的点加入队列。 无须用到vis数组的证明：如果重复遇到同一个点，则说明指向这个点的边不止一条，但是只有当
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #排序
[编程笔记]-Storage_of_Graph图的存储

[编程笔记]-Storage_of_Graph图的存储

邻接矩阵啊开个二维数组，然后a[i][j]表示i到j的边长。完事了。 邻接表利用链表储存每个点的相邻节点。 链式前向星哈希中拉链法头插法也是用的这个。[编程笔记]-Hash_Table哈希表 记录每个节点的第一条边、每条边的边长、每条边指向的节点、每条边的下一条边（指把这个节点的所有边形成一种链式结构链接），然后就能遍历所有边了。 代码前面两个都太简单了，所以就直接上链式前向星的代码吧。 1234
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #树论
[编程笔记]-BFS广度优先搜索

[编程笔记]-BFS广度优先搜索

前言BFS(Breadth First Search)，广度优先搜索，典中典，重中重。 作用一般用来在图、树中进行搜索。 原理过程可视作一棵树，每次把所有子节点都搜一遍，然后把所有子节点加入待搜索的队列中，排着队一个一个搜，每一个又把所有子节点加入队中…… 其实就是一层一层地搜索~ 实现一般用队列来模拟，需要O(2h)的空间。同时，由于BFS算法的性质，它可以用来解决“最短路”问题。 实现最短路：
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #树论 #BFS #搜索
[编程笔记]-DFS深度优先搜索

[编程笔记]-DFS深度优先搜索

简介DFS(Deep First Search)，深度优先搜索，典中典，重中重。 作用一般用来在图、树中进行搜索。 原理过程可视作一棵树，每次向着子节点搜索，搜到叶节点就回溯，然后搜下一个子节点，直到把子节点搜完了就接着回溯。 实现一般用栈来模拟，需要O(h)的空间 概念回溯就是从子节点回到父节点 剪枝跳过已经遍历过的点减少时间复杂度。 代码递归这个太简单了，过(～￣▽￣)～ 栈这个嘛……说句实话
编程笔记 > 图论树论
#原创 #编程 #c++ #笔记 #图论 #树论 #搜索 #DFS #递归
[编程笔记]-STLs(STL大整合)

[编程笔记]-STLs(STL大整合)

前言手打STL毕竟只是锦上添花，STL才是雪中送炭。 所以，来一篇STL大杂烩大整合！ 注意，这里只整理了常用函数，并不是全部函数！ VECTOR概念是一种动态数组，运用到倍增的思想。 按字典序排序。 原理因为申请空间耗时与空间大小无关、与申请次数有关—— 所以vector会倍增申请空间o(￣︶￣)o 常用函数 函数名 函数作用 函数用法 push_back() 在队尾加入元素 vec.
编程笔记 > 数据结构
#原创 #编程 #c++ #笔记 #STL
[编程笔记]-String_Hash字符串哈希

[编程笔记]-String_Hash字符串哈希

前言这边首先推荐有需要滴去先瞅眼哈希表。“[编程笔记]-Hash_Table哈希表” （半夜写的，可能有点癫嘿嘿嘿） 简介字符串哈希，就是对字符串进行哈希，达到快速储存和查询的目的。 实现求HASH这里要用到一种特殊的哈希方法：将字符串视作一个p进制数（p不一定，按题目要求来，一般就是所有可能出现的字符的个数，反正能让每个字符串独一无二就行），然后再对这个p进制数进行哈希操作。别的就一模一样了。
编程笔记 > 数据结构
#原创 #编程 #c++ #笔记 #哈希 #字符串
[编程笔记]-Hash_Table哈希表

[编程笔记]-Hash_Table哈希表

概念通过哈希函数（自定义，一般是取模），把数据映射到哈希表上。 听不懂就对了，听得懂也没必要看原理了(～￣▽￣)～ 当然，如果已经学过离散化的，理解起来可能方便些。 为了方便学习，这里挂一个离散化链接：“[编程笔记]-Discretization离散化” 顺便也挂一个字符串哈希吧，毕竟同根同源~“[编程笔记]-String_Hash字符串哈希” 实现映射这点就讲讲哈希函数，为了减少哈希冲突，我们一
编程笔记 > 数据结构
#原创 #编程 #c++ #笔记 #哈希
[编程笔记]-Heap堆

[编程笔记]-Heap堆

实质事实上，堆就是一棵完全二叉树。 在堆中，以小根堆为例，每个父节点总是小于等于子节点的。 所以根节点事实上就是最小值。 作用 插入一个数 求集合当中的最小值 删除最小值 删除任意元素（STL做不到） 修改任意元素（STL做不到） 实现存储利用一维数组实现，2x是x左子节点，2x+1是x右子节点。 基操根有两个基本操作：上移和下移，就是把节点与父节点/子节点互换以维护堆的单调性。 初始
编程笔记 > 数据结构
#原创 #编程 #c++ #笔记 #树论 #堆 #排序
[编程笔记]-Union_Find_Set并查集

[编程笔记]-Union_Find_Set并查集

作用以接近O(1)的复杂度合并集合并查询两个元素是否在同一个集合中的简介好用数据结构。 实现概览将每个集合视作一棵树，每个节点储存它的父节点。特别地，根节点储存它本身。 初始化将每个点的父节点都设为它本身。 合并将其中一个集合的根节点的父节点设为另一个集合的根节点。 查询看两个点在不在同一个集合中，也就是看两个点的根节点一样不一样。 优化（路径压缩）其实还可以按秩合并，但那个优化代码量相对较大，并
编程笔记 > 数据结构
#原创 #编程 #c++ #笔记 #树论 #并查集