Jerry404Lee

图论

algorithm(1) AVL(1) BFS+队列(2) BST(2) git(1) GO(4) IDEA(1) java(15) java核心API(3) java设计模式(5) linux(1) OS真象还原(1) PAT(11) PAT做题技巧(1) redis(4) Spring(1) STL(3) 三个一工程(9) 二叉树(3) 二维指针(1) 动态规划-dp(3) 堆(1) 复试(3) 多线程(1) 大数问题(5) 实验楼(1) 快速排序(1) 技巧题(5) 操作系统(1) 数论(4) 普通树(1) 机试(1) 栈(1) 模板(4) 活用递推(1) 牛客算法(7) 类型转换(1) 行数据的处理(1) 计算机网络(3) 读书笔记(1) 递归入门(3) 高频算法题(1)

/ 注册

全部文章 / 图论（共13篇）

图的遍历程序模板--DFS

图的遍历程序模板–DFS //图的遍历：DFS 和 BFS //DFS 伪代码模板 //访问顶点u DFS(u) { vis[u]=true; //设置u已被访问 //访问从u出发可以到达的所有顶点v for(从u出发能到达的所有顶点v) ...

2021-04-29

0 387

图的遍历程序模板–BFS

图的遍历程序模板–BFS //图的遍历：DFS 和 BFS //BFS 伪代码模板 //遍历u所在的连通块 BFS(u) { //定义队列q queue q; 将u入队; //设置u已被加入过队列 inq[u] = true; ...

2021-04-29

0 414

单源最短路径问题--Dijkstra

单源最短路径问题–Dijkstra 首先，Dijkstra算法解决的是单源最短路问题，即给定图G(V,E)和起点s（起点又称为源点），求起点s到达其他顶点的最短距离。注意 Dijkstra算法只能应对所有边权都是非负数的情况，如果边权出现负数，那么迪杰斯特拉算法很可能会出错，这时最好使用S...

2021-04-29

1 678

Dijkstra算法应用小例子

Dijkstra算法应用小例子输入 6 8 0 0 1 1 0 3 4 0 4 4 1 3 2 2 5 1 3 2 2 3 4 3 4 5 3 输出 0 1 5 3 4 6 编程 //Dijkstra算法应用小例子 //算法笔记 P368 亚历山大 #include <cs...

2021-04-29

0 598

Dijkstra算法求最短路径

Dijkstra算法求最短路径 //Dijkstra算法用来求最短距离已经实现了 //那么最短路径如何求解并打印出来呢? //此处的方法是记录路径中结点的前驱 if(v未被访问 && 以u为中介点可以使起点s到顶点v的最短距离d[v]更优 ) { 优化d[v];...

2021-04-29

0 505

Dijkstra算法--变型题的求解

Dijkstra算法–变型题的求解 //Dijkstra算法用来求最短距离已经实现了 //做题题型有变化，需要处理升级版 /* //碰到有两条及以上可以达到最短距离的路径，题目就会给出第二标尺 //第一标尺是距离，要求在所有最短路径中选择第二标尺最优的一条路径。 // // 第二标尺常见的有...

2021-04-29

0 355

最短路径变型题解法举例

最短路径变型题解法举例 PAT A 1003 输入 5 6 0 2 1 2 1 5 3 0 1 1 0 2 2 0 3 1 1 2 1 2 4 1 3 4 1 输出 2 4 //最短路径变型题解法举例 //PAT A 1003 #include <cstdio>...

2021-04-29

0 393

Dijkstra算法第二套模板程序

Dijkstra算法第二套模板程序 //Dijkstra算法第二套模板程序 //分两大步骤 //1.使用Dijkstra算法记录所有最短路径 //通俗的说，就是第一步只筛选第一标尺满足条件的情况，也就是最短路径。 //程序具体实现，固定化，不需要修改 vector<int&g...

2021-04-29

0 464

PAT1030

输入 4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20 输出 0 2 3 3 40 程序 #include <cstdio> #include <cstring> #include <algorith...

2021-04-29

0 365

全源最短路问题--Floyd算法

全源最短路问题–Floyd算法 Floyd算法，也就是弗洛伊德算法，用来解决全源最短路问题。就是对给定的图G，求任意两点u，v之间的最短路径长度，时间复杂度为O(n^3)。由于n^3的复杂度决定了顶点数n的限制约在200以内，因此使用邻接矩阵来实现Floyd算法是非常合适且方便的。 Floy...

2021-04-29

0 1003