java数据结构与算法（十一）——10种常用算法
2021/5/13 12:27:14
本文主要是介绍java数据结构与算法（十一）——10种常用算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
一、非递归二分查找
package Algorithm;
public class BinarySearchNoRecursion {
public static void main(String[] args) {
int[] arr = { 1, 3, 8, 10, 11, 67, 100 }; //升序排列
int res = BinarySearch(arr, 11);
System.out.println(res);
}
//二分查找的非递归实现
/**
*
* @param arr 待查找的数组
* @param target 待查找的值
* @return 返回对应的下标，没找到返回-1
*/
public static int BinarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right)/2;
if (arr[mid] == target) {
return mid;
}else if (arr[mid] > target) {
right = mid -1; //向左边查找
}else {
left = mid + 1; //向右边查找
}
}
return -1;
}
}
二、分治算法
汉诺塔问题
package Algorithm;
public class dacHanoitower {
public static void main(String[] args) {
Hanoitower(5, 'A', 'B', 'C');
}
//使用分治算法解决汉诺塔问题
public static void Hanoitower(int num, char a, char b, char c) {
//如果只有一个盘
if (num == 1) {
System.out.println("第1个盘从 " + a + "->" + c);
}
if (num >= 2) {
//如果有两个以上的盘，我们总是可以看做两个盘，最下面的盘1，上面的盘看做一个整体，作为盘2
//先把上面的所有盘2从a->b,移动过程中会使用到c
Hanoitower(num - 1, a, c, b);
//把最下面的盘1从a->c
System.out.println("第" + num + "个盘从 " + a + "->" + c);
//把b塔的所有盘从b->c，移动过程中使用到a塔
Hanoitower(num - 1, b, a, c);
}
}
}
三、动态规划
背包问题
package Algorithm;
public class DynamicKnapsackProblem {
public static void main(String[] args) {
int[] w = { 1, 4, 3 }; //物品的重量
int[] val = { 1500, 3000, 2000 }; //物品的价值
int m = 4; //背包的容量
int n = val.length; //物品的个数
//创建二维数组v[i][j]，表示在前i个物品中能够装入容量为j的背包的最大价值
int[][] v = new int[n + 1][m + 1];
//为了记录放入商品的情况，定义一个二维数组
int[][] path = new int[n + 1][m + 1];
//初始化第一行和第一列
for (int i = 0; i < v.length; i++) {
v[i][0] = 0; //将第一列置为0
}
for (int j = 0; j < v[0].length; j++) {
v[0][j] = 0; //将第一行置为0
}
//动态规划处理
for (int i = 1; i < v.length; i++) { //不处理第一行，i从1开始
for (int j = 1; j < v[0].length; j++) { //不处理第一列，j从1开始
//公式
if (w[i - 1] > j) { //因为i是从1开始的，但是公式中是从0开始的，所以要w[i - 1]
v[i][j] = v[i - 1][j];
}else {
//因为i是从1开始的，但是公式中是从0开始的，所以要val[i - 1],w[i - 1]
// v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
//为了记录放入商品的情况，不能简单的使用max的公式，用if-else语句处理
if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
path[i][j] = 1; //说明新加入的商品放到了该格中
}else {
v[i][j] = v[i - 1][j];
}
}
}
}
//输出最大价值表
for (int i = 0; i < v.length; i++) {
for (int j = 0; j < v[i].length; j++) {
System.out.print(v[i][j] + " ");
}
System.out.println();
}
//输出最后放入的最大价值的商品
int i = path.length - 1; //行的最大下标
int j = path[0].length - 1; //列的最大下标
while (i > 0 && j > 0) { //从path数组的最后开始找
if (path[i][j] == 1) {
System.out.printf("第%d个商品放入背包\n",i);
j = j - w[i - 1]; //放入i商品后背包容量要减少w[i - 1]
}
i--;
}
}
}
四、KMP算法
字符串匹配问题
暴力匹配算法实现
package Algorithm;
public class ViolenceMatch {
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
System.out.println(violenceMatch(str1, str2));
}
//暴力匹配算法实现
public static int violenceMatch(String str1, String str2) {
//先将字符串转换成字符数组
char[] s1 = str1.toCharArray();
char[] s2 = str2.toCharArray();
int s1Len = s1.length;
int s2Len = s2.length;
int i = 0; //i索引指向是s1
int j = 0; //j索引指向是s2
while (i < s1Len && j < s2Len) { //保证匹配时不越界
if (s1[i] == s2[j]) {
i++;
j++;
}else {
i = i - (j - 1);
j = 0;
}
}
if (j == s2Len) { //说明j走到子串最后，匹配成功
return i - j;
}else {
return -1;
}
}
}
KMP算法实现
package Algorithm;
import java.util.Arrays;
public class KMPAlgorithm {
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
int[] next = KMPNext(str2);
System.out.println(Arrays.toString(next));
int res = KMPSearch(str1, str2, next);
System.out.println(res);
}
//KMP算法实现字符串匹配
//1.先创建子串的部分匹配表
//传进来子串，返回子串对应的部分匹配值
public static int[] KMPNext(String dest) {
//创建一个next数组保存部分匹配值
int[] next = new int[dest.length()];
//如果只有一个字符的字符串,其部分匹配值必为0
next[0] = 0;
for (int i = 1, j = 0; i < dest.length(); i++) {
//如果dest.charAt(i) != dest.charAt(j)，就一直循环找到找到匹配的位置
while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j - 1];
}
//如果相等说明匹配成功j所指的就是最大的公共字符的长度-1，因为数组下标从0开始，所以要j++
if (dest.charAt(i) == dest.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
//2.KMP搜索算法
/**
*
* @param str1 源字符串
* @param str2 子串
* @param next 子串对应的部分匹配表
* @return 第一次出现的位置
*/
public static int KMPSearch(String str1, String str2, int[] next) {
//遍历str1
for (int i = 0,j = 0; i < str1.length(); i++) {
//KMP算法核心
while (j >0 && str1.charAt(i) != str2.charAt(j)) {
j = next[j - 1];
}
//如果发现字符相同j后移继续比较
if (str1.charAt(i) == str2.charAt(j)) {
j++;
}
if (j == str2.length()) {
return i - j + 1;
}
}
return -1;
}
}
五、贪心算法
集合覆盖问题
package Algorithm;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
public class Greedy {
public static void main(String[] args) {
//创建广播电台，放入到MAP中
HashMap<String, HashSet<String>> broadcast = new HashMap<String, HashSet<String>>();
//将各个电台放入到里面
HashSet<String> hashSet1 = new HashSet<>();
hashSet1.add("北京");
hashSet1.add("上海");
hashSet1.add("天津");
HashSet<String> hashSet2 = new HashSet<>();
hashSet2.add("广州");
hashSet2.add("北京");
hashSet2.add("深圳");
HashSet<String> hashSet3 = new HashSet<>();
hashSet3.add("成都");
hashSet3.add("上海");
hashSet3.add("杭州");
HashSet<String> hashSet4 = new HashSet<>();
hashSet4.add("上海");
hashSet4.add("天津");
HashSet<String> hashSet5 = new HashSet<>();
hashSet5.add("杭州");
hashSet5.add("大连");
//加入到MAP
broadcast.put("k1", hashSet1);
broadcast.put("k2", hashSet2);
broadcast.put("k3", hashSet3);
broadcast.put("k4", hashSet4);
broadcast.put("k5", hashSet5);
//AllAreas存放所有的地区
HashSet<String> allAreas = new HashSet<>();
allAreas.add("北京");
allAreas.add("上海");
allAreas.add("天津");
allAreas.add("广州");
allAreas.add("深圳");
allAreas.add("成都");
allAreas.add("杭州");
allAreas.add("大连");
//创建ArrayList,存放选择的电台集合
ArrayList<String> select = new ArrayList<String>();
//定义一个集合，存放在遍历过程中，当前的电台覆盖的地区和所有地区的交集
HashSet<String> tempSet = new HashSet<String>();
//定义一个maxKey，保存在一次遍历中，能够覆盖最大的未覆盖地区的电台对应的key
//如果maxKey不为null，则会加入到select中
String maxKey = null;
while (allAreas.size() != 0) { //说明还没有覆盖到所有的地区
//每一次循环都需要将maxKey置空
maxKey = null;
//遍历broadCast，找到key中覆盖区域最大的maxKey
for (String key : broadcast.keySet()) {
//每一次循环都需要将tempSet清空
tempSet.clear();
//当前的key能够覆盖的地区
HashSet<String> areas = broadcast.get(key);
tempSet.addAll(areas);
//求出tempSet和allAreas的交集，交集会赋给tempSet
tempSet.retainAll(allAreas);
//如果有交集,并且 没有找到最大的maxKey,或者找到maxKey但是当前集合包含的未覆盖地区的数量比maxKey指向的集合中的未覆盖地区还多，就需要重置maxKey
//tempSet.size() > broadcast.get(maxKey).size()体现出贪心算法的特点
if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcast.get(maxKey).size())) {
maxKey = key;
}
}
//遍历结束后，得到maxKey，如果不为空就加入到select中
if (maxKey != null) {
select.add(maxKey);
//将maxKey指向的广播电台对应的区域从全部地区集合allAreas中去掉
allAreas.removeAll(broadcast.get(maxKey));
}
}
System.out.println(select);
}
}
六、普里姆算法（Prim）
最小生成树问题——连接所有村庄的最短路径
package Algorithm;
import java.util.Arrays;
public class PrimAlgorithm {
public static void main(String[] args) {
char[] data = {'A','B','C','D','E','F','G'};
int vertex = data.length;
//邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
int[][] weight = {
{10000,5,7,10000,10000,10000,2},
{5,10000,10000,9,10000,10000,3},
{7,10000,10000,10000,8,10000,10000},
{10000,9,10000,10000,10000,4,10000},
{10000,10000,8,10000,10000,5,4},
{10000,10000,10000,4,5,10000,6},
{2,3,10000,10000,4,6,10000},};
MGraph mGraph = new MGraph(vertex);
MinTree minTree = new MinTree();
minTree.creatGraph(mGraph, vertex, data, weight);
minTree.showGraph(mGraph);
minTree.Prim(mGraph, 0);
}
}
//创建最小生成树——村庄的图
class MinTree{
//创建图的邻接矩阵
/**
*
* @param graph 图对象
* @param vertex 图对应的顶点个数
* @param data 图的各顶点的值
* @param weight 图的邻接矩阵
*/
public void creatGraph(MGraph graph, int vertex, char[] data, int[][] weight) {
//将顶点的值赋给data
for (int i = 0; i < vertex; i++) {
graph.data[i] = data[i];
//将边的权值赋给邻接矩阵
for (int j = 0; j < weight.length; j++) {
graph.weight[i][j] = weight[i][j];
}
}
}
//显示图的矩阵
public void showGraph(MGraph graph) {
for (int[] link : graph.weight) {
System.out.println(Arrays.toString(link));
}
}
//Prim算法，得到最小生成树
/**
*
* @param graph 图
* @param v 从图的第几个顶点生成，v是下标
*/
public void Prim(MGraph graph, int v) {
//1.创建visited[]数组标记顶点是否被访问过
int[] visited = new int[graph.vertex];
//初始化visited[]
for (int i = 0; i < visited.length; i++) {
visited[i] = 0;
}
//2.把当前节点标记为已访问
visited[v] = 1;
//h1 和h2记录两个顶点的下标
int h1 = -1;
int h2 = -1;
//最短的边
int minWeight = 10000;
//下面开始遍历，确定每一次生成的子图（就是已访问的节点集合），和未被访问过的节点哪一个最近
//k表示边的个数，共有n-1条边，n是顶点个数
for (int k = 0; k < graph.vertex - 1; k++) {
//遍历访问过的节点,这些节点保存在一个集合中
for (int i = 0; i < graph.vertex; i++) {
//遍历没有访问过的节点，这些节点保存在一个集合中
for (int j = 0; j < graph.vertex; j++) {
//如果所有访问过的节点和没有访问过的节点之间的边长小于minWeight，就将minWeight重置，同时记录最小边长的两个顶点的下标h1和h2
if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
minWeight = graph.weight[i][j];
h1 = i;
h2 = j;
}
}
}
//结束循环后，找到最小的一条边
System.out.println("边<" + graph.data[h1] + ", " + graph.data[h2] + ">" + "权值：" + minWeight);
//将找到的节点标记为已访问
visited[h2] = 1;
//minWeight重新设置为10000
minWeight = 10000;
}
}
}
//先创建一个图的邻接矩阵的类
class MGraph{
int vertex; //表示图的节点个数
char[] data; //存放节点数据
int[][] weight; //存放边，邻接矩阵
public MGraph(int vertex){
this.vertex = vertex;
data = new char[vertex];
weight = new int[vertex][vertex];
}
}
七、克鲁斯卡尔算法（Kruskal）
最小生成树——公交站问题
package Algorithm;
import java.util.Arrays;
/*思路分析：
* 1.先构建公交车站图，顶点和邻接矩阵直接传入
* 2.对边按照大小权值排序
* 2.1 先创建一个表示边的类，包括边的两个顶点和边的权值
* 2.2 创建一个获取边的方法，用对象数组存放
* 2.3 创建一个对边进行排序的方法，选择冒泡排序
* 3.编写一个返回顶点下标的方法
* 4.编写一个获取下标为i的顶点的 终点的下标 的方法
* 5.kruskal算法
* 6.打印最小生成树
*/
public class KruskalAlgorithm {
//创建图需要定义的变量
private char[] vertexs; //存放顶点的数组
private int[][] edges; // 存储图对应的邻接矩阵
private int numOfEdges; // 存储边的数目
public static final int INF = Integer.MAX_VALUE; //表示边不连通的值
public static void main(String[] args) {
//顶点
char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邻接矩阵
int[][] edges = {
/*A*//*B*//*C*//*D*//*E*//*F*//*G*/
/*A*/ { 0, 12, INF, INF, INF, 16, 14},
/*B*/ { 12, 0, 10, INF, INF, 7, INF},
/*C*/ { INF, 10, 0, 3, 5, 6, INF},
/*D*/ { INF, INF, 3, 0, 4, INF, INF},
/*E*/ { INF, INF, 5, 4, 0, 2, 8},
/*F*/ { 16, 7, 6, INF, 2, 0, 9},
/*G*/ { 14, INF, INF, INF, 8, 9, 0}};
//创建对象
KruskalAlgorithm kruskalAlgorithm = new KruskalAlgorithm(vertexs, edges);
//打印邻接矩阵
kruskalAlgorithm.showGraph();
//打印边的数组信息
Edges[] e = kruskalAlgorithm.getEdges();
System.out.println("排序前:" + Arrays.toString(e));
kruskalAlgorithm.bubbleSortEdges(e);
System.out.println("排序后:" + Arrays.toString(e));
//krustra方法
kruskalAlgorithm.Kruskal();
}
//构造器
/**
* 需要传进来的信息
* @param vertexs 存放顶点的数组
* @param edges 存储图对应的邻接矩阵
*/
public KruskalAlgorithm(char[] vertexs, int[][] edges){
int vNum = vertexs.length; //顶点个数
//初始化vertexs，edges,numOfEdges这些变量,采用复制拷贝的方式，不会改变传进来的数组
//初始化邻接矩阵
this.edges = new int[vNum][vNum];
for (int i = 0; i < edges.length; i++) {
for (int j = 0; j < edges.length; j++) {
this.edges[i][j] = edges[i][j];
}
}
//初始化顶点数组
this.vertexs = new char[vNum];
for (int i = 0; i < edges.length; i++) {
this.vertexs[i] = vertexs[i];
}
//初始化边的数目
for (int i = 0; i < vNum; i++) {
for (int j = i + 1; j < vNum; j++) { //j = i + 1表示不统计当前节点和自己相连的边
if (this.edges[i][j] != INF) {
//如果两个顶点之间有连线，numOfEdges++
numOfEdges++;
}
}
}
}
//1.打印邻接矩阵
public void showGraph() {
for (int i = 0; i < edges.length; i++) {
for (int j = 0; j < edges.length; j++) {
System.out.printf("%12d\t", edges[i][j]);
}
System.out.println();
}
}
//创建一个方法，将邻接矩阵中的边的信息传到类Edges中，将边的数组Edges[]进行赋值
public Edges[] getEdges() {
int index = 0;
//对象数组，用来存放边的信息
Edges[] edge = new Edges[numOfEdges];
//遍历邻接矩阵，找到所有的边
for (int i = 0; i < edges.length; i++) {
for (int j = i + 1; j < edges.length; j++) { //j = i + 1表示不统计当前节点和自己相连的边
if (edges[i][j] != INF) {
edge[index] = new Edges(vertexs[i], vertexs[j], edges[i][j]);
index++;
}
}
}
return edge;
}
//用冒泡排序对边按照权值大小排序
public void bubbleSortEdges(Edges[] edges) {
int temp;
boolean flag = false;
for (int i = 0; i < edges.length - 1; i++) {
for (int j = 0; j < edges.length - 1 - i; j++) {
if (edges[j].weight > edges[j + 1].weight) {
flag = true;
temp = edges[j].weight;
edges[j].weight = edges[j + 1].weight;
edges[j + 1].weight = temp;
}
}
if (flag == false) {
break;
}else {
flag = false;
}
}
}
//编写一个返回顶点下标的方法
public int getPosition(char ch) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == ch) {
return i;
}
}
return -1;
}
//获取下标为i的顶点的 终点的下标 的方法
/**
* 功能: 获取下标为i的顶点的终点(), 用于后面判断两个顶点的终点是否相同
* @param end 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成
* @param i 表示传入的顶点对应的下标
* @return 返回的就是 下标为i的这个顶点对应的终点的下标
*/
public int getEnd(int[] end, int i) {
while (end[i] != 0) {
i = end[i]; //没有加入的时候认为终点下标就是自己的下标
}
return i;
}
public void Kruskal() {
int index = 0;
int[] end = new int[numOfEdges]; //用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点
//创建结果数组, 保存最后的最小生成树
Edges[] resEdges = new Edges[vertexs.length - 1];
//获取图中所有的边的集合 ，一共有12边
Edges[] allEdges = getEdges();
System.out.println("图的边的集合=" + Arrays.toString(allEdges) + " 共"+ allEdges.length); //12
// 按照边的权值大小进行排序(从小到大)
bubbleSortEdges(allEdges);
//遍历排序后的allEdges数组，将边添加到最小生成树中时，判断准备加入的边是否构成了回路，如果没有，就加入到resEdges中
for (int i = 0; i < numOfEdges; i++) {
//获取到第i条边的第一个顶点(起点)
int p1 = getPosition(allEdges[i].start); //p1=4
//获取到第i条边的第2个顶点
int p2 = getPosition(allEdges[i].end); //p2 = 5
//获取p1这个顶点在已有最小生成树中的终点
int m = getEnd(end, p1); //m = 4
//获取p2这个顶点在已有最小生成树中的终点
int n = getEnd(end, p2); // n = 5
if (m != n) { //没有构成回路
end[m] = n; // 设置p1在"已有最小生成树"中的终点 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0],将E的终点F的下标加入end数组
resEdges[index] = allEdges[i];
index++; //有一条边加入到resEdges数组
}
}
//打印最小生成树
System.out.println("最小生成树为 = " + Arrays.toString(resEdges));
for(int i = 0; i < index; i++) {
System.out.println(resEdges[i]);
}
System.out.println(Arrays.toString(end));
}
}
//创建一个边的类，包含两个顶点和权值
class Edges{
//需要三个变量才能表示边
char start; //边的起点
char end; //边的终点
int weight; //边的权值
//构造器,这三个参数都需要传进来
public Edges(char start, char end, int weight){
//初始化
this.start = start;
this.end = end;
this.weight = weight;
}
//重写toString方法，以便打印边
@Override
public String toString() {
return "Edges [<" + start + ", " + end + ">= " + weight + "]";
}
}
八、迪杰斯特拉算法（Ddijkstra）
最短距离问题
package Algorithm;
import java.util.Arrays;
public class DijkstraAlgorithm {
public static void main(String[] args) {
char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
//邻接矩阵
int[][] matrix = new int[vertex.length][vertex.length];
final int N = 65535;// 表示不可以连接
matrix[0]=new int[]{N,5,7,N,N,N,2};
matrix[1]=new int[]{5,N,N,9,N,N,3};
matrix[2]=new int[]{7,N,N,N,8,N,N};
matrix[3]=new int[]{N,9,N,N,N,4,N};
matrix[4]=new int[]{N,N,8,N,N,5,4};
matrix[5]=new int[]{N,N,N,4,5,N,6};
matrix[6]=new int[]{2,3,N,N,4,6,N};
// 创建 Graph对象
Graph graph = new Graph(vertex, matrix);
//打印邻接矩阵
graph.showGraph();
graph.dsj(6);//C
graph.showDijkstra();
}
}
//先创建图
class Graph{
//三个变量
private char[] vertexs; //存放顶点的数组
private int[][] matrix; //邻接矩阵
private int numOfEdges; // 存储边的数目
public static final int INF = Integer.MAX_VALUE; //表示边不连通的值
private VisitedVertex vv;
//构造器
public Graph(char[] vertexs, int[][] matrix){
int vNum = vertexs.length; //顶点个数
this.matrix = matrix;
this.vertexs = vertexs;
// 初始化边的数目
for (int i = 0; i < vNum; i++) {
for (int j = i + 1; j < vNum; j++) { // j = i + 1表示不统计当前节点和自己相连的边
if (this.matrix[i][j] != INF) {
// 如果两个顶点之间有连线，numOfEdges++
numOfEdges++;
}
}
}
}
// 打印邻接矩阵
public void showGraph() {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
System.out.printf("%5d\t", matrix[i][j]);
}
System.out.println();
}
}
//显示结果
public void showDijkstra() {
vv.show();
}
// 迪杰斯特拉算法实现
/**
* @param index 表示访问顶点对应的下标
*/
public void dsj(int index) {
vv = new VisitedVertex(vertexs.length, index);
update(index);//更新start顶点到周围顶点的距离和前驱顶点
for(int j = 1; j <vertexs.length; j++) {
index = vv.updateArr();// 选择并返回新的访问顶点
update(index); // 更新index顶点到周围顶点的距离和前驱顶点
}
}
//更新index下标顶点到周围顶点的距离，以及周围顶点的前驱顶点,index为访问顶点
private void update(int index) {
// 遍历邻接矩阵中matrix[index]={2,3,N,N,4,6,N}这一行的数据去更新
for (int i = 0; i < matrix[index].length; i++) {
// len 含义是 : 出发顶点到index顶点的距离 + 从index顶点到i顶点的距离的和
int len = vv.getDis(index) + matrix[index][i];
// 如果i顶点没有被访问过，并且 len 小于Dis中已经存在的出发顶点到i顶点的距离，就需要更新Dis中的距离
if (!vv.in(i) && len < vv.getDis(i)) {
vv.updatePre(i, index); // 更新i顶点的前驱为index顶点
vv.updateDis(i, len); // 更新出发顶点到i顶点的距离
}
}
}
}
//已访问顶点集合类
class VisitedVertex {
public static final int INF = Integer.MAX_VALUE; //表示边不连通的值
// 记录各个顶点是否访问过 1表示访问过,0未访问,会动态更新
public int[] already_arr;
// 每个下标对应的值为前一个顶点下标, 会动态更新
public int[] pre_visited;
// 记录出发顶点到其他所有顶点的距离,比如G为出发顶点，就会记录G到其它顶点的距离，会动态更新，求的最短距离就会存放到dis
public int[] dis;
//构造器
/**
*
* @param vlength 表示顶点的个数
* @param index 出发顶点对应的下标, 比如G顶点，下标就是6
*/
public VisitedVertex(int vlength, int index){
//初始化
this.already_arr = new int[vlength];
this.pre_visited = new int[vlength];
this.dis = new int[vlength];
//初始化 dis数组
Arrays.fill(dis, INF);
this.already_arr[index] = 1; //设置出发顶点被访问过
this.dis[index] = 0;//设置出发顶点的访问距离为0
}
/**
* 功能: 判断index顶点是否被访问过
* @param index
* @return 如果访问过，就返回true, 否则访问false
*/
public boolean in(int index) {
return already_arr[index] == 1;
}
/**
* 功能: 更新出发顶点到index顶点的距离
* @param index
* @param len
*/
public void updateDis(int index, int len) {
dis[index] = len;
}
/**
* 功能: 更新index这个顶点的前驱顶点为pre顶点
* @param pre
* @param index
*/
public void updatePre(int index, int pre) {
pre_visited[index] = pre;
}
/**
* 功能:返回出发顶点到index顶点的距离
* @param index
*/
public int getDis(int index) {
return dis[index];
}
/**
* 继续选择并返回新的访问顶点， 比如这里的G 完后，就是 A点作为新的访问顶点(注意不是出发顶点)
* @return
*/
public int updateArr() {
int min = 65535, index = 0;
for(int i = 0; i < already_arr.length; i++) {
if(already_arr[i] == 0 && dis[i] < min ) {
min = dis[i];
index = i;
}
}
//更新 index 顶点被访问过
already_arr[index] = 1;
return index;
}
//显示最后的结果
//即将三个数组的情况输出
public void show() {
System.out.println("==========================");
//输出already_arr
for(int i : already_arr) {
System.out.print(i + " ");
}
System.out.println();
//输出pre_visited
for(int i : pre_visited) {
System.out.print(i + " ");
}
System.out.println();
//输出dis
for(int i : dis) {
System.out.print(i + " ");
}
System.out.println();
//为了好看最后的最短距离，我们处理
char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
int count = 0;
for (int i : dis) {
if (i != 65535) {
System.out.print(vertex[count] + "("+i+") ");
} else {
System.out.println("N ");
}
count++;
}
System.out.println();
}
}
九、弗洛伊德算法（floyd）
找到图中各定点之间最短的距离
package Algorithm;
import java.util.Arrays;
public class FloydAlgorithm {
public static void main(String[] args) {
char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
//创建邻接矩阵
int[][] matrix = new int[vertex.length][vertex.length];
final int N = 65535;
matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 };
matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 };
matrix[2] = new int[] { 7, N, 0, N, 8, N, N };
matrix[3] = new int[] { N, 9, N, 0, N, 4, N };
matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 };
matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 };
matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 };
floydGraph graph = new floydGraph(vertex.length, matrix, vertex);
System.out.println("初始值：");
graph.showDisPre();
System.out.println("floyd算法：");
graph.floyd();
graph.showDisPre();
}
}
//创建图
class floydGraph{
private char[] vertex; //存放顶点的数组
private int[][] dis; // 保存从各个顶点出发到其它顶点的距离，最后的结果，也是保留在该数组
private int[][] pre;// 保存到达目标顶点的前驱顶点
//构造器
/**
*
* @param length 顶点个数
* @param matrix 邻接矩阵
* @param vertex 顶点数组
*/
public floydGraph(int length, int[][] matrix, char[] vertex) {
//初始化
this.vertex = vertex;
this.dis = matrix;
this.pre = new int[length][length];
// 对pre数组初始化, 注意存放的是前驱顶点的下标
for (int i = 0; i < pre.length; i++) {
Arrays.fill(pre[i], i);
}
}
//显示dis数组和前驱数组
public void showDisPre() {
// 为了显示便于阅读，我们优化一下输出
for (int k = 0; k < dis.length; k++) {
// 先将pre数组输出的一行
for (int i = 0; i < dis.length; i++) {
System.out.print(vertex[pre[k][i]] + " ");
}
System.out.println();
// 输出dis数组的一行数据
for (int i = 0; i < dis.length; i++) {
System.out.print("(" + vertex[k] + "到" + vertex[i] + "的最短路径是" + dis[k][i] + ") ");
}
System.out.println();
System.out.println();
}
}
//floyd算法
public void floyd() {
int len = 0; //保存距离的变量
//对中间顶点k遍历，k是下标[A, B, C, D, E, F, G]
for (int k = 0; k < dis.length; k++) {
//对出发顶点i遍历 [A, B, C, D, E, F, G]
for (int i = 0; i < dis.length; i++) {
//对终点j遍历 [A, B, C, D, E, F, G]
for (int j = 0; j < dis.length; j++) {
// 求出从i 顶点出发，经过 k中间顶点，到达 j 顶点距离
len = dis[i][k] + dis[k][j];
if(len < dis[i][j]) {//如果len小于 dis[i][j]
dis[i][j] = len;//更新距离
pre[i][j] = pre[k][j];//更新前驱顶点
}
}
}
}
}
}
十、马踏棋盘算法
package Algorithm;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Comparator;
public class HorseChessBoard {
private static int X; //棋盘的列数
private static int Y; //棋盘的行数
// 创建一个数组，标记棋盘的各个位置是否被访问过
private static boolean visited[][];
// 使用一个属性，标记是否棋盘的所有位置都被访问
private static boolean finished; // 如果为true,表示成功
public static void main(String[] args) {
System.out.println("骑士周游算法，开始运行~~");
X = 8;
Y = 8;
int row = 1; //马儿初始位置的行，从1开始编号
int column = 1; //马儿初始位置的列，从1开始编号
//创建棋盘
int[][] chessboard = new int[X][Y];
visited = new boolean[X][Y];//初始值都是false
// 测试一下耗时
long start = System.currentTimeMillis();
travelChessBoard(chessboard, row - 1, column - 1, 1);
long end = System.currentTimeMillis();
System.out.println("共耗时: " + (end - start) + " 毫秒");
// 输出棋盘的最后情况
for (int[] rows : chessboard) {
for (int step : rows) {
System.out.print(step + "\t");
}
System.out.println();
}
}
/**
* 功能： 根据当前位置(Point对象)，计算马儿还能走哪些位置(Point)，并放入到一个集合中(ArrayList), 最多有8个位置
* @param curPoint
* @return
*/
public static ArrayList<Point> next(Point curPoint) {
//创建一个ArrayList用于存放马能走的位置，x表示列，y表示行
ArrayList<Point> position = new ArrayList<>();
Point p1 = new Point();
// 表示马儿可以走5这个位置
if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
position.add(new Point(p1));
}
// 判断马儿可以走6这个位置
if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
position.add(new Point(p1));
}
// 判断马儿可以走7这个位置
if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
position.add(new Point(p1));
}
// 判断马儿可以走0这个位置
if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
position.add(new Point(p1));
}
// 判断马儿可以走1这个位置
if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
position.add(new Point(p1));
}
// 判断马儿可以走2这个位置
if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
position.add(new Point(p1));
}
// 判断马儿可以走3这个位置
if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
position.add(new Point(p1));
}
// 判断马儿可以走4这个位置
if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
position.add(new Point(p1));
}
return position;
}
//根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数
public static void sort(ArrayList<Point> ps) {
ps.sort(new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
// TODO Auto-generated method stub
//获取到o1的下一步的所有位置个数
int count1 = next(o1).size();
//获取到o2的下一步的所有位置个数
int count2 = next(o2).size();
if(count1 < count2) {
return -1;
} else if (count1 == count2) {
return 0;
} else {
return 1;
}
}
});
}
/**
* 完成骑士周游问题的算法
* @param chessboard 棋盘
* @param row 马儿当前的位置的行 从0开始
* @param column 马儿当前的位置的列 从0开始
* @param step 是第几步 ,初始位置就是第1步
*/
public static void travelChessBoard(int[][] chessboard, int row, int column, int step) {
chessboard[row][column] = step; //将马所在的棋盘位置标记为步数
visited[row][column] = true; //标记该位置已经访问
//当前位置
Point curP = new Point(column,row);
//获取当前位置可以走的下一个位置的集合
ArrayList<Point> nextPosition = next(curP);
//对nextPosition进行排序,排序的规则就是对nextPosition的所有的Point对象的下一步的位置的数目，进行非递减排序
sort(nextPosition);
//遍历nextPosition集合，获取下一步的位置，只要集合中有元素nextPosition.isEmpty()就是false
while (!nextPosition.isEmpty()) {
Point p = nextPosition.remove(0); //获取下一个点的位置
if (visited[p.y][p.x] == false) { //如果还没有访问过
travelChessBoard(chessboard, p.y, p.x, step + 1); //递归遍历
}
}
//判断马是否完成了任务，使用step和应该走的步数比较
//如果没有完成任务，将整个棋盘置0
//说明: step < X * Y 成立的情况有两种
//1. 棋盘到目前位置,仍然没有走完
//2. 棋盘处于一个回溯过程
if (step < X * Y && finished == false) {
chessboard[row][column] = 0;
visited[row][column] = false;
}else {
finished = true;
}
}
}
这篇关于java数据结构与算法（十一）——10种常用算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-26Mybatis官方生成器资料详解与应用教程
- 2024-11-26Mybatis一级缓存资料详解与实战教程
- 2024-11-26Mybatis一级缓存资料详解：新手快速入门
- 2024-11-26SpringBoot3+JDK17搭建后端资料详尽教程
- 2024-11-26Springboot单体架构搭建资料：新手入门教程
- 2024-11-26Springboot单体架构搭建资料详解与实战教程
- 2024-11-26Springboot框架资料：新手入门教程
- 2024-11-26Springboot企业级开发资料入门教程
- 2024-11-26SpringBoot企业级开发资料详解与实战教程
- 2024-11-26Springboot微服务资料：新手入门全攻略
