阿坝州住房和城乡建设厅网站,wordpress 升级后 插件,酷炫网站欣赏,微信公众号制作的网站开发前言
本博客是博主用于复习数据结构以及算法的博客#xff0c;如果疏忽出现错误#xff0c;还望各位指正。
Folyd实现原理
中心点的概念
感觉像是充当一个桥梁的作用 还是这个图
我们常在一些讲解视频中看到#xff0c;就比如dist#xff08;-1#xff09;#xff0…前言
本博客是博主用于复习数据结构以及算法的博客如果疏忽出现错误还望各位指正。
Folyd实现原理
中心点的概念
感觉像是充当一个桥梁的作用 还是这个图
我们常在一些讲解视频中看到就比如dist-1这是原始的邻接矩阵
dist0就是A充当中心点
这时候就是打比方我D-EA作为中心点之后这一轮就是看D-A-E的距离相较之前是否最小所以A-A-B多次一举所以passX-A-A也是多此一举所以pass对角线别动X-A-X又回到自己PASS。一来三个pass差不多如图。我们只需要剩下的就可以。 打比方B-C那么加入A之后就是B-A-CBAAC819相比于之前的6大了所以不换不更新。
B-E那么加入A之后就是B-A-EBAAE8INF直接pass遇到不通的情况。
遍历完B到C继续重复步骤更新……即可脑力有限就不多解释了。
这样我每个点都充当一次中心点下来我的最短路径也出来了。
Folyd实现代码
Folyd的代码形式十分简单如果比赛中看寻找最短路径嫌Dijkstra算法麻烦的话直接试试Folyd看看能不能过不能再说单源的。以下是主要实现代码。
public int[][] Folyd(){int N vertexList.size();int[][] edges new int[N][N];//新开个二维数组防止数据被动//edges[i] this.edges[i]这样是不行的因为java的引用for(int i 0;iN;i){for(int j0;jN;j){edges[i][j] this.edges[i][j];}}//弗洛伊德算法就是要求整个的for(int k 0;kN;k){//中心点for(int i 0;iN;i){//哪个点//if(ik) continue;for(int j 0;jN;j){//到哪个点//if(j k) continue;if(i j) continue;if(edges[i][k] !Integer.MAX_VALUE edges[k][j] ! Integer.MAX_VALUE){edges[i][j] Math.min(edges[i][j], edges[i][k] edges[k][j]);//当前的ij位置}}}}return edges;}
三层循环代码中注释//掉的if就是我原理里面pass的东西。
以下是完整的实现代码以及与迪杰斯特拉算法结果的比对。
//package GraphTest.Demo;import java.util.*;public class Graph{//这是一个图类/***基础属性***/int[][] edges; //邻接矩阵存储边ArrayListEData to new ArrayList(); //EData包含start,end,weight三个属性相当于另一种存储方式主要是为了实现kruskal算法定义的ArrayListString vertexList new ArrayList(); //存储结点名称当然你若想用Integer也可以这个是我自己复习用的int numOfEdges; //边的个数boolean[] isVisited;//构造器Graph(int n){this.edges new int[n][n];//为了方便决定讲结点初始化为INF这也方便后续某些操作int INF Integer.MAX_VALUE;for(int i0;in;i){Arrays.fill(edges[i],INF);}this.numOfEdges 0;this.isVisited new boolean[n];}//插入点public void insertVertex(String vertex){//看自己个人喜好我这边是一个一个在主方法里插入点的名称vertexList.add(vertex);}//点的个数public int getNumOfVertex(){return vertexList.size();}//获取第i个节点的名称public String getVertexByIndex(int i){return vertexList.get(i);}//获取该节点的下标public int getIndexOfVertex(String vertex){return vertexList.indexOf(vertex);}//插入边public void insertEdge(int v1,int v2,int weight){//注意这里是无向图edges[v1][v2] weight;edges[v2][v1] weight;this.numOfEdges;//如果要用Kruskal算法的话这里to.add(new EData(v1,v2,weight)); //加入from to这种存储方式}//边的个数public int getNumOfEdge(){return this.numOfEdges;}//得到点到点的权值public int getWeight(int v1,int v2){//获取v1和v2边的权重return edges[v1][v2];}//打印图public void showGraph(){for(int[] line:edges){System.out.println(Arrays.toString(line));}}//获取index行 第一个邻接结点public int getFirstNeighbor(int index){for(int i 0;i vertexList.size();i){if(edges[index][i] ! Integer.MAX_VALUE){return i; //找到就返回邻接结点的坐标}}return -1; //没找到的话返回-1}//获取row行 column列之后的第一个邻接结点public int getNextNeighbor(int row,int column){for(int i column 1;i vertexList.size();i){if(edges[row][i] ! Integer.MAX_VALUE){return i; //找到就返回邻接结点的坐标}}return -1; //没找到的话返回-1}//DFS实现先定义一个isVisited布尔数组确认该点是否遍历过public void DFS(int index,boolean[] isVisited){System.out.print(getVertexByIndex(index) ); //打印当前结点isVisited[index] true;//查找index的第一个邻接结点fint f getFirstNeighbor(index);//while(f ! -1){//说明有if(!isVisited[f]){//f没被访问过DFS(f,isVisited); //就进入该节点f进行遍历}//如果f已经被访问过,从当前 i 行的 f列 处往后找f getNextNeighbor(index,f);}}//考虑到连通分量需要对所有结点进行一次遍历因为有Visited所以不用考虑冲突情况public void DFS(){for(int i0;ivertexList.size();i){if(!isVisited[i]){DFS(i,isVisited);}}}public void BFS(int index,boolean[] isVisited){//BFS是由队列实现的所以我们先创建一个队列LinkedListInteger queue new LinkedList();System.out.print(getVertexByIndex(index) ); //打印当前结点isVisited[index] true; //遍历标志turequeue.addLast(index); //队尾加入元素int cur,neighbor; //队列头节点cur和邻接结点neighborwhile(!queue.isEmpty()){//如果队列不为空的话就一直进行下去//取出队列头结点下标cur queue.removeFirst(); //可以用作出队//得到第一个邻接结点的下标neighbor getFirstNeighbor(cur);//之后遍历下一个while(neighbor ! -1){//邻接结点存在//是否访问过if(!isVisited[neighbor]){System.out.print(getVertexByIndex(neighbor) );isVisited[neighbor] true;queue.addLast(neighbor);}//在cur行找neighbor列之后的下一个邻接结点neighbor getNextNeighbor(cur,neighbor);}}}//考虑到连通分量需要对所有结点进行一次遍历因为有Visited所以不用考虑冲突情况public void BFS(){for(int i0;ivertexList.size();i){if(!isVisited[i]){BFS(i,isVisited);}}}public void prim(int begin){//Prim原理从当前集合选出权重最小的邻接结点加入集合构成新的集合重复步骤直到N-1条边int N vertexList.size();//当前的集合 与其他邻接结点的最小值int[] lowcost edges[begin];//记录该结点是从哪个邻接结点过来的int[] adjvex new int[N];Arrays.fill(adjvex,begin);//表示已经遍历过了,isVisited置trueisVisited[begin] true;for(int i 0;iN-1;i){//进行N-1次即可因为只需要联通N-1条边//寻找当前集合最小权重邻接结点的操作int index 0;int mincost Integer.MAX_VALUE;for(int j 0;jN;j){if(isVisited[j]) continue;if(lowcost[j] mincost){//寻找当前松弛点mincost lowcost[j];index j;}}System.out.println(选择节点index权重为mincost);isVisited[index] true;System.out.println(index);//加入集合后更新的操作看最小邻接结点是否更改for(int k 0;kN;k){if(isVisited[k]) continue;//如果遍历过就跳过if(edges[index][k] lowcost[k]){ //加入新的节点之后更新,检查原图的index节点加入后是否有更新的lowcost[k] (edges[index][k]);adjvex[k] index;}}}}//用于对之前定义的to进行排序public void toSort(){Collections.sort(this.to, new ComparatorEData() {Overridepublic int compare(EData o1, EData o2) {//顺序对就是升序顺序不对就是降序比如我现在是o1和o2传进来比较时候o1在前就是升序o1在后就是降序int result Integer.compare(o1.weight,o2.weight);return result;}});}//并查集查找public int find(int x,int[] f){while(x!f[x]){x f[x];}return x;}//并查集合并public int union(int x,int y,int[] f){find(x,f);find(y,f);if(x!y){f[x] y;return y;}return -1; //如果一样的集合就返回-1}public ArrayListInteger kruskal(){//kruskal是对form to weight这种结构的类进行排序然后选取最短的一条边看是否形成回路加入toSort(); //调用toSort进行排序//由于要判断是否形成回路我们可以用DFS或者BFS因为之前都写过所以我们在这用并查集//初始化并查集int[] f new int[vertexList.size()];for(int i 0;ivertexList.size();i){f[i] i;}ArrayListInteger res new ArrayList();int count 0;for(int i 0;count ! vertexList.size()-1 ithis.to.size();i){//之后就是开始取边了EData temp this.to.get(i);if(union(temp.start,temp.end,f)!-1){//如果查到不是一个集就可以添加//这里都加进来是方便看哪个边res.add(temp.start);res.add(temp.end);count;}}return res; //最后把集合返回去就行}public int[] Dijkstra(int begin){int N vertexList.size();//到其他点的最短路径动态更新直到最后返回int[] dist new int[N];for(int i0;iN;i){ //进行一下拷贝以免更改核心数据dist[i] edges[begin][i];}//System.out.println(Arrays.toString(dist));isVisited[begin] true; //该点已经遍历过int[] path new int[N]; //记录这个点从哪来的到时候在path里寻找就行//比如path 2 1 1 1 1那么A就是从C来的然后去CC是从B来的B是从B来的OK结束路径出来Arrays.fill(path,begin);for(int i 0;iN;i){//几个点遍历多少次int min Integer.MAX_VALUE;int index 0;for(int j 0;jN;j){//寻找当前的最短路径if(!isVisited[j]){if(dist[j] min){min dist[j];index j;}}}isVisited[index] true; //置为遍历过for(int k 0;kN;k){//新加入点后看minedges[新加点的那一行]看是不是比以前的小小就换了if(!isVisited[k] edges[index][k]!Integer.MAX_VALUE){//此处格外注意因为Integer.MAX_VALUE再就变成负的了所以一定要注意if(dist[index]edges[index][k] dist[k]){dist[k] dist[index]edges[index][k];path[k] index;}}}//找到了之后呢}//System.out.println(Arrays.toString(dist));//System.out.println(Arrays.toString(path));return dist; //返回的是到每个点的最小路径}public int[][] Folyd(){int N vertexList.size();int[][] edges new int[N][N];for(int i 0;iN;i){for(int j 0;jN;j){edges[i][j] this.edges[i][j];}}//弗洛伊德算法就是要求整个的for(int k 0;kN;k){//中心点for(int i 0;iN;i){//哪个点//if(ik) continue;for(int j 0;jN;j){//到哪个点//if(j k) continue;if(i j) continue;if(edges[i][k] !Integer.MAX_VALUE edges[k][j] ! Integer.MAX_VALUE){edges[i][j] Math.min(edges[i][j], edges[i][k] edges[k][j]);//当前的ij位置}}}}return edges;}public static void main(String[] args) {int n 5;String[] Vertexs {A,B,C,D,E};//创建图对象Graph graph new Graph(n);for(String value:Vertexs){graph.insertVertex(value);}graph.insertEdge(0,1,8);graph.insertEdge(0,2,1);graph.insertEdge(1,2,6);graph.insertEdge(1,3,3);graph.insertEdge(1,4,5);graph.insertEdge(3,4,8);
// graph.showGraph();
//
// graph.DFS(1, graph.isVisited);
// System.out.println();
// graph.DFS();//再求求所有的看有没有剩下的
// System.out.println();
// Arrays.fill(graph.isVisited,false);
// graph.BFS(1, graph.isVisited);
// System.out.println();
// Arrays.fill(graph.isVisited,false);
// graph.BFS();
// System.out.println();
// Arrays.fill(graph.isVisited,false);
// graph.prim(2);
// graph.toSort();
// for(EData i : graph.to){
// System.out.println(i.toString());
// }
// System.out.println(graph.kruskal().toString());;
// Arrays.fill(graph.isVisited,false);for(int i 0;igraph.getNumOfVertex();i){//每个点的到其他点的最短路径只需要遍历一遍即可时间复杂度On3Arrays.fill(graph.isVisited,false);System.out.println(Arrays.toString(graph.Dijkstra(i)));;}for(int[] i : graph.Folyd()){System.out.println(Arrays.toString(i));}}
}class EData{//当然这是为了方便直接记录结点下标而不记录像A这种int start;int end;int weight;EData(int start,int end,int weight){this.start start;this.end end;this.weight weight;}Overridepublic String toString() {return EData{ start start , end end , weight weight };}
}
