15 梅森上校

尚未进行身份认证

十多年软件行业从业经验,热爱技术,精于项目管理和研发团队建设。闲暇至于,喜欢欣赏音乐,看看电影;摆弄摆弄茶道,让身心得以调整和休息。

等级
博文 610
排名 2k+

彻底搞懂深度优先搜索算法(DFS)— JAVA版本

彻底搞懂DFS算法法(JAVA版本)深度优先搜索算法(DFS,Depth-First-Search),是搜索算法的一种。基本思想:沿着树的深度来遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直...

2019-07-21 01:37:39

算法题解:求有向图中的最短路径(JAVA+DFS算法实现)

求有向图中的最短路径(JAVA+DFS算法实现)问题描述给定一个有向图,如下图所示,求从1号顶点到5号顶点的最短路径。输入数据格式为第一行输入顶点数和边数,从第二行开始每一行输入3个整数,分别代表连接顶点的边和权重。例如:122,表示从1号顶点到2号顶点连接的边,权重为2。Input:581221510233257314...

2019-07-16 00:31:57

算法题解:不邻接植花(JAVA代码)

不邻接植花(JAVA代码)原题链接:1042.FlowerPlantingWithNoAdjacenthttps://leetcode.com/problems/flower-planting-with-no-adjacent/有N个花园,按从1到N标记。在每个花园中,你打算种下四种花之一。paths[i]=[x,y]描述了花园x到花园y的双向路...

2019-07-15 23:06:00

算法题解:单词接龙(JAVA+BFS算法)

单词接龙(JAVA+BFS算法)原题链接:127.WordLadderhttps://leetcode.com/problems/word-ladder/给定两个单词(beginWord和endWord)和一个字典,找到从beginWord到endWord的最短转换序列的长度。转换需遵循如下规则:每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。...

2019-07-15 01:01:25

算法题解:对于给定的无向连通图G和m种不同的颜色计算图的所有不同着色法(JAVA代码)

对于给定的无向连通图G和m种不同的颜色计算图的所有不同着色法问题描述给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。如果有一种着色法使图G中每条边的2个顶点着不同颜色,则称这个图是m可着色的。图的m着色问题是对于给定图G和m种颜色,找出所有不同的着色法。你的任务是对于给定的无向连通图G和m种不同的颜色,编写一个JAVA程序来计算无向图G的所...

2019-07-14 11:48:04

算法题解:图的着色问题(给定无向连通图的顶点数和边数计算图的色数)—JAVA回溯算法

图的着色问题(给定图的顶点数和边数计算需要的颜色数)问题描述给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。是否有一种着色法使图G中每条边的两个顶点有不同的颜色?问题分析这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边相连接的两个顶点着不同颜色,称这个数m为这个图的色数。求一个图的色数m称为图的m可着色优化问题。...

2019-07-13 16:20:06

JAVA算法:判断一个图是否为星型图(Star Graph)

