package com.qin.Algorithm;
//二分查找算法
//要求数组必须有序
public class BinarySearchNoRecursion {
public static void main(String[] args) {
int arr[] = {1,3,8,10,11,67,100};
int index = binarySearch(arr,100);
if (index==-1){
System.out.println("没有找到");
}else {
System.out.println("被查找的数下标为:"+index);
}
}
//二分查找的非递归实现
//arr 被找的数组，target返回被查找的下标
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 com.qin.Algorithm;
//分治算法
public class DivideAndConquer {
public static void main(String[] args) {
//目标把A柱子中的盘子移动到C柱子，并从低到高，从大到小
hanoiTower(2,'A','B','C');
}
//汉诺塔移动的方法
//使用分治算法
//num 有几个圆盘 ，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的情况，我们总是可以看做两个盘，最下边的一个盘2和上面的所有盘1
//1.先把最上面的所有盘A->B,移动过程会使用到c
hanoiTower(num - 1,a,c,b);
//2.把最下面的盘移动到A->C
System.out.println("第"+num+"个盘从"+a+"->"+c);
//3.把b塔的所有盘从b->c
hanoiTower(num-1,b,a,c);
}
}
}
package com.qin.Algorithm;
public class KnapsackProblem {
public static void main(String[] args) {
int[] w = {1,4,3} ; //物品的重量
int[] val = {1500,3000,2000};//物品的价值
int m = 4 ; //背包的容量
int n = val.length; //物品的个数
//填表：为了记录 放入商品的情况我们定义一个二维数组
int[][] path = new int[n+1][m+1];
//创建一个二维数组
//v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大的价值
int[][] v = new int[n+1][m+1];
//初始化第一行和第一列，这里在本程序中可以不处处理，因为默认为0
for (int i = 0; i < v.length; i++) {
v[i][0] = 0 ; //把第一列设置为0
}
for (int i = 0; i < v[0].length; i++) {
v[0][i] = 0; //将第一行设置为0
}
//根据前面的到的公式来动态规划
for (int i = 1; i < v.length; i++) { //不处理第一行,行代表的是物品的种类
for (int j = 1; j < v[0].length; j++) { //代表不处理第一列，列代表的是重量
//公式
//因为我们的程序i是从1开始的，因此原来的公式中w[i]修改成w[i-1]
if (w[i-1]>j) { //物品的重量大于当前背包的容量
//就把当前方案的上一行的方案赋给这一行
v[i][j] = v[i-1][j] ;
}else { //物品的重量小于当前背包的容量时
/*
因为我们的程序i是从1开始的，因此调整为val[i-1]+v[i-1][j-w[i]]
v[i-1][j]指的是上一行同等重量下的的最佳方案的价格
val[i-1]指的是这次的物品价值，因为i是从1开始的，而我们的数组下标是从0开始的
v[i-1][j-w[i]]指的是上一行重量范围内最佳方案的价格
v[i][j] = Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
为了记录商品存放到背包的情况，我们不能简单的使用上面的公式，需要使用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
path[i][j] = 1;
}else {
v[i][j] = v[i-1][j];
}
}
}
}
//输出一下v，看看目前情况
System.out.println("建表情况");
for (int[] a : v){
for (int i = 0; i < a.length; i++) {
System.out.printf("%d\t",a[i]);
}
System.out.println();
}
System.out.println("============");
for (int[] i:path){
for (int j = 0; j < i.length; j++) {
System.out.printf("%d\t",i[j]);
}
System.out.println();
}
//输出我们放入的是那些商品
System.out.println("在一定重量下的最大价值存放方案");
int i= path.length-1; //行的最大下标
int j = path[0].length-1; //列的最大下标
while (i>0){ //从path最后开始找
if (path[i][j]==1){
System.out.printf("第%d个商品放入到背包\n",i);
j-=w[i-1];
}
i--;
}
}
}
package com.qin.Algorithm;
//暴力匹配算法
public class ViolenceMatch {
public static void main(String[] args) {
String str1 = "秦小东是张伟爸爸的爷爷";
String str2 = "张伟爸爸的";
int i = violenceMatch(str1, str2);
if (i == -1){
System.out.println("信息不匹配");
}else {
System.out.println("开始下标为"+i);
}
}
//暴力匹配算法实现
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){
return i - j;
}else {
return -1;
}
}
}
重点：已匹配数-部分匹配表=位移数
代码实现
package com.qin.Algorithm;
import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;
import java.util.Arrays;
//KMP算法
public class KMP {
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
int[] next = kmpNext(str2); //[0,1]
System.out.println("next="+ Arrays.toString(next));
System.out.println("====================");
int i = kmpSearch(str1, str2, next);
if (i==-1){
System.out.println("没有找到");
}else {
System.out.println("开始下标为"+i);
}
}
//获取到一个字符串（子串）的部分匹配值
public static int[] kmpNext(String dest){
//创建一个next数组保存部分匹配值
int[] next = new int[dest.length()];
next[0] = 0; //如果字符串长度为1，部分匹配值就是0
for (int i = 1,j = 0; i < dest.length(); i++) {
//当dest.charAt(i)!=dest.charAt(j)，我们就需要从next[j-1]获取新的j
//知道我们发现有dest.charAt(i)==dest.charAt(j)成立才退出
//这是kmp的核心点
while (j>0 && dest.charAt(i)!=dest.charAt(j)){
j = next[j - 1];
}
//当dest.charAt(i)==dest.charAt(j)这个条件满足时
//部分匹配值就是加1
if (dest.charAt(i)==dest.charAt(j)){
j++;
}
next[i] = j;
}
return next;
}
//写出我们的kmp搜索算法
public static int kmpSearch(String s1,String s2,int[] next){
//遍历str1
for (int i = 0,j = 0; i < s1.length(); i++) {
//需要考虑s1.charAt(i)！=s2.charAt(j)，核心点
while (j>0 && s1.charAt(i)!=s2.charAt(j)){
j = next[j-1];
}
if (s1.charAt(i)==s2.charAt(j)){
j++;
}
if(j==s2.length()){ //找到了
return i-j+1;
}
}
return -1;
}
}
package com.qin.Algorithm;
import javax.print.DocFlavor;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
//贪心算法
public class GreedyAlgorithm {
public static void main(String[] args) {
//创建广播电台，放入到Map中
HashMap<String, HashSet<String>> broadcasts= new HashMap<>();
//将各个电台放入到broadcasts
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("大连");
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<>();
allAreas.add("北京");
allAreas.add("上海");
allAreas.add("天津");
allAreas.add("广州");
allAreas.add("深圳");
allAreas.add("成都");
allAreas.add("杭州");
allAreas.add("大连");
//创建一个ArrayList,存放选择的电台集合
ArrayList<String> selects = new ArrayList<>();
//定义一个临时的集合，在遍历过程中，存放遍历过程中的电台覆盖的地区
HashSet<String> tempSet = new HashSet<>();
//定义一个maxKey，保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
//如果maxKey不为空，则会加入到selects里面
String maxKey = null;
while (allAreas.size()!=0){ //如果不为0，则表示还没有覆盖到所有地区
//每进行一次while循环都需要把maxKey制空
maxKey = null;
//遍历broadcast,取出对应的key
for (String key:broadcasts.keySet()){ //拿到hashMap中的k的数组
//每进行一次for循环就需要把tempSet清空
tempSet.clear();
//当前这个key能够覆盖的地区
HashSet<String> areas = broadcasts.get(key);
tempSet.addAll(areas);
//求出tempSet和allAreas的交集，交集会赋给tempSet
tempSet.retainAll(allAreas);
//如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合覆盖的地区还多
//就需要重置maxKey
if (tempSet.size()>0&&
//tempSet.size()>broadcasts.get(maxKey).size())体现出贪心算法的核心
(maxKey==null||tempSet.size()>broadcasts.get(maxKey).size())){
maxKey = key;
}
}
//如果maxKey!=null，就应该讲maxKey加入selects中
if (maxKey!=null){
selects.add(maxKey);
//将maxKey指向的广播电台从broadcasts中取出
allAreas.removeAll(broadcasts.get(maxKey));
}
}
System.out.println("得到的选择结果"+selects);
}
}
package com.qin.Algorithm;
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 num = 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 graph = new MGraph(num);
//创建一个MinTree对象
MinTree minTree = new MinTree();
minTree.createGraph(graph,num,data,weight);
//打印图
minTree.showGraph(graph);
//测速普利姆算法
minTree.prim(graph,1);
}
}
class MGraph{
int num; //表示图的节点个数
char[] data; //存放节点数据
int[][] weight; //存放边的权值，就是我们的邻接矩阵
public MGraph(int num) {
this.num = num;
data = new char[num];
weight = new int[num][num];
}
}
//创建最小生成树->村庄的图
class MinTree{
//创建图的邻接矩阵
//graph 图对象 num 图对应的顶点个数 data图的各个顶点的值 weight图的邻接矩阵
public void createGraph(MGraph graph,int num,char data[],int[][] weight){
int i,j;
for (i=0;i<num;i++){ //顶点
graph.data[i] = data[i];
for (j=0;j<num;j++){
graph.weight[i][j] = weight[i][j];
}
}
}
//显示图的方法
public void showGraph(MGraph graph){
for (int[] link:graph.weight) {
System.out.println(Arrays.toString(link));
}
}
//编写普利姆算法，得到最小生成树
//graph 这个是图 ，v 这个是从第几个顶点开始生成 'A'-> 0
public void prim(MGraph graph,int v){
//visited 标记顶点是否被访问过
//visited 默认元素都是0 ，代表没有被访问过
int[] visited = new int[graph.num];
//把当前节点标记为已经访问过了
visited[v] = 1;
//h1,h2记录两个顶点的下标
int h1 = -1;
int h2 = -1;
int minWeight = 10000; //将minWeight初始成一个大数，后面在遍历过程中会被替换
for (int k = 1; k < graph.num; k++) { //graph.num个顶点，普利姆算法结束后有graph.num-1条边
//这个是确定每一次生成的子图，和那个节点的距离最近
for (int i = 0; i < graph.num; i++) { //i节点表示被访问过的节点
for (int j = 0; j < graph.num; j++) { //j节点表示还没有被访问过的节点
if (visited[i]==1&&visited[j]==0&&graph.weight[i][j]<minWeight){
//替换minWeight（寻找已经访问过的节点和未访问过的节点中权值最小的边）
minWeight = graph.weight[i][j];
h1 = i;
h2 = j;
}
}
}
//推出了这个for循环，找到了一条最小的边
System.out.println("边<"+graph.data[h1]+","+graph.data[h2]+">权值:"+minWeight);
//将当前节点标记为已经访问过的
visited[h2] = 1;
//重新设置为最大值10000
minWeight = 10000;
}
}
}
那么如何判断是否构成回路?
我们顶点的创建是按照ABCDEFG的顺序来创建的，那么在CDEF这几个点中，F是最大的，所以F是CDE的终点
package com.qin.Algorithm;
import java.util.Arrays;
//克鲁斯卡尔算法
public class KruskalCase {
private int edgeNum;//边的个数
private char[] vertexs; //顶点的数组
private int[][] matrix; //邻接矩阵,边
//使用INF表示两个顶点不能连通
private static final int INF = Integer.MAX_VALUE;
public KruskalCase(char[] vertexs,int[][] matrix) {
//初始化顶点数和边的个数
int vlen = vertexs.length;
//初始化顶点
this.vertexs = new char[vlen];
for (int i = 0; i < vertexs.length ; i++) {
this.vertexs[i] = vertexs[i];
}
//初始化边,使用的是复制拷贝的方式
this.matrix = new int[vlen][vlen];
for (int i = 0; i< vlen;i++){
for (int j = 0; j < vlen ; j++) {
this.matrix[i][j] = matrix[i][j];
}
}
//统计边
for (int i = 0; i < vlen; i++) {
for (int j = i+1; j < vlen ; j++) {
if (this.matrix[i][j]!=INF){
edgeNum++;
}
}
}
}
//打印邻接矩阵
public void print(){
System.out.println("邻接矩阵为：\n");
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
System.out.printf("%10d\t",matrix[i][j]);
}
System.out.println();
}
}
//对边进行排序，冒泡
private 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 tmp = edges[j];
edges[j] = edges[j+1];
edges[j+1] = tmp;
}
}
}
}
//ch顶点的值，比如'A','B'
//返回ch对应的下标，如果找不到，返回-1
private int getPosition(char ch){
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == ch){ //找到
return i;
}
}
return -1;
}
//获取图中的边，放到EData[]数组中，后面我们需要遍历该数组
//是通过matrix 邻接矩阵来获取
//EData[] 形式[['A','B',12],['B','F',7],。。。。]
private 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的顶点的终点，用于后面判断两个顶点的终点是否相同
//ends: 数组就是记录了各个顶点对应的终点是哪个
//i 表示传入的顶点对应的下标
//返回的就是下标为i的这个顶点的终点的下标
private int getEnd(int[] ends,int i){
while (ends[i]!=0){
i = ends[i];
}
return i;
}
public void kruskal() {
int index = 0; //表示最后一个结果数组的索引
int[] ends = new int[edgeNum]; //用于保存"已有最小生成树"的终点
//创建结果数组，保存我们最后的最小生成树
EData[] rets = new EData[edgeNum];
//获取图中所有边的集合，一共有12边
EData[] edges = getEdges();
System.out.println("图的边的集合=" + Arrays.toString(edges) + "共" + edges.length);
//排序，按照边的权值大小进行排序（从小到大）
sortEdges(edges);
//遍历edges数组，将添加到最小生成树，判断是否形成回路，如果没有就加入rets,否则不能加入
for (int i = 0; i < edgeNum; i++) {
//获取到第i条边的第一个顶点
int p1 = getPosition(edges[i].start);
//获取到第i条边的第二个顶点
int p2 = getPosition(edges[i].end);
//获取p1这个顶点在我们已有的最小生成树中的终点
int m = getEnd(ends,p1);
//获取平p2这个顶点在我们已有的最小生成树中的终点
int n = getEnd(ends,p2);
//判断是否构成回路
if (m!=n){ //没有构成回路
ends[m] = n; //设置m在已有生成树的终点
rets[index++] = edges[i]; //有一条边加入到rets数组
}
}
//统计并打印最小生成树
for (int i = 0; i < index; i++) {
System.out.println(rets[i]);
}
}
public static void main(String[] args) {
char[] vertexs = {'A','B','C','D','E','F','G'};
int[][] matrix= {
{0,12,INF,INF,INF,16,14},
{12,0,10,INF,INF,7,INF},
{INF,10,0,3,5,6,INF},
{INF,INF,3,0,4,INF,INF},
{INF,INF,5,4,0,2,8},
{16,7,6,INF,2,0,9},
{14,INF,INF,INF,8,9,0}
};
//创建克鲁斯卡尔对象是咧
KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
kruskalCase.print();
EData[] edges = kruskalCase.getEdges();
System.out.println("=====================");
System.out.println("未排序");
System.out.println(Arrays.toString(kruskalCase.getEdges()));
System.out.println("排序后");
kruskalCase.sortEdges(edges);
System.out.println(Arrays.toString(edges));
kruskalCase.kruskal();
}
}
//创建一个类EData，他的对象实例就表示一条边
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=" + start +
", end=" + end +
", weight=" + weight +
'}';
}
}
package com.qin.Algorithm;
import com.sun.java.swing.plaf.windows.WindowsDesktopIconUI;
import java.util.Arrays;
//迪杰斯特拉算法
public class DijkstraAlgorithm {
public static void main(String[] args) {
char[] vertex = {'A','B','C','D','F','E','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 = new Graph(vertex, matrix);
System.out.println("打印邻接矩阵");
graph.showGraph();
System.out.println("============");
System.out.println("测试迪杰斯特拉算法");
graph.djs(6);
graph.showDijkstra();
}
}
class Graph{
private char[] vertex; //顶点数组
private int[][] matrix; //邻接矩阵
private VisitedVertex vv; //已经访问顶点的所有信息
public Graph(char[] vertex, int[][] matrix) {
this.vertex = vertex;
this.matrix = matrix;
}
//显示图的方法
public void showGraph(){
for(int i = 0; i < matrix.length ; i++){
for (int j = 0; j < matrix[i].length ; j++) {
System.out.printf("%7d\t",matrix[i][j]);
}
System.out.println();
}
}
//迪杰斯特拉算法
//index 表示出发顶点对应的下标
public void djs(int index){
vv = new VisitedVertex(vertex.length, index);
update(index); //更新index顶点到走周围顶点的距离和前驱顶点
for (int i = 1; i < vertex.length; i++) {
index = vv.updateArr(); //选择并访问新的访问顶点
update(index);
}
}
//更新index下标顶点到周围顶点的距离和周围顶点的前驱结点
private void update(int index){
int len = 0;
//根据遍历我们的邻接矩阵的matrix[index]行
for (int i = 0; i < matrix[index].length; i++) {
// len 含义是出发顶点到index顶点的距离 + 从index顶点到i顶点的距离
len = vv.getDis(index) + matrix[index][i];
//如果当前i节点没有被访问过和len小于出发顶点到i顶点的距离
if (!vv.in(i) && len < vv.getDis(i)){
vv.updatePre(i,index); //更新i节点的前驱结点
vv.updateDis(i,len); //跟新出发顶点到i顶点的最短距离
}
}
}
//显示最后结果
public void showDijkstra(){
vv.show();
}
}
class VisitedVertex{ //已访问顶点集合
public int[] already_arr; //记录每个顶点是否被访问过，1表示访问过，0表示未访问，会动态更新
//每个下标对应的值为前一个顶点的下标，会动态更新
public int[] pre_visited;
//记录出发顶点到其他所有顶点的距离，比如G为出发点，就会记录G到其他顶点的距离，会动态更新，求得到的最短距离就会放在dis中
public int[] dis;
//构造器
//length 表示顶点的个数，index 表示出发顶点对应的下标
public VisitedVertex(int length,int index) {
this.already_arr = new int[length];
this.pre_visited = new int[length];
this.dis = new int[length];
//初始化dis
Arrays.fill(dis,65535); //设置其他顶点的距离为65535
this.already_arr[index] = 1; //设置出发顶点被访问过
this.dis[index] = 0; //设置出发顶点的访问距离为0
}
//判断index顶点是否被访问过，如果访问过就返回true
public boolean in(int index){
return already_arr[index] == 1;
}
//更新出发顶点到index顶点的距离
public void updateDis(int index,int len){
dis[index] = len;
}
//更新pre顶点的前驱顶点为index节点
public void updatePre(int pre,int index){
pre_visited[pre] = index; //下标为pre的顶点的前驱节点为index
}
//返回出发顶点到index顶点的距离
public int getDis(int index){
return dis[index];
}
//继续选择并返回新的访问节点，比如这里G完后，就是A作为新的访问节点（注意不是出发节点 ）
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(){
//输出already_arr
for (int i:already_arr ) {
System.out.print(i + " ");
}
System.out.println();
//输出前驱顶点
System.out.println("前驱节点");
for (int i:pre_visited ) {
System.out.print(i + " ");
}
System.out.println();
//输出dis
System.out.println("到出发顶点的最短距离");
for (int i:dis ) {
System.out.print(i + " ");
}
}
}
package com.qin.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};
Graph1 graph = new Graph1(vertex.length, matrix, vertex);
//调用弗洛伊德算法
graph.floyd();
graph.show();
}
}
//创建图
class Graph1 {
private char[] vertex; //存放顶点的数组
private int[][] dis; //保存从各个顶点出发到其他顶点的距离，最后的结果也是保留在该数组
private int[][] pre; //保存到达目标顶点的前驱节点
//length 大小 matrix 邻接矩阵 vertex 顶点数组
public Graph1(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);
}
}
//显示pre数组和dis数组
public void show(){
char[] vertex = {'A','B','C','D','E','F','G'};
System.out.println("打印各个顶点到其他顶点的最短距离");
for (int k = 0; k < dis.length ; k++) {
for (int i = 0; i < dis.length; i++) {
System.out.printf(vertex[pre[k][i]]+" ");
}
System.out.println();
}
System.out.println("打印各个顶点的前驱节点");
for (int k = 0; k < dis.length; k++) {
for (int i = 0; i < dis.length ; i++) {
System.out.print("("+vertex[k]+"到"+vertex[i]+"的最短路径是"+dis[k][i]+")\t");
}
System.out.println();
}
}
//弗洛伊德算法
public void floyd(){
int len = 0; //保存距离
//对中间顶点遍历，k就是中间顶点的下标
for (int k = 0; k < dis.length ; k++) { //['A','B','C','D','E','F','G']
//从i顶点开始出发['A','B','C','D','E','F','G']
for (int i = 0; i < dis.length ; i++) {
//到达j顶点
for (int j = 0; j < dis.length; j++) {
len = dis[i][k] + dis[k][j]; // 求出从i顶点出发经过k中间顶点，到达j顶点
if (len<dis[i][j]){ //如果len小于dis[i][j]
dis[i][j] = len; //更新距离
pre[i][j] = pre[k][j] ; // 更新前驱顶点
}
}
}
}
}
}
package com.qin.Algorithm;
import javax.print.DocFlavor;
import java.awt.*;
import java.util.ArrayList;
//马踏棋盘算法，骑士周游世界算法
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) {
//测试骑士周游算法
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();
traversalChessBoard(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();
}
}
//功能，根据当前的位置，计算马儿还能走哪些位置，并放在一个ArrayList中
public static ArrayList<Point> next(Point curPoint){
//创建一个ArrayList
ArrayList<Point> ps = new ArrayList<>();
//创建一个Point
Point p1 = new Point();
//判断马儿可以走5这个位置
if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0){
ps.add(new Point(p1));
}
//判断马儿是否可以走6这个位置
if ((p1.x = curPoint.x -1) >= 0 && (p1.y = curPoint.y - 2) >= 0){
ps.add(new Point(p1));
}
//判断马儿是否可以走7这个位置
if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0){
ps.add(new Point(p1));
}
//判断马儿是否可以走0这个位置
if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0){
ps.add(new Point(p1));
}
//判断马儿是否可以走1这个位置
if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y){
ps.add(new Point(p1));
}
//判断马儿是否可以2这个位置
if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y){
ps.add(new Point(p1));
}
//判断马儿是否可以走3这个位置
if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y){
ps.add(new Point(p1));
}
//判断马儿是否可以走4这个位置
if ((p1.x = curPoint.x -2 ) >= 0 && (p1.y = curPoint.y + 1) < Y){
ps.add(new Point(p1));
}
return ps;
}
//完成骑士周游世界问题的算法
//chessBoard 棋盘 row 马儿当前的行，从0开始
//column 马儿当前的列，从0开始
//step 是第几步，初始位置就是1
public static void traversalChessBoard(int[][] chessBoard,int row, int column,int step){
chessBoard[row][column] = step;
// row = 4 X = 8 column = 4 ; 4*8+4 = 36
visited[row*X+column] = true; //标记该位置已被访问
//获取当前位置可以走的集合
ArrayList<Point> ps = next(new Point(column, row));
//遍历ps
while (!ps.isEmpty()){
Point p = ps.remove(0); //取出下一个可以走的位置
//判断该点是否已经访问过
if (!visited[p.y*X+p.x]){ //说明还没有访问过
traversalChessBoard(chessBoard,p.y,p.x,step+1);
}
}
//判断马儿是否完成了任务
//说明：step<X*Y成立的情况有两种
//第一种棋盘到目前为止没有走完
//第二种棋盘处于回溯过程
if (step < X*Y && !finished){
chessBoard[row][column] = 0;
visited[row*X+column] = false;
}else {
finished = true;
}
}
}
