当前位置:   article > 正文

程序员常用九大算法(二分查找(非递归)、分治、动态规划、KMP、贪心、普里姆、克鲁斯卡尔、迪杰斯特拉、弗洛伊德算法)_程序员常用的十大经典算法

程序员常用的十大经典算法
程序员常用九大算法:

1.二分查找(非递归)
2.分治算法
3.动态规划算法
4.KMP算法
5.贪心算法
6.普里姆算法
7.克鲁斯卡尔算法
8.迪杰斯特拉算法
9.弗洛伊德算法

1.二分查找(非递归):

就是不使用递归的二分查找,这里不做介绍

二分查找代码实现:
public class BinarySearchNoRecur {
	public static void main(String[] args) {
		int[] arr = { 1, 3, 8, 10, 11, 67, 100 };
		int i = binarySearch(arr, 11);
		System.out.println(i);
	}

	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;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
2.分治算法:

比起算法,更像是一种思维
在这里插入图片描述
在这里插入图片描述
分治算法应用场景:
汉诺塔:
在这里插入图片描述
问题分析:
在这里插入图片描述

汉诺塔代码实现:
public class Hanoitower {
	public static void main(String[] args) {
		hanoiTower(6, 'a', 'b', 'c');
	}

	public static void hanoiTower(int num, char a, char b, char c) {
		// 如果只有一个盘
		if (num == 1) {
			System.out.println("第1个盘从 " + a + "->" + c);
		} else {
			// 如果我们有n >= 2情况,我们总是可以看做是两个盘1.最下面一个盘2.上面的盘
			// 1.先把最上面的所有盘A -> B
			//将b参数和c参数互换,下一次递归的任务就是将a移动到b,而不会使用到c,c的使用在下下次递归中
			hanoiTower(num - 1, a, c, b);
			// 2.将最下面的盘A->C
			System.out.println("第" + num + "个盘从 " + a + "->" + c);
			// 3.把B塔的所有盘从B -> C,移动过程使用A塔
			hanoiTower(num - 1, b, a, c);

		}
	}

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
3.动态规划算法:

背包问题(0-1背包):
在这里插入图片描述

思路分析和图解:

左表有基本信息,右表为最优解表
在这里插入图片描述

思路和公式:

在这里插入图片描述

背包问题代码实现(附讲解注释):
import java.util.Arrays;

public class KnapsackProblem {
	public static void main(String[] args) {
		// 物品的重量
		int[] weight = { 1, 4, 3 };
		// 物品的价值
		int[] value = { 1500, 3000, 2000 };
		// 背包的容量
		int capacity = 4;
		// 物品的个数
		int num = weight.length;
		// 创建一个最优解数组(二维数组)
		// v[][]的每一个值都表示一种最优解
		// 例如:
		// v[2][3]表示:当容量为3时,只有前两种物品可选时存在的最优解
		// v[1][2]表示:当容量为2时,只有第一种物品可选时存在的最优解
		int[][] v = new int[num + 1][capacity + 1];

		// 为了记录放入商品的路径,定义一个二维数组
		//如果有新商品加入时,则对应商品数值置为1,否则不处理
		int[][] path = new int[num + 1][capacity + 1];

		// 初始化第一行和第一列,为0
		for (int i = 0; i < v.length; i++) {
			v[i][0] = 0;
		}
		for (int i = 0; i < v[0].length; i++) {
			v[0][i] = 0;
		}

		// 根据公式进行动态规划处理
		for (int i = 1; i < v.length; i++) {// 不处理第一行
			for (int j = 1; j < v[0].length; j++) {// 不处理第一列
				// 如果重量比容量大,则无法放入,最优解为之前的值
				//
				if (weight[i - 1] > j) {
					v[i][j] = v[i - 1][j];
				} else {
					// 如果容量足够,那么最优解可能有两种情况
					// 1.放入物品的价值 + 剩余空间的最优解
					// 2.即使能放入物品,但是最优解不比上次的最优解大
//					v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - weight[i - 1]]);
					if (v[i - 1][j] < value[i - 1] + v[i - 1][j - weight[i - 1]]) {
						v[i][j] = value[i - 1] + v[i - 1][j - weight[i - 1]];
						path[i][j] = 1;
					} else {
						// 如果只是用之前的值替换,则表示没有出现最优解
						v[i][j] = v[i - 1][j];
					}
				}
			}
		}

		for (int[] i : v) {
			System.out.println(Arrays.toString(i));
		}
		for (int[] i : path) {
			System.out.println(Arrays.toString(i));
		}
		int i = path.length - 1;
		int j = path[0].length - 1;
		while (i > 0) {// 逆向遍历
			if (path[i][j] == 1) {
				System.out.printf("第%d个商品放入到背包\n", i);
				j -= weight[i - 1];
			}
			i--;
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
4.KMP算法:

在这里插入图片描述
参考资料:https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

KMP算法代码实现:
public class Kmp {
	public static void main(String[] args) {
		String string1 = "BBC ABCDAB ABCDABCDABDE";
		String string2 = "ABCDABD";
		int[] next = kmpNext("ABCDABD");

		System.out.println(kmpSearch(string1, string2, next));
	}

	/**
	 * 
	 * @param str1 原字符串
	 * @param str2 子串
	 * @param next 部分匹配表,是子串对应的部分匹配表
	 * @return 如果是-1就是没有匹配到,否则返回第一个匹配的位置
	 */
	public static int kmpSearch(String str1, String str2, int[] next) {
		// 遍历
		for (int i = 0, j = 0; i < str1.length(); i++) {

			// KMP核心算法
			while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
				j = next[j - 1];
			}
			if (str1.charAt(i) == str2.charAt(j)) {
				j++;
			}
			if (j == str2.length()) {
				return i - j + 1;
			}
		}
		return -1;
	}

	// 获取到一个字符串的部分匹配值表
	public static int[] kmpNext(String dest) {
		// 创建一个next数组保存部分匹配值
		int[] next = new int[dest.length()];
		// 第一个肯定是0,因为长度为一,没有前缀和后缀
		next[0] = 0;// 如果字符串时长度为1部分匹配值就是0
		for (int i = 1, j = 0; i < dest.length(); i++) {

			// 当dest.chatAt(i) != dest.chatAt(j),我们需要从next[j-1]获取新的j
			// 直到发现有dest.chatAt(i) == dest.chatAt(j)时退出、
			// 要j大于0才走这里
			while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
				j = next[j - 1];
			}
			// 当dest.chatAt(i) == dest.chatAt(j)满足时,部分匹配值就是+1
			if (dest.charAt(i) == dest.charAt(j)) {
				j++;
			}
			next[i] = j;
		}

		return next;

	}

	// 暴力匹配
	public static int violenceMatch(String str1, String str2) {
		char[] s1 = str1.toCharArray();
		char[] s2 = str2.toCharArray();
		boolean flag = false;
		int s1len = s1.length;
		int s2len = s2.length;
		int i = 0;
		int j = 0;
		while (i < s1len && j < s2len) {
			if (s1[i] == s2[j]) {
				i++;
				j++;
			} else {
				i = i - (j - 1);
				j = 0;
			}
		}
		if (j == s2len) {
			return i - j;
		} else {
			return -1;
		}

	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
5.贪心算法:

在这里插入图片描述

贪心算法应用场景:

在这里插入图片描述

利用贪心算法解题代码:
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class Greedy {
	public static void main(String[] args) {
		HashMap<String, HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
		HashSet<String> hashset1 = new HashSet<String>();
		hashset1.add("北京");
		hashset1.add("上海");
		hashset1.add("天津");

		HashSet<String> hashset2 = new HashSet<String>();
		hashset2.add("北京");
		hashset2.add("广州");
		hashset2.add("深圳");

		HashSet<String> hashset3 = new HashSet<String>();
		hashset3.add("成都");
		hashset3.add("上海");
		hashset3.add("杭州");

		HashSet<String> hashset4 = new HashSet<String>();
		hashset4.add("天津");
		hashset4.add("上海");

		HashSet<String> hashset5 = new HashSet<String>();
		hashset5.add("杭州");
		hashset5.add("大连");

		broadcasts.put("K1", hashset1);
		broadcasts.put("K2", hashset2);
		broadcasts.put("K3", hashset3);
		broadcasts.put("K4", hashset4);
		broadcasts.put("K5", hashset5);

		// allAreas,如果覆盖到其中一个地区,就会移除地区,如果全覆盖,则为空
		HashSet<String> allAreas = new HashSet<String>();
		allAreas.add("北京");
		allAreas.add("上海");
		allAreas.add("天津");
		allAreas.add("杭州");
		allAreas.add("大连");
		allAreas.add("成都");
		allAreas.add("广州");
		allAreas.add("深圳");

		// 创建ArrayList,存放选择的电台集合
		ArrayList<String> selects = new ArrayList<String>();
		String maxKey = null;

		HashSet<String> tempSet = new HashSet<String>();
		
		
		while (allAreas.size() != 0) {

			
			maxKey = null;

			for (String key : broadcasts.keySet()) {
				tempSet.clear();
				HashSet<String> areas = broadcasts.get(key);
				tempSet.addAll(areas);

				// 求出交集
				tempSet.retainAll(allAreas);
				// 求交集后,如果大小大于0,则表示还能覆盖新的地区,如果不大于零,就没有必要加入
				//如果maxKey为空,则赋值当前的key
				//如果maxKey不为空,则保存的是上次的最大覆盖地区key
				//如果当前这个集合包含的未覆盖地区的数量,比maxKey指向的集合未覆盖的地区还多,就重置maxKey
				if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
					maxKey = key;
				}
			}
			if (maxKey != null) {
				//加入选择
				selects.add(maxKey);
				//移除已添加的地区
				allAreas.removeAll(broadcasts.get(maxKey));

			}
		}
		//当退出循环后,则就按照贪心算法得到一个解
		System.out.println(selects);

	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
6.普里姆算法:

在这里插入图片描述

普里姆算法应用场景:

在这里插入图片描述

利用普里姆算法解题代码:
import java.util.Arrays;

public class Prim {
	public static void main(String[] args) {
		char[] data = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		int verxs = data.length;

		int[][] weight = new int[][] { { 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(verxs);
		MinTree minTree = new MinTree();
		minTree.createGraph(mGraph, verxs, data, weight);
		minTree.showGaph(mGraph);
		minTree.prim(mGraph, 1);
	}
}

//创建最小生成树 -> 村庄的图
class MinTree {
	/**
	 * 
	 * @param graph  图对象
	 * @param verxs  图对应的顶点个数
	 * @param data   图的各个顶点的值
	 * @param weight 图的邻接矩阵
	 */
	public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
		int i, j;
		for (i = 0; i < verxs; i++) {
			graph.data[i] = data[i];
			for (j = 0; j < verxs; j++) {
				graph.weight[i][j] = weight[i][j];
			}
		}
	}

	public void showGaph(MGraph graph) {
		for (int i = 0; i < graph.weight.length; i++) {
			System.out.println(Arrays.toString(graph.weight[i]));
		}
	}

	/**
	 * 
	 * @param graph 图
	 * @param value 表示从图的第一个顶点开始生成,就是起点的下标
	 */
	public void prim(MGraph graph, int value) {
		int[] visited = new int[graph.verxs];
		visited[value] = 1;

		int h1 = -1;
		int h2 = -1;
		int minWeight = 10000;
		for (int k = 1; k < graph.verxs; k++) {//因为有graph.verxs顶点,普利姆算法借宿后,有graph.verxs-1边

			// 这个是确定每一次生成的子图,和那个结点的距离最近
			// 以下的双重循环是为了遍历每一条边,i为起点的下标,j为终点的下标
			for (int i = 0; i < graph.verxs; i++) {// i结点表示被访问的结点
				for (int j = 0; j < graph.verxs; j++) {// j结点表示还没有访问过的结点
					//当然这样做有点冗余
					//这里需要过滤一下,i已访问,j未访问才是需要的
					//并在这些条件下挑出距离最小的那一个
					if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
						// 替代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 verxs;// 表示圆的结点个数
	char[] data;// 存放节点数据
	int[][] weight;// 存放边,就是我们的邻接矩阵

	public MGraph(int verxs) {
		this.verxs = verxs;
		data = new char[verxs];
		weight = new int[verxs][verxs];
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
7.克鲁斯卡尔算法:

在这里插入图片描述

克鲁斯卡尔算法应用场景:

在这里插入图片描述

利用克鲁斯卡尔算法解题代码:
import java.util.Arrays;

public class Kruskal {

	public int edgeNum;// 边的个数
	public char[] vertexs;// 顶点数组
	public int[][] matrix;// 邻接矩阵

	public static final int INF = Integer.MAX_VALUE;

	public static void main(String[] args) {
		char[] vertexs = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		int matrix[][] = {
				/* 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 } };
		Kruskal kruskal = new Kruskal(vertexs, matrix);
		kruskal.kruskal();
//		kruskal.print();

	}

	public Kruskal(char[] vertexs, int[][] matrix) {
		int vlen = vertexs.length;
		this.vertexs = new char[vlen];
		// 使用复制的方式
		this.vertexs = vertexs.clone();
		this.matrix = matrix.clone();

		for (int i = 0; i < matrix.length; i++) {
			for (int j = i + 1; j < matrix[0].length; j++) {
				if (matrix[i][j] != INF) {
					edgeNum++;
				}
			}
		}
	}

	public void print() {
		System.out.println("邻接矩阵:");
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				System.out.printf("%10d\t", matrix[i][j]);
			}
			System.out.println();
		}

	}

	public void sortEdges(EData[] edges) {
		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) {
					EData tempData = edges[j];
					edges[j] = edges[j + 1];
					edges[j + 1] = tempData;
				}

			}
		}
	}

	/**
	 * 
	 * @param ch
	 * @return 返回下标
	 */
	public int getPosition(char ch) {
		for (int i = 0; i < vertexs.length; i++) {
			if (vertexs[i] == ch) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 功能:获取图中的边, 通过matrix 邻接矩阵类获取
	 * 
	 * @return
	 */
	public EData[] getEdges() {
		int index = 0;
		EData[] edges = new EData[edgeNum];
		for (int i = 0; i < vertexs.length; i++) {
			for (int j = i + 1; j < vertexs.length; j++) {
				if (matrix[i][j] != INF) {
					edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);

				}
			}
		}
		return edges;
	}

	/**
	 * 功能:获取下标 为 i 的顶点的终点,用于后面判断两个顶点的终点是否相同
	 * 
	 * @param ends:数组就是记录了各个顶点对应的终点是哪个,ends数组是在遍历过程中,逐步形成
	 * @param i:表示传入的顶点对应的下标
	 * @return 返回的就是下标为 i 的这个顶点对应的终点的下标
	 * 
	 */
	public int getEnd(int[] ends, int i) {
		while (ends[i] != 0) {
			i = ends[i];
		}
		System.out.println("End:"+Arrays.toString(ends));
		return i;
	}

	public void kruskal() {
		int index = 0;// 表示最后结果数组的索引
		int[] ends = new int[edgeNum];// 用于保存
		EData[] rets = new EData[edgeNum];
		EData[] edges = getEdges();
		sortEdges(edges);

		for (int i = 0; i < edgeNum; i++) {
			int p1 = getPosition(edges[i].start);
			int p2 = getPosition(edges[i].end);

			int m = getEnd(ends, p1);// m = 4
			int n = getEnd(ends, p2);// n = 5

			// 是否构成回路
			if (m != n) {
				ends[m] = n;
				rets[index++] = edges[i];
			}
		}
		for (int i = 0; i < index; i++) {
			System.out.println(rets[i]);
		}
	}

}

//创建边的类
class EData {
	char start;// 起点
	char end;// 终点
	int weight;// 权值

	public EData(char start, char end, int weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}

	@Override
	public String toString() {
		return "[EData <" + start + ", " + end + "> weight=" + weight + "]";
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
8.迪杰斯特拉算法:

在这里插入图片描述

迪杰斯特拉算法应用场景:

在这里插入图片描述

利用迪杰斯特拉算法解题代码:
import java.util.Arrays;

public class Dijkstra {
	public static void main(String[] args) {
		
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		final int N = 65535;
		
		int[][] matrix = new int[][] { 
			{ N, 5, 7, N, N, N, 2 },
			{ 5, N, N, 9, N, N, 3 },
			{ 7, N, N, N, 8, N, N },
			{ N, 9, N, N, N, 4, N },
			{ N, N, 8, N, N, 5, 4 },
			{ N, N, N, 4, 5, N, 6 },
			{ 2, 3, N, N, 4, 6, N },
		};
		Graph graph = new Graph(vertex, matrix);
//		graph.showGraph();
		graph.dsj(6);
		graph.showDjs();

	}
}

class Graph {
	public char[] vertex;
	public int[][] matrix;
	// 已经访问的顶点的集合
	public VisitedVertex vv;

	public Graph(char[] vertex, int[][] matrix) {
		this.vertex = vertex;
		this.matrix = matrix;
	}

	public void showDjs() {
		vv.show();
	}

	public void showGraph() {
		for (int[] i : matrix) {
			System.out.println(Arrays.toString(i));
		}
	}

	/**
	 * 
	 * @param index 表示出发顶点对应的下标
	 */
	public void dsj(int index) {
		//新创建的已访问数组
		vv = new VisitedVertex(vertex.length, index);
		//首先更新一下起点
		update(index);
		for (int j = 1; j < vertex.length; j++) {
			index = vv.updateArr();
			update(index);
		}
	}

	// 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
	public void update(int index) {
		int len = 0;
		// 根据遍历我们的邻接矩阵的 matrix[index]行
		for (int j = 0; j < matrix[index].length; j++) {
			// len含义是:出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和
			//一开始dis的值都是65535
			len = vv.getDis(index) + matrix[index][j];
			// 如果j没有被访问过,并且len小于出发顶点到j顶点的距离,就需要更新
			if (!vv.in(j) && len < vv.getDis(j)) {
				vv.updatePre(j, index);// 更新j顶点的前驱为index顶点
				vv.updateDis(j, len);// 更新出发顶点到j顶点的距离
			}

		}
	}

}

//已访问顶点的集合
class VisitedVertex {
	// 记录各个顶点是否访问过,1表示访问过,0表示未访问,会动态更新
	public int[] already_arr;
	// 每个小标对应的值为前一个顶点下标,会动态更新
	public int[] pre_visited;
//	记录出发顶点到其他所有顶点的距离,比如G为出发顶点,就会记录G到其他顶点的距离,会动态更新,求的最短距离就会存放到dis
	public int[] dis;

	/**
	 * 
	 * @param lenght 表示顶点的个数
	 * @param index  表示出发顶点对应的下标
	 */
	public VisitedVertex(int lenght, int index) {
		this.already_arr = new int[lenght];
		this.pre_visited = new int[lenght];
		this.dis = new int[lenght];

		// 初始化dis数组
		Arrays.fill(dis, 65535);
		// 设置出发顶点的访问距离为0
		this.dis[index] = 0;

		this.already_arr[index] = 1;
	}

	/**
	 * 功能:判断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结点
	 * 
	 * @param pre
	 * @param index
	 */
	public void updatePre(int pre, int index) {
		pre_visited[pre] = index;
	}

	/**
	 * 功能:返回出发顶点到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;
			}
		}
		already_arr[index] = 1;
		return index;
	}

	public void show() {
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'D', 'G' };
		int count = 0;
		for (int i : dis) {
			if (i != 65535) {
				System.out.print(vertex[count++] + "(" + i + ")");
			}
		}
	}

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
9.弗洛伊德算法:

在这里插入图片描述

弗洛伊德算法应用场景:

在这里插入图片描述

利用弗洛伊德算法解题代码:
import java.util.Arrays;

public class Floyd {
	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 };

		Graph2 graph = new Graph2(vertex.length, matrix, vertex);
		graph.floyd();
		graph.show();
	}
}

class Graph2 {
	public char[] vertex;// 存放顶点
	public int[][] dis;// 保存,从各个顶点出发到其他顶点的距离,最后的结构,也是保存在该数组
	public int[][] pre;// 前驱

	public Graph2(int length, int[][] matrix, char[] vertex) {
		this.vertex = vertex;
		this.dis = matrix;
		this.pre = new int[length][length];
		// 对pre数组初始化
		// 一开始前驱是本身
		for (int i = 0; i < length; i++) {
			Arrays.fill(pre[i], i);
		}
	}

	public void show() {
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		for (int k = 0; k < dis.length; k++) {

			for (int i = 0; i < dis.length; i++) {
				System.out.print(vertex[pre[k][i]] + " ");
			}
			System.out.println();
			for (int i = 0; i < dis.length; i++) {
				System.out.print("(" + vertex[k] + "到" + vertex[i] + "的最短路径是" + dis[k][i] + ")");
			}
			System.out.println();
			System.out.println();
		}
	}

	public void floyd() {
		int len = 0;
		// 从中间顶点的遍历
		for (int k = 0; k < dis.length; k++) {
			// 从i顶点出发a、b、c、d、。。。
			for (int i = 0; i < dis.length; i++) {
				for (int j = 0; j < dis.length; j++) {
					len = dis[i][k] + dis[k][j];// 求出i顶点出发,经过k中间点,到达j顶点距离
					if (len < dis[i][j]) {// 如果小于直连距离
						dis[i][j] = len;
						pre[i][j] = pre[k][j];
					}
				}
			}
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/896691
推荐阅读
相关标签
  

闽ICP备14008679号