判断一个图是否为星型图(StarGraph)给你一个n*n矩阵,它代表一个有n个顶点的图,检查输入矩阵是否代表一个星型图。输入矩阵Mat[][]={{0,1,0},{1,0,1},{0,1,0}}输出:星型图(Stargraph)输入矩阵Mat[][]={{0,1,...

2019-07-11 22:19:50

JAVA算法:有向图的强连通分量(Strongly Connected Components)

有向图的强连通分量(StronglyConnectedComponents)如果在所有顶点对之间都有一条路径,则有向图是强连通的。有向图的强连通分量是最大的强连通子图。例如,下图中有3个SCC。算法分析我们可以使用Kosaraju算法在O(V+E)时间内找到所有强连通组件。以下是Kosaraju的详细算法:1)创建一个空堆栈“S”,并对一个图G执行DFS遍历。...

2019-07-11 21:53:56

算法题解:寻找有向无环图中的最长路径(JAVA+动态规划)

寻找有向无环图中的最长路径(JAVA+动态规划)给出了一个具有n个顶点和m个边的有向图G。任务是找出图中最长有向路径的长度。注:有向路径的长度是指路径中的边数。例如:下图中有4个顶点,5条边。最长的有向路径的长度为3。从1到3,到2,到4。算法实现packagecom.bean.algorithm.graph;importjava.util.ArrayL...

2019-07-11 21:21:15

JAVA算法:无向图的着色(Graph Coloring)问题

图着色(GraphColoring)问题图着色问题(GraphColoringProblem,GCP)又称着色问题,是最著名的NP—完全问题之一。道路着色问题(RoadColoringProblem)是图论中最著名的猜想之一。数学定义:给定一个无向图G=(V,E),其中V为顶点集合,E为边集合,图着色问题即为将V分为K个颜色组,每个组形成一个独立集,即其中没有相邻的顶点...

2019-07-08 23:26:49

算法题解:旅行商(TSP)问题JAVA算法求解

旅行商TSP问题描述旅行推销员问题(Travellingsalesmanproblem,TSP)是这样一个问题:给定一组城市和每对城市之间的距离,问题是找到最短的可能路线,访问每个城市一次,然后返回起点。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中非常重要。注意哈密顿回路和TSP之间的区别。哈密顿回路问题是要找出是否存在一个旅游线路,每个城市访问一次。这里我们...

2019-07-08 00:03:26

JAVA算法:Dijkstra最短路径算法

JAVA算法:Dijkstra最短路径算法基础知识:迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。问题描述:在有向图G=(V,E)中,假设每条边E[i]的长度为w[i],找到由...

2019-07-07 21:58:35

算法题解:二维矩阵从左上角到右下角路径的最小和(JAVA代码)—动态规划

二维矩阵从左上角到右下角路径的最小和(JAVA代码)—动态规划给定一个二维数组m行,n列。假设这个二维数组中每个单元格的值都是正整数,表示从该单元格经过时需要花费的成本。那么求从右上角第一个单元格到右下角最后一个单元格的路径中,花费的最小成本是多少?约束条件为:你只能向右,向下,或者向右下(对角线方向)走。例如:给定一个m=3,n=3的二维数组cost,如下图所示,从左上角的第...

2019-07-07 21:10:33

JAVA算法:无向图的BFS遍历算法(Breadth First Traversal)

JAVA算法:无向图的BFS遍历算法图的广度优先遍历(BFS,BreadthFirstTraversal)类似于树的广度优先遍历。这里唯一的要点是,与树不同,图可能包含循环回路,因此我们可能再次到达同一个节点。为了避免多次处理一个节点,我们使用一个布尔访问数组。为了简单起见,假设所有顶点都可以从起始顶点到达。例如,在下图中,我们从顶点2开始遍历。当我们到达顶点0时,我们寻找它的所有相邻...

2019-07-07 15:32:55

JAVA算法:计算有向图中顶点的依赖和

JAVA算法:计算图中顶点的依赖和给出了一个具有n个节点的有向连通图。如果从U到V有一个边,那么U依赖于V。我们的任务是找出每个节点的依赖项之和。例如下图中:对于节点A,从A出发的边有两条,A到C,和A到D;则根据题目描述的定义,A依赖于C和D,则依赖项为2;对于节点B,从B出发的边有一条,B到C,则B依赖于C,依赖项为1;对于节点C,没有从C出发的边,则依赖项为0;...

2019-07-07 12:04:33

算法题解:岛屿的数量(JAVA代码)

算法题解:岛屿的数量(JAVA代码)给定一个二维数组,数组元素由0和1组成。0代表水,1代表陆地。陆地可以形成岛。如果上下左右,包括对角线方向如有相邻的陆地(1)则可以形成岛。如下图所示。编写一个算法,求岛的数量。例如:规定一个二维数组:{1,1,0,0,0},{0,1,0,0,1},{1,0,0,1,1},{0,0,0,0,0},{1...

2019-07-07 11:36:00

JAVA算法:无向图的表示(基础)

JAVA算法:无向图的表示(基础)图形是由以下两部分组成的数据结构:一组有限的顶点(Vertices),也称为节点(Nodes)。 一组有限的有序对形式(u,v)称为边(Edge)。因为在有向图的情况下,(u,v)与(v,u)不同,所以对是有序的。对于(u,v)表示从顶点u到顶点v有一条边。边可能包含权重/值/成本等信息。如上图所示,表示一个具有5个顶点,7条边的无向图。图通常...

2019-07-06 23:24:03

算法题解:计算两个顶点之间的所有可能路径(JAVA代码)

算法题解:计算两个顶点之间的所有可能路径(JAVA代码)计算有向图中两个顶点之间存在的路径总数。这些路径不包含循环路径。例如在上图中,计算从顶点A到顶点E的所有可能路径。结果为:从A点到E点存在4条路径。分别为:A->E A->B->E A->C->E A->B->D->C->...

2019-07-06 18:00:55

JAVA代码详解: 有向图中判断欧拉路径和欧拉回路

JAVA代码详解:有向图中判断欧拉路径和欧拉回路欧拉路径是图中访问每一条边一次的路径。欧拉回路是在同一顶点上开始和结束的欧拉路径。有欧拉回路的图称为欧拉图。上一篇博客讨论了无向图的欧拉回路。接下来这一篇博客讨论有向图中判断欧拉路径和欧拉回路问题。例如,下图的欧拉循环为1、0、3、4、0、2、1如何检查有向图是否是欧拉图?如果以下条件为真(成立),则有向图具有欧拉回...

2019-07-06 17:43:59

JAVA代码详解:无向图中判断欧拉路径和欧拉回路

JAVA代码详解:无向图中判断欧拉路径和欧拉回路欧拉回路(EulerCircuit)是数学家欧拉(Euler)在研究著名的德国哥尼斯堡(Koenigsberg)七桥问题时发现的。如下图所示,流经哥尼斯堡的普雷格尔河中有两个岛,两个岛与两岸共4处陆地通过7座桥彼此相联。7桥问题就是如何能从任一处陆地出发,经过且经过每个桥一次后回到原出发点。欧拉由此提出了著名的欧拉定理。1)欧拉路(...

2019-07-06 13:43:58
奖章
  • 领英
    领英
    绑定领英第三方账户获取
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。