- 博客(61)
- 资源 (1)
- 收藏
- 关注
RSS订阅转载 图的遍历、最小生成树、最短路径
数据结构和算法系列17 图 阅读目录一，图的定义二，图相关的概念和术语三，图的创建和遍历四，最小生成树和最短路径五，算法实现这一篇我们要总结的是图(Graph)，图可能比我们之前学习的线性结构和树形结构都要复杂，不过没有关系，我们一点一点地来总结，那么关于图我想从以下几点进行总结： 1，图的定义？ 2，图相关的概念和术语？ 3，图的创建和遍历？ 4，最小生成树和最短路径？
2017-08-09 21:53:58
14935
转载 数据结构：图的存储、图的遍历、最小生成树、最短路径、拓扑排序
一、基本术语图：由有穷、非空点集和边集合组成，简写成G(V,E);Vertex：图中的顶点；无向图：图中每条边都没有方向；有向图：图中每条边都有方向；无向边：边是没有方向的，写为(a,b)有向边：边是有方向的，写为<a,b>有向边也成为弧；开始顶点称为弧尾，结束顶点称为弧头；简单图：不存在指向自己的边、不存在两条重复的边的图；无向完全图：每个顶点之间都有一条边的无向图；有向完全图：
2017-08-09 21:49:54
21784
转载 数据结构：图——图的遍历、最小生成树、最短路径算法
前言在这里,如果大家对图或者数据结构还不太熟悉,想找一个动态的生成过程来参考,这是一个不错的网站.知识框架图的定义在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素(除第一个和最后一个外)只有一个直接前趋和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素(双亲节点)及下一层的多个元素(孩子节点)相关
2017-08-09 21:46:13
48655
转载 Kruskal算法：贪心+并查集=最小生成树
算法的高效实现需要一种称作并查集的结构。我们在这里不介绍并查集，只介绍Kruskal算法的基本思想和证明，实现留在以后讨论。
2017-08-09 21:42:32
3386
转载 带权最短路 Dijkstra、SPFA、Bellman-Ford、ASP、Floyd-Warshall 算法分析
图论中，用来求最短路的方法有很多，适用范围和时间复杂度也各不相同。本文主要介绍的算法的代码主要来源如下：Dijkstra: Algorithms（《算法概论》）Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani;《算法竞赛入门经典—训练指南》刘汝佳、陈峰。SPFA (Shortest Path Faster Algorithm): Data
2017-08-07 08:47:20
51706
转载 Dijkstra、Bellman_Ford、SPFA、Floyd算法复杂度比较
Dijkstra：适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度O(E+VlgV)BellmanFord：适用于权值有负值的图的单源最短路径，并且能够检测负圈，复杂度O(VE)SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，论文中的复杂度O(kE)，k为每个节点进入Queue的次数，且k一般<=2，但此处的复杂度证明是有问题的，其实SPFA的最坏情况应该是O(VE).
2017-08-07 08:43:01
44580
转载 图的最短路径：Dijkstra、Bellman-Ford、SPFA、Floyd、A*算法
图的表示方式：邻接矩阵、邻接表SPFA、Bellman-Ford、Dijkstra、A*算法
2017-08-07 08:41:03
50310
转载 SPFA算法详解
适用范围：给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。 我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。算法思想：我们用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。
2017-08-07 08:34:24
9940
转载 SPFA算法 求单源最短路
SPFA算法为了简便，我们约定图中不存在负权回路，这可以通过一次拓扑排序知道。SPFA实际是Bellman-Ford算法的一种队列实现，用一个数组来保存最短路径的估计值，初始时将源加入队列，每次从队列中取队头元素，并对所有与其相邻的结点进行松弛操作，如果该点的估计值有所调整，且该点不在队列中，则入队，如此反复，直到队空。
2017-08-07 08:32:40
982
转载 最短路算法
最短路径问题旨在寻找图中两节点之间的最短路径，常用的算法有以下四种。注意是把图处理成无向还是有向Dijkstra’s (权值非负)1 Dijkstra’s算法解决的是图中单个源点到其它顶点的最短路径。只能解决权值非负2 Dijkstral只能求出任意点到达源点的最短距离（不能求出任意两点之间的最短距离），同时适用于有向图和无向图，复杂度为O(n^2).3算法的过程： 1设置顶点集合S并不断的
2017-08-06 07:25:33
1407
转载 Prim算法和Kruskal算法
Prim算法和Kruskal算法都能从连通图找出最小生成树。区别在于Prim算法是挨个找，而Kruskal是先排序再找。
2017-08-06 07:21:42
20010
2
转载 最小生成树Prim算法理解
MST（Minimum Spanning Tree，最小生成树）问题有两种通用的解法，Prim算法就是其中之一，它是从点的方面考虑构建一颗MST，大致思想是：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意
2017-08-06 07:19:20
1231
转载 最小生成树之Prim算法
普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆
2017-08-06 07:11:05
6743
转载 最小生成树之Kruskal算法
给定一个无向图，如果它任意两个顶点都联通并且是一棵树，那么我们就称之为生成树(Spanning Tree)。如果是带权值的无向图，那么权值之和最小的生成树，我们就称之为最小生成树(MST, Minimum Spanning Tree)。 我们由最小生成树的定义，可以延伸出一个修建道路的问题：把无向图的每个顶点看作村庄，计划修建道路使得可以在所有村庄之间通行。把每个村庄之间修建道路的费用
2017-08-06 07:07:20
6602
转载 拓扑排序的原理及其实现
本文将从以下几个方面介绍拓扑排序：拓扑排序的定义和前置条件和离散数学中偏序/全序概念的联系典型实现算法Kahn算法基于DFS的算法解的唯一性问题实际例子取材自以下材料：http://en.wikipedia.org/wiki/Topological_sortinghttp://en.wikipedia.org/wiki/Hamiltonian_path定义和前置条件：定义：将有向图中的顶
2017-08-06 06:59:23
981
转载 拓扑排序的原理及实现
拓扑排序，顾名思义，就是一种排序方法。这是一种什么排序？这种排序的作用？然后怎么去实现这种排序算法？现在就让我们仔细研究下。1、什么是拓扑排序，也就是拓扑排序的概念实际上，拓扑排序是一种图论算法，该算法在《数据结构与算法》一书中有涉猎。引用维基百科的定义：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。
2017-08-05 14:06:27
24776
6
转载 拓扑排序
拓扑排序 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。 通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。
2017-08-05 14:05:00
7884
转载 拓扑排序的原理及其实现
本文将从以下几个方面介绍拓扑排序：拓扑排序的定义和前置条件和离散数学中偏序/全序概念的联系典型实现算法Kahn算法基于DFS的算法解的唯一性问题实际例子取材自以下材料：http://en.wikipedia.org/wiki/Topological_sortinghttp://en.wikipedia.org/wiki/Hamiltonian_path定义和前置条件：定义：将有向图中的顶
2017-08-05 14:01:52
12380
转载 动态规划入门
学动态规划自然要从数字三角形开始起步，那么我们就先从数字三角形开始。数字三角形题目：有一个由非负整数组成的三角形，第一行只有一个数，除了最下行之外的每个数的左下方和右下方各有一个数，如下图所示：13 24 10 14 3 2 20从第一行的数开始，每次可以往下或往右下走一格，直到走到最下行，把沿途经过的数全部加起来。如何走才能使这个和最大？知道回溯法么（请参看：八皇后与回溯法），你
2017-08-05 13:53:44
5316
转载 动态规划总结与题目分类
源博客链接：http://blog.csdn.net/cc_again/article/details/25866971动态规划一直是ACM竞赛中的重点，同时又是难点，因为该算法时间效率高，代码量少，多元性强，主要考察思维能力、建模抽象能力、灵活度。动态规划（英语：Dynamic programming，DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解
2017-08-05 13:52:06
1633
转载 很特别的动态规划教程——通过金矿模型介绍动态规划
很特别的一个动态规划入门教程附上原文地址：http://www.cnblogs.com/sdjl/articles/1274312.html通过金矿模型介绍动态规划 对于动态规划，每个刚接触的人都需要一段时间来理解，特别是第一次接触的时候总是想不通为什么这种方法可行，这篇文章就是为了帮助大家理解动态规划，并通过讲解基本的01背包问题来引导读者如何去思考动态规划。本文力求通俗易懂，
2017-08-05 13:49:25
540
转载 动态规划题目总结
动态规划一直是ACM竞赛中的重点，同时又是难点，因为该算法时间效率高，代码量少，多元性强，主要考察思维能力、建模抽象能力、灵活度。
2017-08-05 13:46:32
7971
2
转载 动态规划总结
终于来到了算法设计思想中最难，也最有趣的这部分，在去年的google笔试中，7道算法设计题有2道动态规划（Dynamic Programming）。看了这么久的算法，这部分也是唯一感觉到了比较难的地方，从这篇文章开始，将花连续的篇幅来讨论一些动态规划的问题。这包括书上介绍过的计算二项式系数，Warshall算法求传递闭包，Floyd算法求完全最短路径，构造最有二叉查找树，背包问题和记忆功能。也包括一
2017-08-05 13:42:12
10161
转载 教你彻底学会动态规划
动态规划相信大家都知道，动态规划算法也是新手在刚接触算法设计时很苦恼的问题，有时候觉得难以理解，但是真正理解之后，就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章，大多都是叙述概念，讲解原理，让人觉得晦涩难懂，即使一时间看懂了，发现当自己做题的时候又会觉得无所适从。我觉得，理解算法最重要的还是在于练习，只有通过自己练习，才可以更快地提升。话不多说，接下来，下面我就通过一个例
2017-08-05 13:39:40
7146
转载 白话经典算法系列之十六 “基数排序”之数组中缺失的数字
首先看看题目要求：给定一个无序的整数数组，怎么找到第一个大于0，并且不在此数组的整数。比如[1,2,0]返回3，[3,4,-1,1]返回2，[1, 5, 3, 4, 2]返回6
2017-08-04 09:23:50
1619
转载 白话经典算法系列之十五 “一步千里”之数组找数
首先看看题目要求（题目来源：http://weibo.com/lirenchen，特此鸣谢）：有这样一个数组A，大小为n，相邻元素差的绝对值都是1。如：A={4,5,6,5,6,7,8,9,10,9}。现在，给定A和目标整数t，请找到t在A中的位置。除了依次遍历，还有更好的方法么？这道题目的解法非常有趣。数组第一个数为array[0], 要找的数为y，设t = abs(y - array[0])。由
2017-08-04 09:22:26
1461
转载 白话经典算法系列之十三 随机生成和为S的N个正整数——投影法
【白话经典算法系列之十三】随机生成和为S的N个正整数——投影法 随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效且比较有趣味性的解法——投影法。 以生成和为20的4个数为例，可以先生成随机生成0到20之间的三个数字再排序，假设得到了4，7，18。然后在X-Y数轴上画出这三个数，如下图：然后将这些数值投影到Y轴上，可得下图：由图很容易看出AB，BC，CD，DE这四段的长度和
2017-08-04 09:19:35
1756
转载 白话经典算法系列之十二 数组中只出现一次的两个数字（百度面试题）
微博http://weibo.com/MoreWindows已开通，欢迎关注。本系列文章地址：http://blog.csdn.net/MoreWindows/article/category/859207首先来看题目要求：在一个数组中除两个数字只出现1次外，其它数字都出现了2次， 要求尽快找出这两个数字。 考虑下这个题目的简化版——数组中除一个数字只出现1次外，其它数字都成对出现，要求尽快找
2017-08-04 09:17:50
1711
转载 白话经典算法系列之十一 一道有趣的GOOGLE面试题 【解法2】
上一篇《白话经典算法系列之十一道有趣的GOOGLE面试题》中对一道有趣的GOOGLE面试题进行了详细的讲解，使用了类似于基数排序的做法在O(N)的时间复杂度和O(1)的空间复杂度完成了题目的要求，文章发表后，网友fengchaokobe在评论中给出了另一种解法，见下图。文字版：[cpp] view plain copy print?int Repeat(int *a, int n) {
2017-08-04 09:15:15
5735
转载 白话经典算法系列之十 一道有趣的GOOGLE面试题
微博http://weibo.com/MoreWindows已开通，欢迎关注。最近在微博上看到一道有趣的GOOGLE面试题，见下图：文字版：一个大小为n的数组，里面的数都属于范围[0, n-1]，有不确定的重复元素，找到至少一个重复元素，要求O(1)空间和O(n)时间。 这个题目要求用O(n)的时间复杂度，这意味着只能遍历数组一次。同时还要寻找重复元素，很容易想到建立哈希表来完成，遍历数组时
2017-08-04 09:11:17
7154
转载 白话经典算法系列之九 从归并排序到数列的逆序数对（微软笔试题）
首先来看看原题 微软2010年笔试题在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序数对。一个排列中逆序的总数就称为这个排列的逆序数。如{2，4，3，1}中，2和1，4和3，4和1，3和1是逆序数对，因此整个数组的逆序数对个数为4，现在给定一数组，要求统计出该数组的逆序数对个数。 计算数列的逆序数对个数最简单的方便就最从前向后依次统计每个数字与它后面的
2017-08-04 08:59:23
6928
转载 白话经典算法系列之八 白话经典算法之七大排序总结篇
在我的博客对冒泡排序，直接插入排序，直接选择排序，希尔排序，归并排序，快速排序和堆排序这七种常用的排序方法进行了详细的讲解。 首先回顾下各种排序的主要思路：一． 冒泡排序冒泡排序主要思路是：通过交换使相邻的两个数变成小数在前大数在后，这样每次遍历后，最大的数就“沉”到最后面了。重复N次即可以使数组有序。冒泡排序改进1：在某次遍历中如果没有数据交换，说明整个数组已经有序。因此通
2017-08-04 08:57:08
1240
转载 白话经典算法系列之六 快速排序 快速搞定
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想—-分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。总的说来，要直接默写出快速排序还是有一定难度的，因为本人就自己的理解对快速排序作了下白话解释，希望对大家理解有帮助，达到快速排序，快速搞定
2017-08-04 08:48:45
6634
转载 白话经典算法系列之七 堆与堆排序
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想—-分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。总的说来，要直接默写出快速排序还是有一定难度的，因为本人就自己的理解对快速排序作了下白话解释，希望对大家理解有帮助，达到快速排序，快速搞定
2017-08-04 08:45:57
6211
转载 白话经典算法系列之五 归并排序的实现
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。[cpp] view plain copy print?//将有序数组a[]和
2017-08-03 10:23:37
1584
线性代数 工程数学 同济大学
2017-08-11
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人