7 残月飞雪

尚未进行身份认证

在读博士,方向为图像处理

等级
博文 231
排名 3k+

数据结构与算法C++之更多和最短路径相关的问题

2018-12-04 22:24:44

数据结构与算法C++之单源最短路径算法 Bellman-Ford

实现程序如下#include<iostream>#include"SparseGraph.h"#include"ReadGraph.h"#include"BellmanFord.h"usingnamespacestd;intmain(){stringfilename="testG2.txt";//stringfi...

2018-12-04 22:04:08

数据结构与算法C++之单源最短路径算法 dijkstra

单源最短路径算法dijkstra(1)从起始节点0开始,与0连接的节点有1,2,3,将它们的权重存入右表中,可以看出最小的权重是边0-2,权重为2,那么在图中不能有负权边的前提下,0-2的最短路径就是边0-2(2)接下来,以节点2为出发点,考察与2连接的节点1,4,3,边2-1的权重为1,那么0-2-1的耗费为3,比上图表中0-1的耗费5要小,所以将1位置的5替换为3;边2-4权...

2018-11-30 21:04:37

数据结构与算法C++之最小生成树问题总结

2018-11-30 01:51:10

数据结构与算法C++之最小生成树问题 Kruskal

下面是Kruskal算法实现最小生成树(1)下面是有权无向图,初始边的连接如下图(2)对上图的权重按照从小到大排序,如下图(3)按照权重从小到大寻找边,只要不形成环该权重边就符合要求,如下图前5个标为红色的都没有形成环,而边1-3会形成环,舍弃,1-5也会形成环,舍弃,4-5不会形成环,保留,边2-6不会形成环,保留,下图标红的形成最小生成树使用堆实现权重排序#include...

2018-11-30 01:30:05

数据结构与算法C++之最小生成树问题 Prim

上篇博客中使用LazyPrim实现的最小生成树算法复杂度为O(ElogE)O(ElogE)O(ElogE)下面使用Prim实现最小生成树,算法复杂度为O(ElogV)O(ElogV)O(ElogV)使用最小索引堆实现Prim(1)将与节点0相连接的节点的权值放入数组中,节点7的权重最小,那么边0-7属于最小生成树(2)下面开始考察与节点7相连接的节点,对于节点1来说,数组中没有,...

2018-11-29 23:13:48

数据结构与算法C++之最小生成树问题

最小生成树算法LazyPrim

2018-11-29 14:24:11

数据结构与算法C++之带权图

带权图WeightedGraph程序实现如下#include<iostream>#include<iomanip>#include"DenseGraph.h"#include"SparseGraph.h"#include"ReadGraph.h"usingnamespacestd;intmain(){string...

2018-11-28 22:33:50

数据结构与算法C++之图的广度优先遍历

2018-11-28 12:19:34

数据结构与算法C++之图的获得两点之间的一条路径

使用深度优先遍历即可获得两点间的一条路径定义Path.h实现获取路径#include<stack>#include<iostream>#include<cassert>usingnamespacestd;template<typenameGraph>classPath{private:Gr...

2018-11-27 18:48:23

数据结构与算法C++之图的遍历(深度优先遍历)

图的遍历:深度优先遍历(1)首先遍历节点0,与0连接的节点有1,2,5,6,那么先遍历节点1,下面再看与节点1相连的是节点0,节点0已经遍历过了,那么继续遍历节点2,与2连接的节点是0,节点0已经遍历过了,那么开始遍历节点5,(2)与5连接的节点有0,3,4,节点0已经遍历过了,那么开始遍历节点3,3没有被遍历过,记录下3,与节点3连接的节点是4和5,首先4没有被遍历过,记录下4,继续查看...

2018-11-27 09:52:59

数据结构与算法C++之txt中读入图

建立一个ReadGraph.h文件读入txt中存储的图#include<iostream>#include<ctime>#include<cstdlib>#include"SparseGraph.h"#include"DenseGraph.h"#include"ReadGraph.h"usingnamespacestd;int..

2018-11-21 20:26:17

数据结构与算法C++之图的遍历

图的遍历:遍历邻边下面是程序的实现#include<iostream>#include<ctime>#include<cstdlib>#include"SparseGraph.h"#include"DenseGraph.h"usingnamespacestd;intmain(){intN=20;//顶点个...

2018-11-20 19:12:38

数据结构与算法C++之图的表示

图的表示:邻接矩阵、

2018-11-20 11:38:30

数据结构与算法C++之图论

下面这三个连通的,可以是三个图,也可以是一个图

2018-11-19 19:11:57

数据结构与算法C++之并查集 路径压缩

前几篇博客都是对并查集的union进行优化,其实并查集的find也可以优化,之前进行find操作时,如下图,查找4的根节点需要4->3->2->1->0,当根节点数目特别多时,这样是很耗时的,可以通过路径压缩来优化当寻找4的根节点时,首先发现4的父节点3不是根节点,那么继续找3的父节点2是不是根节点这里根据路径压缩,当发现4的父节点3不是根节点时,不再查找3,此时...

2018-11-19 18:42:47

数据结构与算法C++之并查集 基于rank的优化

上一篇博客中,选择根节点数目少的节点指向根节点数目多的节点,这种策略一般是没有问题的,但是如果是下图的情况,要合并4和2根据根节点数目少的指向根节点数目多的,4的根节点数目为3,2的根节点数目为6,那么需要将4的根节点8指向2的根节点7,但是这样树的高度变为4而如果将2的根节点7指向4的根节点8,那么这样树的高度变为3,因此需要根据树的高度来判断谁指向谁根据树的高度判断指向,称为基于r...

2018-11-19 16:05:08

数据结构与算法C++之并查集的优化

上篇中实现的union操作中合并两个元素是无序的,一般将第一个元素指向第二个元素,如下图中,是将4的根节点指向9,但是这样造成树总的高度为4,如果将9指向4的话,树的高度为3,树的高度减少后会很节省后面的查找花费的时间,因此需要先判断一下两个节点的根节点的数目,选择根节点数目少的节点指向根节点数目多的节点下面是程序实现#include<iostream>#include&l...

2018-11-19 15:14:18

数据结构与算法C++之并查集2

上篇博客实现的并查集是使用quickfind实现的,这其中,尽管实现find比较快,但是实现并union却比较慢,现在看一下另外一种实现思路如果两个元素相连接,就把一个元素指向另一个元素,如下图,如果3和2连接,就将3指向2,成2为3的父节点,2只指向自己,如果父节点5也要指向节点2,就把5指向2,那么5下面的6和7的父节点都变为了2...

2018-11-19 14:34:18

数据结构与算法C++之并查集

并查集UnionFind可以解决连接问题和路径问题下图中使用id表示数组,第一行表示其索引,第二行表示元素值,为0的元素表示是互相连接在一起的,同样为1的元素表示互相连接在一起的下面是测试一个并查集Union操作的计算复杂度#include<iostream>#include<cassert>#include"UnionFindTestHel...

2018-11-18 16:27:33
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!