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种常用算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程