- 博客(18)
- 收藏
- 关注
RSS订阅原创 有向图的生成树算法及其MATLAB实现
摘要在图论的数学领域中，如果连通图 G的一个子图是一棵包含G 的所有顶点的树，则该子图称为G的生成树(SpanningTree)。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树（来自百度百科）算法思想任意选择一条有向边，记录此边的顶点集合S，删除集合S中各顶点之间的所有有向边，在新的矩阵中寻找与集合S中顶点相关联的有向边，选...
2019-04-17 19:30:38
4549
1
原创 无向图的生成树算法及其MATLAB实现
摘要在图论的数学领域中，如果连通图 G的一个子图是一棵包含G 的所有顶点的树，则该子图称为G的生成树(SpanningTree)。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。（来自百度百科）算法思想任意选择一条边，记录边的顶点集合S，删除S中的各顶点之间的所有边，在新的矩阵中寻找与集合S中顶点相关联的边，选择其中一条边，...
2019-04-13 21:11:44
2841
原创 求割点算法及其MATLAB实现
摘要在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。如果某个割点集合只含有一个顶点X（也即{X}是一个割点集合），那么X称为一个割点（来自百度百科）算法思想其中，下述中的k(v)称为顶点v的DFS编码；f(v)称为顶点的父，v称为f(v)的子，且以f(v)为起始点、v为终点的有向边称为父子边。先给出有关...
2019-04-13 18:52:11
981
2
原创 深度优先搜索算法及其MATLAB实现
摘要深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有...
2019-04-13 14:33:32
9888
原创 广度优先搜索算法及其MATLAB实现
摘要广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。(来自百度百科)算法思想1.对图中的任...
2019-04-10 19:48:49
6276
6
原创 求Huffman树及其MATLAB实现
Huffman树的定义给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。（来自百度百科）算法思想1.对给出的所有叶子节点的权重进行从小到大的排序，得到权重向量W = (p1, p2, p3…pn)。2.写出子节点为p1，p2父节点为p1+...
2019-04-09 19:44:27
1856
原创 连通图的中心及加权中心的算法及其MATLAB实现
摘要1.中心：设连通图G=(V,E)，所有的顶点与离它自身最远顶点的距离取得极小值的顶点称图G的中心2.加权中心：若图G的每一个顶点赋有权值，则考虑权值的情况下求出的中心为权值中心。算法思想1.求中心：先求出图的最短距离矩阵（该程序用的Floyd算法），在求矩阵各行的极大值，在这些极大值中选取最小值，最小值的下标对应的顶点为图的中心。2.求加权中心：同样先求出距离矩阵，再输入权值矩阵，对...
2019-04-04 11:22:54
1611
原创 力扣之寻找两个有序数组的中位数（题号4）
题目叙述给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。示例 1:nums1 = [1, 3]nums2 = [2]则中位数是 2.0示例 2:nums1 = [1, 2]nums2 = [3, 4]则中位数是 (2...
2019-04-03 21:26:54
250
原创 力扣之最长回文子串（题号5）
题目叙述给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: “babad”输出: “bab”注意: “aba” 也是一个有效答案。示例 2：输入: “cbbd”输出: “bb”题解方法一：暴力法截取出输入字符串的所有子串，并判断是否是回文子串，在找到最大的那个private static String f(String ...
2019-04-03 20:59:18
222
原创 Warshell算法判读图的连通性算法及其MATLAB实现
算法思想若矩阵P是判断矩阵，P(i, j) == 1表示从i到j连通，P(i, j) == 0表示从i到j不连通(1)置新矩阵 P:= G; (2)置 i = 1;(3)对所有的j，若P(j, i) == 1，则对k=1,2,…,n，有P(j, k) := P(j, k) νP(i, k)(4)i = i + 1;(5)如n >= i转向步骤(3), 否则停止。程序参数说明G...
2019-04-02 15:34:10
3959
2
原创 求两点间最短路的Dijkstra算法及其MATLAB实现
算法思想把顶点集合V分成两组：（1）S：已求出的顶点的集合（初始时只含有源点V0）（2）V-S=T：尚未确定的顶点集合将T中顶点按递增的次序加入到S中，保证：（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点：从V0到此顶点的长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度程序参数说明A表示图...
2019-03-31 18:19:03
2892
1
原创 无向图的关联矩阵和邻接矩阵的相互转换算法及其MATLAB实现
算法思想1.邻接矩阵转换为关联矩阵给边的起始点赋值为1，给边的终点赋值为12.关联矩阵转换为邻接矩阵存在边，则邻接矩阵的对应值为1程序的参数说明当f=0时，邻接矩阵转换为关联矩阵，F表示邻接矩阵，W表示关联矩阵当f=1时，关联矩阵转换为邻接矩阵，F表示关联矩阵，W表示邻接矩阵MATLAB实现function W = incandaf(F,f)if f == 0 m = ...
2019-03-31 12:24:56
5124
原创 计算有向图的可达矩阵的算法及其MATLAB实现
算法思想设A为n阶有向图的邻接矩阵先求出Bn=A+A2+⋅⋅⋅+An然后把矩阵Bn的不为0的数变为1，为0的数不变MATLAB实现function P = dgraf(A)n = size(A,1);P = A;for i = 2 : n P = P + A^i;endP(P ~= 0) = 1;测试测试用例： A = [0,1,1,1;1,0,1,1;1,1,0...
2019-03-31 11:29:13
6487
2
原创 力扣之最大子序和（题号53）
题目叙述给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。题解方法一：暴力法public static int max...
2019-03-27 23:17:41
128
原创 力扣之盛最多水的容器（题号11）
题目叙述给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且 n 的值至少为 2。图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（...
2019-03-27 19:42:30
216
原创 力扣之两数之和（题号1）
题目叙述给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]题解方法一...
2019-03-26 19:50:44
2716
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人