JAVA实现根据实时天气地图景点数据-智能推荐旅游景点路线系统源码+项目说明.7z

package com.bs.weather.util.SuanFa.ZhuLiu_TarJan; import com.bs.weather.util.SuanFa.Entity.SetNewMapReturn; import java.util.*; public class ZhuLiu { private final float INF = Float.MAX_VALUE; private float[][] distance; //距离矩阵 private int[] minArray; //每个节点入边最小的数组 private int[][] resultArray; //入边可达性矩阵 private boolean[] ifInStack; //判断是否在栈中 private boolean[] ifVisit; //判断是否访问过 private Stack<Integer> stack; //tarjan栈 private List<ArrayList> allRingList; //环总集合 private int firstPoint; //起点 private int ringCount = 0; //环数 private List<float[][]> allDistanceList;//存储每一层递归的distance方便做展开操作时使用 private List<SetNewMapReturn> allsetNewMapReturnList;//存储每一层递归的SetNewMapReturn方便做展开操作时使用 //tarjan的三个参数 int[] dfn; //时间戳 int[] low; //low一致的为同一环 int index; //索引值 public ZhuLiu(float[][] distance, int firstPoint) { int l = distance.length; this.firstPoint = firstPoint; this.distance = distance; dfn = new int[l]; low = new int[l]; ifInStack = new boolean[l]; ifVisit = new boolean[l]; stack = new Stack<>(); resultArray = new int[l][l]; allRingList = new ArrayList<>(); minArray = new int[l]; allDistanceList = new ArrayList<>(); allsetNewMapReturnList = new ArrayList<>(); init(); } public void init() { //初始化最短入边矩阵值都为-1 for (int i = 0; i < minArray.length; i++) { minArray[i] = -1; } } //朱刘算法 public int[] runZhuLiu() { //最短距离临时变量 float minLengthTmp; //选取每个节点的最小的入边(朱刘第一步) for (int i = 0; i < distance.length; i++) { minLengthTmp = Float.MAX_VALUE; for (int j = 0; j < distance.length; j++) { if (i != j) { if ((minLengthTmp > distance[j][i])) { minLengthTmp = distance[j][i]; //diePointList存储入边信息，例如diePointList.get(0)为1则0节点min入边为 1-0 minArray[i] = j; } else if (minLengthTmp == distance[j][i] && minArray[i] != -1 && minArray[minArray[i]] == i) { //假设A-B与C-B距离一致，此时A-B并且B-A，那么要用C-B替换A-B以免形成环 //diePointList存储入边信息，例如diePointList.get(0)为1则0节点min入边为 1-0 minArray[i] = j; } } } } //将起点设置为没有最短入边，也就是起点不可达 minArray[firstPoint] = -1; //根据minArray，形成新的可达关系矩阵 for (int i = 0; i < minArray.length; i++) { if (minArray[i] != -1) { //当前节点有入边 //将minArray中可达的距离矩阵坐标至为1 resultArray[minArray[i]][i] = 1; } //由于最外层接口做了可达性验证所以不会出现没有入度的节点除了-1 // else if (i != firstPoint) { // //当前节点没有入边&&当前城市不是起点因为起点没有入边 // //需要完善 // System.out.println("产生了不可达节点遍历结果集可找出"); // } } //如果有环进行缩环为点，如果没有返回结果(缩环为点 朱刘第二步) if (ifHaveRing(firstPoint)) { //有环进行缩环为点，形成新图(会再次递归朱刘直到没有环) SetNewMapReturn setNewMapReturn = shrinkagePoint(distance, firstPoint, allRingList, new SetNewMapReturn()); //判断新图是否有环 ZhuLiu zhuliu = new ZhuLiu(setNewMapReturn.getDistanceTmp(), setNewMapReturn.getFirstPointTmp()); int[] newMinArray = zhuliu.runZhuLiu(); // if (newMinArray!=null){} 空指针异常处理但是会少点 return unfoldMap(setNewMapReturn, newMinArray); } else { //无环构造图形 //输出---输出没有环直接构造的图形结果 // System.out.println("无环构造图形"); // for (int i = 0; i < minArray.length; i++) { // if (minArray[i] != -1) { // //起点不可以有入边 // System.out.println(minArray[i] + "---->" + i); // } // } // System.out.println(); //拿到当前传入的distance，此时的distance就是上一层的更新权值后的距离矩阵，根据其及索引关系进行展开 return minArray; } } //判断是否有环(参数为起点)，tarjan public boolean ifHaveRing(int firstPoint) { boolean ifHaveRingMark = true; //遍历入边可达矩阵，判断是否有环 for (int i = 0; i < resultArray.length; i++) { //将没走过的节点传入，并且当前节点不等于出发点 if (!ifVisit[i]) { //还有节点没走到继续遍历 recursionHaveRing(i, firstPoint); } } if (ringCount == 0) { //无环 ifHaveRingMark = false; } // //最短可达距离顺序输出 // System.out.println("--------------"); // for (Integer i : resultRingList) { // System.out.println(i); // } // System.out.println("--------------"); return ifHaveRingMark; } //判断是否有环递归函数 public void recursionHaveRing(int u, int firstPoint) { //u不等于起始点，因为起始点并没有入边，所以起始点不用加入tarjan，resultArray中起始点入边都为-1 if (u != firstPoint) { //给dfn和low赋值 dfn[u] = low[u] = index++; //当前节点入栈 stack.push(u); //标记当前节点在栈中 ifInStack[u] = true; ifVisit[u] = true; //开始遍历其可达节点 for (int i = 0; i < resultArray.length; i++) { //首先保证u-i可以走通 if (resultArray[u][i] == 1) { //u-i可以走通 if (!ifInStack[i]) { //i节点不存在栈中 recursionHaveRing(i, firstPoint); //递归完成进行low的更新，如果low[u]<low[i]证明i节点的后续的节点与u节点前面的节点形成了环，所以他们的low都需要更新为该环中最小的low low[u] = Math.min(low[u], low[i]); } else { //如果当前点在栈中 //更新low，u节点的low如果小于i节点的dfn那么形成环，更新low[u] low[u] = Math.min(low[u], dfn[i]); } } } if (dfn[u] == low[u]) { //是否成环标志 boolean ringMark = false; //环集合 ArrayList<Integer> ringList = new ArrayList<>(); //每个节点只有一个入边所以不需要一个节点访问2次的情况（如果出现直接过滤即可）所以是否访问过的矩阵状态不需要更新 while (stack.size() != 0 && stack.peek() != u) { //如果栈顶元素不等于u则成环 ringMark = true; //将是否在栈状态改