Dijkstra算法求最短生成路径简介最短路径：在网图中，两顶点之间经历的边上权值之和最少的路径。Dijkstra算法： 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。基本思想：1.初始化数组dist,path和s2.while(s中的元素个数<n)在dist[n]中求最小值，其编号为k；输出dist[k]和path[k]修改数组dist和path将顶点k添加至数组s该有向图如下：求最短生成路径各分量的变化代码实现此处我采用邻接矩阵储存该有向图，为了省时间（其实是自己懒 ），此处省略邻接矩阵的构造过程，采用手动写入边集构建该有向图。MGraph类package Dijkstra; /** * @Author {zbl} * @Date: 2019/12/14/ 13:04 * @Description */ public class MGragh { public static final int INT_MAX= 0x7ffffff; //邻接矩阵，边集 public int[][] arc = { {INT_MAX,10,INT_MAX,30,100}, {INT_MAX,INT_MAX,50,INT_MAX,INT_MAX}, {INT_MAX,INT_MAX,INT_MAX,INT_MAX,10}, {INT_MAX,INT_MAX,20,INT_MAX,60}, {INT_MAX,INT_MAX,INT_MAX,INT_MAX,INT_MAX} }; //顶点数 public int vertexNum = 5; //空构造方法 public MGragh(){} } 主函数：package Dijkstra; import java.nio.file.attribute.DosFileAttributes; import java.util.ArrayList; import java.util.List; /** * @Author {zbl} * @Date: 2019/12/14/ 13:02 * @Description */ public class Main { /** * @Description: 主函数 * @Param: [args] * @return: void * @Author: {zbl} * @Date: 2019/12/14 */ public static void main(String[] args){ MGragh g = new MGragh(); Dijkstra(g,0); } /** * @Description: Dijkstra算法 * @Param: [mGragh, n] * @return: void * @Author: {zbl} * @Date: 2019/12/14 */ public static void Dijkstra(MGragh mGragh,int n){ //加入的顶点集 List<Integer> v = new ArrayList<>(); //路径 String[] path = new String[mGragh.vertexNum]; //边集权值 int[] dist = new int[mGragh.vertexNum]; //初始化dist,path for (int i = 0; i<mGragh.vertexNum; ++i){ dist[i] = mGragh.arc[n][i]; if(dist[i]!=MGragh.INT_MAX) path[i] = "V"+n+"V"+i; else path[i] = ""; } v.add(n); //点集中元素个数少于顶点数 while(v.size()<mGragh.vertexNum){ int k,i; //找到dist中最小的 for (k=0,i = 1; i<mGragh.vertexNum; ++i){ if(dist[i]!=0 && dist[i]<dist[k]) k=i; } //输出dist和path System.out.println(dist[k]+" "+path[k]); v.add(k); //更新dist和path数组 for (i = 0; i<mGragh.vertexNum; ++i){ if(dist[i]>dist[k] + mGragh.arc[k][i]){ dist[i] = dist[k] + mGragh.arc[k][i]; path[i] = path[k] + "V" + i; } } dist[k] = 0; } } } 参考文献王红梅，胡明，王涛编著. 数据结构（C++版）（第二版）[M]. 清华大学出版社.
Kruskal算法求最小生成树简介上一篇博客介绍了用Prim算法求无向图的最小生成树，Prim算法适合用求稠密网的最小生成树，那么当网内的边较少时Prim算法显然就不适用了，于是Kruskal算法便随之诞生了。Kruskal算法是求最小生成树的一种方法，适用于求稀疏网的最小生成树。Kruskal算法的基本思想是：1、初始化：U=V； TE={}；2、重复下述操作直到T中的连通分量个数为1：2.1 在E中寻找最短边（u，v），且满足u∈U，v∈V；2.2 如果顶点u,v位于T的两个不同连通分量，则 2.2.1 将边（u，v）并入TE；2.2.2 将这两个连通分量合为一个；2.3 在E中标记边（u，v）,使得（u，v）不参加后续最短边的选取显然，实现Kruskal算法的关键之处在于：如何叛变被考察边的两个顶点是否位于两个连通分量（即是否与生成树中的 边形成回路）求最小生成树的步骤无向图如下图所示Kruskal算法求最小生成树的步骤：代码实现此处我采用邻接矩阵储存该无向图，边集储存该图中的边，为了省时间（其实是自己懒 ），此处省略邻接矩阵的构造过程，采用手动构建该无向图，通过无向图构建边集。Kruskal算法代码实现： /** * Kruskal算法 * @param G */ public static void Kruskal(EdgeGraph G){ int[] parent = new int[G.vertexNum]; //初始化parent数组 for (int i = 0; i<G.vertexNum;++i){ parent[i] = -1; } for (int num = 0,i = 0; i<G.edgeNum; ++i){ int vex1 = FindRoot(parent,G.edge[i].from); int vex2 = FindRoot(parent,G.edge[i].to); if(vex1 != vex2){ //输出加入的边 System.out.println("(" + G.edge[i].from + "," + G.edge[i].to + "),weight:" + G.edge[i].weight); //合并生成树 parent[vex2] = vex1; ++num; if (num == G.vertexNum-1) return; } } }完整代码无向图存储类EdgeGraphpackage Kruskal; /** * @Author zbl * @Date: 2019/11/23/ 17:33 * @Description */ public class EdgeGraph { int[] vertex = new int[7]; Edge[] edge = new Edge[9]; int vertexNum = 7; int edgeNum = 9; public EdgeGraph(){ //此处省略构造过程 for (int i = 0; i<vertexNum;++i) vertex[i] = i; int[][] arc ={ {0,5,6,0,0,0,0}, {5,0,0,2,0,3,0}, {6,0,0,0,2,0,0}, {0,2,0,0,0,6,3}, {0,0,2,0,0,0,9}, {0,3,0,6,0,0,8}, {0,0,0,3,9,8,0} }; int count = 0; for (int i = 0;i<7; ++i){ for (int j = i; j<7; ++j){ if(arc[i][j]!=0){ edge[count] = new Edge(); edge[count].from = i; edge[count].to = j; edge[count++].weight = arc[i][j]; } } } //记录最后一次交换的位置 int lastExchangeIndex = 0; //无序数列的边界，每次只需比较到这里为止 int sortBorder = edge.length - 1; for (int i = 0;i<edge.length - 1;++i){ boolean flag = true; for (int j = 0;j<sortBorder;++j){ if(edge[j].weight > edge[j+1].weight){ Edge tmp = edge[j]; edge[j] = edge[j+1]; edge[j+1] = tmp; //更新最后一次交换的位置 lastExchangeIndex = j; flag = false; } } //更新边界 sortBorder = lastExchangeIndex; if(flag) break; } } } 储存边的辅助类：package Kruskal; /** * @Author zbl * @Date: 2019/11/23/ 17:34 * @Description */ public class Edge { int from; int to; int weight; } 主要代码：package Kruskal; /** * @Author zbl * @Date: 2019/11/23/ 16:38 * @Description */ public class Main { /** * Kruskal算法 * @param G */ public static void Kruskal(EdgeGraph G){ int[] parent = new int[G.vertexNum]; //初始化parent数组 for (int i = 0; i<G.vertexNum;++i){ parent[i] = -1; } for (int num = 0,i = 0; i<G.edgeNum; ++i){ int vex1 = FindRoot(parent,G.edge[i].from); int vex2 = FindRoot(parent,G.edge[i].to); if(vex1 != vex2){ //输出加入的边 System.out.println("(" + G.edge[i].from + "," + G.edge[i].to + "),weight:" + G.edge[i].weight); //合并生成树 parent[vex2] = vex1; ++num; if (num == G.vertexNum-1) return; } } } public static int FindRoot(int[] parent,int v){ int t = v; //求顶点t的双亲 if(parent[t] > -1) t = parent[t]; return t; } public static void main(String[] args){ Kruskal(new EdgeGraph()); } } 运行结果：复杂度分析Kruskal算法，设连通网中有n个顶点e条边，则第一个进行初始化的循环语句需要执行n次，第二个循环最多执行e次，最少执行n-1次，函数FindRoot的循环语句最多执行log2n次，由于在执行Kruskal算法之前需要对边集数组进行排序，此处采用冒泡排序O(n²)（采用快排需要O(elog2e)），所以，此处Kruskal算法的时间复杂度为O(n²)，但实际可优化为O(elog2e)。参考文献王红梅，胡明，王涛编著. 数据结构（C++版）（第二版）[M]. 清华大学出版社.
Prim算法求最小生成树简介最小生成树： 一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边 （边的代价和最小）Prim算法是求最小生成树的一种方法，由于Prim算法的复杂度与边的数量无关，于是较适用于求稠密网的最小生成树。Prim算法的基本思想是：1、初始化：U={v0}； TE={}；2、重复下述操作直到U=V：2.1 在E中寻找最短边（u，v），且满足u∈U，v∈V；2.2 U=U+{v}；2.3 TE=TE+{ (u，v) }；求最小生成树的步骤无向图如下图所示Prim算法求最小生成树的步骤：代码实现此处我采用邻接矩阵储存该无向图，为了省时间（其实是自己懒 ），此处省略邻接矩阵的构造过程，采用手动写入边集和点集构建该无向图。Prim算法代码实现： /** * Prim算法 * @param G 无向图 * @param shortEdge 辅助边集 */ public static void Prim(MGraph G, ShortEdge[] shortEdge){ //初始化辅助数组 for (int i = 0;i<G.vertexNum;++i){ shortEdge[i].lowcast = G.arc[0][i]; shortEdge[i].adjvex = i; } //将顶点0加入集合U shortEdge[0].lowcast = 0; //建立辅助顶点集合 int[] verctor = new int[G.vertexNum]; verctor[0]++; for (int i = 1;i<G.vertexNum;++i){ //寻找最短边的邻接点k int k = MinEdge(shortEdge,G.vertexNum); //打印 System.out.println("(顶点：" + k + ",边的权值：" + shortEdge[k].lowcast + ")"); //将顶点k加入集合U shortEdge[k].lowcast = 0; verctor[k]++; for (int j = 0;j<G.vertexNum;++j){ //若该点已加入集合U,则跳过该点 if(verctor[j]>0) continue; //更新辅助数组,选取最新的邻接边更新至辅助数组 if ((G.arc[k][j]<shortEdge[j].lowcast || shortEdge[j].lowcast==0 )&& G.arc[k][j]!=0){ shortEdge[j].lowcast = G.arc[k][j]; shortEdge[j].adjvex = j; } } } }完整代码无向图存储类MGraphpackage Prim; /** * @Author zbl * @Date: 2019/11/21/ 10:52 * @Description */ public class MGraph { //边集 public int[][] arc ={ {0,5,6,0,0,0,0}, {5,0,0,2,0,3,0}, {6,0,0,0,2,0,0}, {0,2,0,0,0,6,3}, {0,0,2,0,0,0,9}, {0,3,0,6,0,0,8}, {0,0,0,3,9,8,0} }; //顶点数 public int vertexNum = 7; //空构造函数 public MGraph(){}; } 储存最短边的辅助类：package Prim; /** * @Author zbl * @Date: 2019/11/21/ 11:04 * @Description */ public class ShortEdge { //权值 public int lowcast; //邻接点 public int adjvex; }主要代码：package Prim; /** * @Author zbl * @Date: 2019/11/21/ 10:50 * @Description */ public class Main { //主函数 public static void main(String[] args) { //建立辅助数组 ShortEdge[] shortEdges = new ShortEdge[7]; for(int i = 0;i<7;++i){ shortEdges[i] = new ShortEdge(); } Prim(new MGraph(),shortEdges); } /** * Prim算法 * @param G 无向图 * @param shortEdge 辅助边集 */ public static void Prim(MGraph G, ShortEdge[] shortEdge){ //初始化辅助数组 for (int i = 0;i<G.vertexNum;++i){ shortEdge[i].lowcast = G.arc[0][i]; shortEdge[i].adjvex = i; } //将顶点0加入集合U shortEdge[0].lowcast = 0; //建立辅助顶点集合 int[] verctor = new int[G.vertexNum]; verctor[0]++; for (int i = 1;i<G.vertexNum;++i){ //寻找最短边的邻接点k int k = MinEdge(shortEdge,G.vertexNum); //打印 System.out.println("(顶点：" + k + ",边的权值：" + shortEdge[k].lowcast + ")"); //将顶点k加入集合U shortEdge[k].lowcast = 0; verctor[k]++; for (int j = 0;j<G.vertexNum;++j){ //若该点已加入集合U,则跳过该点 if(verctor[j]>0) continue; //更新辅助数组,选取最新的邻接边更新至辅助数组 if ((G.arc[k][j]<shortEdge[j].lowcast || shortEdge[j].lowcast==0 )&& G.arc[k][j]!=0){ shortEdge[j].lowcast = G.arc[k][j]; shortEdge[j].adjvex = j; } } } } /** * 获取最小邻接点 * @param shortEdges 辅助边集 * @param num 图的顶点数目 * @return 最小邻接点 */ public static int MinEdge(ShortEdge[] shortEdges,int num){ int min = 999999999; int result = 0; //遍历获取与集合U中都点权值最小的邻接点及其该最小边 for (int i = 0;i<num;++i){ if (min > shortEdges[i].lowcast && shortEdges[i].lowcast!=0){ min = shortEdges[i].lowcast; result = shortEdges[i].adjvex; } } return result; } } 运行结果：参考文献王红梅，胡明，王涛编著. 数据结构（C++版）（第二版）[M]. 清华大学出版社.
欢迎移步博主CSDN：CSDN博客无向图的两种遍历算法的实现简介图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为$$ G = (V,E) $$如果图的任意两个顶点之间的边都是无向边，则称该图为无向图,否则称该图为有向图。图的两种遍历算法思想深度优先遍历算法思想 （1）访问顶点v； （2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历； （3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到广度优先遍历算法思想 （1）访问顶点v； （2）依次访问v的各个未被访问的邻接点v1，v2，v3...... （3）分别从v1，v2，v3......出发依次访问它们未被访问的邻接点，并使先被访问顶点的邻接点先于后被访问顶点的邻接点被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。采用邻接矩阵存储图的邻接矩阵存储也称为数组表示法，其方法是用一个以为数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间临界关系的二维数组称为邻接矩阵。以下面这个无向图为例进行实现该无向图的DFS访问顺序：V0->V1->V4->V5->V2->V3该无向图的BFS访问顺序：V0->V1->V2->V3->V4->V5为了省时间（其实是自己懒 ），此处省略邻接矩阵的构造过程，采用手动写入边集和点集构建该无向图。 //手动构造图的点集和边集 //点集 int[] vector = { 0,1,2,3,4,5 }; //边集 int[][] arc ={ {0,1,1,1,1,0}, {1,0,0,0,1,0}, {1,0,0,0,1,0}, {1,0,0,0,0,0}, {1,1,1,0,0,1}, {0,0,0,0,1,1} }; //记录是否访问 int[] visited = { 0,0,0,0,0,0 };深度优先遍历（递归实现） //图的深搜DFS,递归 public static void DFS(int[] vector, int[] visited, int[][] arc,int i){ //访问结点并标记 System.out.println(vector[i]); visited[i]=1; for (int j = 0;j<vector.length; ++j){ if (visited[j]==0 && arc[i][j]==1) DFS(vector,visited,arc,j); } } 深度优先遍历 （非递归实现）//图的深搜DFS ,非递归 public static void DFS(int[] vector, int[] visited, int[][] arc){ //访问第一个顶点并入栈 System.out.println(vector[0]); Stack<Integer> stack = new Stack<Integer>(); stack.push(0); visited[0] = 1; while(!stack.isEmpty()){ //获取栈顶元素 int x = stack.peek(); //标志位 boolean flag = false; for (int i = 0; i<vector.length;++i){ if (visited[i]==0 && arc[x][i]==1){ System.out.println(vector[i]); //入栈 stack.push(i); //更改访问位,标志位 visited[i] = 1; flag = true; break; } } //出栈 if (!flag) stack.pop(); } } 广度优先遍历//图的广搜BFS,非递归 public static void BFS(int[] vector, int[] visited, int[][] arc){ Queue<Integer> queue = new LinkedList<Integer>(); //第一个顶点入队 queue.offer(0); while (!queue.isEmpty()){ //出队 int x = queue.poll(); //访问结点并标记 System.out.println(vector[x]); visited[x] = 1; //寻找连通的结点并入队 for (int i = 0; i<vector.length;++i){ if (visited[i]==0 && arc[x][i]==1){ queue.offer(i); visited[i] = 1; } } } }采用邻接表存储图的邻接表存储是一种顺序存储与链接存储相结合的存储方法，类似于数的孩子链表表示法。对于图的每个顶点v，将所有邻接于v的顶点链成一个单链表，称为顶点v的边表（对于有向图则称为出边表）。顶点类：/** * @Author zbl * @Date: 2019/11/18/ 17:59 * @Description */ //顶点结点 public class VertexNode{ public int vertex; public ArcNode firstEdge; }边表类：/** * @Author zbl * @Date: 2019/11/18/ 17:12 * @Description */ //边结点 public class ArcNode { //邻接点域 public int adjvex; public ArcNode next; public ArcNode(){} public ArcNode(int adjvex,ArcNode arcNode) {this.adjvex=adjvex;this.next=arcNode;} }以下面这个无向图为例进行实现该无向图的DFS访问顺序：V0->V1->V4->V2->V3该无向图的BFS访问顺序：V0->V1->V2->V3->V4为了省时间（其实是自己懒 ），此处省略邻接表的构造过程，采用手动写入边集和点集构建该无向图。 //手动构造图的点集和边集 //手动构造点集和边集 VertexNode[] vertex = new VertexNode[5]; for (int i = 0;i<vertex.length;++i){ vertex[i] = new VertexNode(); vertex[i].vertex=i; } ArcNode V03 = new ArcNode(3,null); ArcNode V02 = new ArcNode(2,V03); ArcNode V01 = new ArcNode(1,V02); ArcNode V12 = new ArcNode(4,null); ArcNode V11 = new ArcNode(0,V12); ArcNode V22 = new ArcNode(3,null); ArcNode V21 = new ArcNode(0,V22); ArcNode V32 = new ArcNode(2,null); ArcNode V31 = new ArcNode(0,V32); ArcNode V41 = new ArcNode(1,null); vertex[0].firstEdge=V01; vertex[1].firstEdge=V11; vertex[2].firstEdge=V21; vertex[3].firstEdge=V31; vertex[4].firstEdge=V41; for(int i = 0; i<visited.length; ++i) visited[i] = 0; 深度优先遍历（递归实现） /** * @Description: 图的深搜DFS，邻接矩阵存储，递归 * @Param: [vertex, visited, i] * @return: void * @Author: zbl * @Date: 2019/11/18 */ public static void DFS(VertexNode[] vertex,int[] visited,int i){ System.out.println(vertex[i].vertex); visited[i]=1; ArcNode tmp = vertex[i].firstEdge; while(tmp != null){ int j = tmp.adjvex; if(visited[j]==0) DFS(vertex,visited,j); tmp = tmp.next; } }深度优先遍历 （非递归实现）/** * @Description: 图的深搜DFS，邻接矩阵存储，非递归 * @Param: [vertex, visited] * @return: void * @Author: zbl * @Date: 2019/11/18 */ public static void DFS(VertexNode[] vertex,int[] visited){ Stack<Integer> stack = new Stack<Integer>(); //访问第一个顶点并入栈 System.out.println(vertex[0].vertex); stack.push(0); visited[0]=1; //栈不为空 while(!stack.isEmpty()){ boolean flag = false; //获取栈顶但不弹栈 int i = stack.peek(); ArcNode tmp = vertex[i].firstEdge; //遍历边表 while(tmp!=null){ if (visited[tmp.adjvex]==0){ //访问并入栈 System.out.println(vertex[tmp.adjvex].vertex); stack.push(tmp.adjvex); //更改访问位,标志位 visited[tmp.adjvex]=1; flag = true; break; } tmp = tmp.next; } //弹栈 if(!flag) stack.pop(); } }广度优先遍历 /** * @Description: 图的广搜BFS，邻接矩阵存储，非递归 * @Param: [vertex, visited] * @return: void * @Author: zbl * @Date: 2019/11/18 */ public static void BFS(VertexNode[] vertex,int[] visited){ for (int i = 0; i<vertex.length; ++i){ ArcNode tmp = vertex[i].firstEdge; //若未访问,则访问并标记 if (visited[i]==0){ System.out.println(vertex[i].vertex); visited[i]=1; } while(tmp!=null){ //若未访问,则访问并标记 if (visited[tmp.adjvex]==0){ System.out.println(vertex[tmp.adjvex].vertex); visited[tmp.adjvex]=1; } tmp = tmp.next; } } }完整函数代码顶点类和边表类在上面已经给出，在此就不重复放出来了。import javafx.scene.shape.Arc; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /** * author zbl * * datetime 2019.11.18 * */ public class Main { //图的深搜DFS ,非递归 public static void DFS(int[] vector, int[] visited, int[][] arc){ //访问第一个顶点并入栈 System.out.println(vector[0]); Stack<Integer> stack = new Stack<Integer>(); stack.push(0); visited[0] = 1; while(!stack.isEmpty()){ //获取栈顶元素 int x = stack.peek(); //标志位 boolean flag = false; for (int i = 0; i<vector.length;++i){ if (visited[i]==0 && arc[x][i]==1){ System.out.println(vector[i]); //入栈 stack.push(i); //更改访问位,标志位 visited[i] = 1; flag = true; break; } } //出栈 if (!flag) stack.pop(); } } //图的深搜DFS,递归 public static void DFS(int[] vector, int[] visited, int[][] arc,int i){ //访问结点并标记 System.out.println(vector[i]); visited[i]=1; for (int j = 0;j<vector.length; ++j){ if (visited[j]==0 && arc[i][j]==1) DFS(vector,visited,arc,j); } } //图的广搜BFS,非递归 public static void BFS(int[] vector, int[] visited, int[][] arc){ Queue<Integer> queue = new LinkedList<Integer>(); //第一个顶点入队 queue.offer(0); while (!queue.isEmpty()){ //出队 int x = queue.poll(); //访问结点并标记 System.out.println(vector[x]); visited[x] = 1; //寻找连通的结点并入队 for (int i = 0; i<vector.length;++i){ if (visited[i]==0 && arc[x][i]==1){ queue.offer(i); visited[i] = 1; } } } } /** * @Description: 图的深搜DFS，邻接矩阵存储，非递归 * @Param: [vertex, visited] * @return: void * @Author: zbl * @Date: 2019/11/18 */ public static void DFS(VertexNode[] vertex,int[] visited){ Stack<Integer> stack = new Stack<Integer>(); //访问第一个顶点并入栈 System.out.println(vertex[0].vertex); stack.push(0); visited[0]=1; //栈不为空 while(!stack.isEmpty()){ boolean flag = false; //获取栈顶但不弹栈 int i = stack.peek(); ArcNode tmp = vertex[i].firstEdge; //遍历边表 while(tmp!=null){ if (visited[tmp.adjvex]==0){ //访问并入栈 System.out.println(vertex[tmp.adjvex].vertex); stack.push(tmp.adjvex); //更改访问位,标志位 visited[tmp.adjvex]=1; flag = true; break; } tmp = tmp.next; } //弹栈 if(!flag) stack.pop(); } } /** * @Description: 图的深搜DFS，邻接矩阵存储，递归 * @Param: [vertex, visited, i] * @return: void * @Author: zbl * @Date: 2019/11/18 */ public static void DFS(VertexNode[] vertex,int[] visited,int i){ System.out.println(vertex[i].vertex); visited[i]=1; ArcNode tmp = vertex[i].firstEdge; while(tmp != null){ int j = tmp.adjvex; if(visited[j]==0) DFS(vertex,visited,j); tmp = tmp.next; } } /** * @Description: 图的广搜BFS，邻接矩阵存储，非递归 * @Param: [vertex, visited] * @return: void * @Author: zbl * @Date: 2019/11/18 */ public static void BFS(VertexNode[] vertex,int[] visited){ for (int i = 0; i<vertex.length; ++i){ ArcNode tmp = vertex[i].firstEdge; //若未访问,则访问并标记 if (visited[i]==0){ System.out.println(vertex[i].vertex); visited[i]=1; } while(tmp!=null){ //若未访问,则访问并标记 if (visited[tmp.adjvex]==0){ System.out.println(vertex[tmp.adjvex].vertex); visited[tmp.adjvex]=1; } tmp = tmp.next; } } } public static void main(String[] args) { //手动构造点集和边集 //点集 int[] vector = { 0,1,2,3,4,5 }; //边集 int[][] arc ={ {0,1,1,1,1,0}, {1,0,0,0,1,0}, {1,0,0,0,1,0}, {1,0,0,0,0,0}, {1,1,1,0,0,1}, {0,0,0,0,1,1} }; //记录是否访问 int[] visited = { 0,0,0,0,0,0 }; System.out.println("===============邻接矩阵Start==============="); System.out.println("Start DFS:"); DFS(vector,visited,arc); System.out.println("End DFS\n"); for(int i = 0; i<visited.length; ++i) visited[i] = 0; System.out.println("Start DFS:"); DFS(vector,visited,arc,0); System.out.println("End DFS\n"); for(int i = 0; i<visited.length; ++i) visited[i] = 0; System.out.println("Start BFS:"); BFS(vector,visited,arc); System.out.println("End BFS"); System.out.println("===============邻接矩阵End===============\n"); System.out.println("===============邻接表Start==============="); //手动构造点集和边集 VertexNode[] vertex = new VertexNode[5]; for (int i = 0;i<vertex.length;++i){ vertex[i] = new VertexNode(); vertex[i].vertex=i; } ArcNode V03 = new ArcNode(3,null); ArcNode V02 = new ArcNode(2,V03); ArcNode V01 = new ArcNode(1,V02); ArcNode V12 = new ArcNode(4,null); ArcNode V11 = new ArcNode(0,V12); ArcNode V22 = new ArcNode(3,null); ArcNode V21 = new ArcNode(0,V22); ArcNode V32 = new ArcNode(2,null); ArcNode V31 = new ArcNode(0,V32); ArcNode V41 = new ArcNode(1,null); vertex[0].firstEdge=V01; vertex[1].firstEdge=V11; vertex[2].firstEdge=V21; vertex[3].firstEdge=V31; vertex[4].firstEdge=V41; for(int i = 0; i<visited.length; ++i) visited[i] = 0; System.out.println("Start DFS:"); DFS(vertex,visited); System.out.println("End DFS\n"); for(int i = 0; i<visited.length; ++i) visited[i] = 0; System.out.println("Start DFS:"); DFS(vertex,visited,0); System.out.println("End DFS\n"); for(int i = 0; i<visited.length; ++i) visited[i] = 0; System.out.println("Start BFS:"); BFS(vertex,visited); System.out.println("End BFS"); System.out.println("===============邻接表End==============="); } } 注意事项以上代码只适用于强连通图！！！以上代码只适用于强连通图！！！以上代码只适用于强连通图！！！重要的事说三遍。参考文献王红梅，胡明，王涛编著. 数据结构（C++版）（第二版）[M]. 清华大学出版社.
欢迎移步博主CSDN：CSDN博客数据结构之排序算法冒泡排序简介冒泡排序，又名起泡排序，顾名思义，就如同气泡从水中不断上浮一样。其算法思想为元素从数列头开始依次往数列尾进行比较，第一遍将最大的元素放置于数列尾的有序区，接着再从数列头的无序区中找到第二大的元素置于数列尾的有序区，如此进行下去，直至数列中所有元素有序。算法复杂度时间复杂度：O(n²)空间复杂度：O(1)代码实现Java代码实现：//冒泡排序 public static void sort(int[] array) { //记录最后一次交换的位置 int lastExchangeIndex = 0; //无序数列的边界，每次只需比较到这里为止 int sortBorder = array.length - 1; for (int i = 0; i < array.length - 1; ++i) { boolean flag = true; for (int j = 0; j < sortBorder; ++j) { if (array[j] > array[j + 1]) { array[j] = array[j] ^ array[j + 1]; array[j + 1] = array[j] ^ array[j + 1]; array[j] = array[j] ^ array[j + 1]; //更新最后一次交换的位置 lastExchangeIndex = j; flag = false; } } //更新边界 sortBorder = lastExchangeIndex; if (flag) break; } }冒泡改进之鸡尾酒排序简介由于冒泡排序每一轮都是从左至右来比较元素，只能单向的进行位置交换，在碰见{2,3,4,5,6,7,8,1}这样的数组时，使用冒泡排序还需进行7轮排序，效率比较低下。而我们当然是不希望这种情况的出现啦，由此鸡尾酒排序算法便诞生了!鸡尾酒排序算法和冒泡排序的不同之处在于遍历算法由单向遍历改为双向遍历，这样能避免出现前端基本有序的数列遍历时效率低下的问题，那么双向遍历究竟是怎样的呢？ 下面将为大家详细说明。鸡尾酒排序第一轮和冒泡排序一样，也是从左至右比较元素，而到了第二轮时，则反过来从右至左开始比较元素，这样往复，直至数列全部有序。鸡尾酒排序的过程就像钟摆一样，第一轮从左至右，第二轮从右往左，第三轮再从左至右······像{2,3,4,5,6,7,8,1}这样的数列，使用鸡尾酒排序只用3轮遍历就已经解决了！复杂度时间复杂度：O(n²)空间复杂度：O(1)代码实现Java代码实现//鸡尾酒排序 public static void jwSort(int[] array) { for (int i = 0; i < array.length / 2; ++i) { boolean flag = true; //奇数轮，从左往右 for (int j = i; j < array.length - 1; ++j) { if (array[j] > array[j + 1]) { array[j] = array[j] ^ array[j + 1]; array[j + 1] = array[j] ^ array[j + 1]; array[j] = array[j] ^ array[j + 1]; flag = false; } } if (flag) break; //重置标记 flag = true; //偶数轮，从右往左 for (int j = array.length - 1; j > i; --j) { if (array[j] < array[j - 1]) { array[j] = array[j] ^ array[j - 1]; array[j - 1] = array[j] ^ array[j - 1]; array[j] = array[j] ^ array[j - 1]; flag = false; } } if (flag) break; } }补充说明鸡尾酒排序的优点是能够在特定的条件下，减少排序的回合数；而缺点也很明显，就是代码量几乎增加了1倍。至于它能发挥出优势的场景，是大部分元素已经有序的情况。快速排序上面介绍的算法时间复杂度都为O(n²),那么有没有比它们更快的算法呢？现在我们介绍一种时间复杂度为O(nlogn)的算法---快速排序简介快速排序之所以快，是因为它使用了分治法，将大问题划分为小问题，分而治之。快速排序和冒泡排序一样，也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。不同的是，冒泡排序在每一轮中只把一个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其他比它打的元素移动到数列的一边，比它小的元素移动到数列的另一边，从而吧数列拆解成两个部分，如此拆分下去，不断将复杂问题简单化，这种思路就叫做分治法。复杂度时间复杂度：O(nlogn)空间复杂度：O(logn)代码实现1.双边循环法//快排辅助函数 双边循环 public static int partition(int[] array, int startIndex, int lastIndex) { //取第一个元素为基准元素 int pivot = array[startIndex]; int left = startIndex; int right = lastIndex; while (left != right) { //控制right指针比较并左移 while (left < right && array[right] > pivot) { --right; } //控制left指针比较并右移 while (left < right && array[left] <= pivot) { ++left; } //交换left和right指针所指向元素 if (left < right) { array[left] = array[left] ^ array[right]; array[right] = array[left] ^ array[right]; array[left] = array[left] ^ array[right]; } } //pivot和指针重合点交换 array[startIndex] = array[left]; array[left] = pivot; return left; }2.单边循环法//快排辅助函数 单边循环 public static int singlePartition(int[] array, int startIndex, int lastIndex){ //取第一个元素为基准元素 int pivot = array[startIndex]; int mark = startIndex; for (int i = startIndex + 1;i<=lastIndex;++i){ if (array[i] < pivot){ mark++; int p = array[mark]; array[mark] = array[i]; array[i] = p; //请勿用下列方式进行两值得交换，此处会发生i==mark ,使得异或值变为零 // array[mark] = array[i]^array[mark]; // array[i] = array[i]^array[mark]; // array[mark] = array[i]^array[mark]; } } array[startIndex] = array[mark]; array[mark] = pivot; return mark; }快排递归实现//快排 public static void quickSort(int[] array, int startIndex, int lastIndex) { //递归结束条件 if (startIndex >= lastIndex) return; //得到基准元素 int pivotIndex = singlePartition(array, startIndex, lastIndex); //根据基准元素,分成2部分进行排序 quickSort(array, startIndex, pivotIndex - 1); quickSort(array, pivotIndex + 1, lastIndex); }快排非递归实现//快排非递归实现 public static void NoQuickSort(int[] array, int startIndex, int lastIndex){ //用栈实现非递归快排 Stack<Map<String,Integer>> quickSortStack = new Stack<Map<String, Integer>>(); //整个数列的起止下标入栈 Map rootParam = new HashMap(); rootParam.put("startIndex",startIndex); rootParam.put("endIndex",lastIndex); quickSortStack.push(rootParam); //栈非空 while(!quickSortStack.isEmpty()){ //栈顶元素出栈 Map<String,Integer> param = quickSortStack.pop(); //得到基准元素位置 int pivotIndex = singlePartition(array,param.get("startIndex"),param.get("endIndex")); //根据基准元素将数列分成2部分 if(param.get("startIndex") < pivotIndex - 1){ Map<String,Integer> leftParam = new HashMap<String,Integer>(); leftParam.put("startIndex",param.get("startIndex")); leftParam.put("endIndex",pivotIndex - 1); quickSortStack.push(leftParam); } if(pivotIndex + 1 < param.get("endIndex")){ Map<String,Integer> rightParam = new HashMap<String,Integer>(); rightParam.put("startIndex",pivotIndex + 1); rightParam.put("endIndex",param.get("endIndex")); quickSortStack.push(rightParam); } } }堆排序简介堆排序是基于二叉堆实现的。二叉堆的特性1.最大堆的堆顶是整个堆中的最大元素2.最小堆的堆顶是整个堆中的最小元素堆排序就是不断去构建最大堆/最小堆去实现的实现步骤：1.把无序数列构建成二叉堆。2.循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶复杂度时间复杂度：O(nlogn)空间复杂度：O(1)代码实现//堆排序 升序 public static void heapSort(int[] array){ //把无序数组构建成大顶堆 for (int i = (array.length - 2) / 2;i>=0;--i){ downAdjust(array,i,array.length); } //输出构建好的大顶堆 // System.out.println(Arrays.toString(array)); //循环删除堆顶元素,调整堆产生新的堆顶 for (int i = array.length - 1;i>0;--i){ //最后一个元素和第一个元素交换 array[i] = array[0]^array[i]; array[0] = array[0]^array[i]; array[i] = array[0]^array[i]; //执行下沉操作 downAdjust(array,0,i); } } //堆排辅助函数,下沉操作 public static void downAdjust(int[] array, int parentIndex, int length){ //temp保存根结点信息 int temp = array[parentIndex]; int childIndex = parentIndex * 2 + 1; //大顶堆 while (childIndex < length){ //如果有右孩子,且右孩子大于左孩子的值，则定位到右孩子 if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]){ childIndex++; } //如果父节点大于任何一个孩子的值,则直接跳出 if (temp >= array[childIndex]) break; //无需赋值,单向交换 array[parentIndex] = array[childIndex]; parentIndex = childIndex; childIndex = parentIndex * 2 + 1; } //最后赋值 array[parentIndex] = temp; }计数排序简介计数排序是一种线性时间复杂度的算法。采用了空间换时间的方式来实现排序！复杂度时间复杂度：O(n+m)空间复杂度：O(m)代码实现//计数排序 public static int[] countSort(int[] array){ int max = array[0]; int min = array[0]; //得出数组最大值与最小值 for (int i = 1; i<array.length;++i){ if (array[i]>max){ max = array[i]; } if (array[i]<min) { min = array[i]; } } //创建数组 int[] countArray = new int[max - min + 1]; //计数 for (int i = 0; i<array.length;++i ){ countArray[array[i]-min]++; } //统计数组做变形,后面的元素等于前面的元素相加 for (int i = 1; i<countArray.length;++i){ countArray[i] += countArray[i - 1]; } //倒序遍历原始数组,从统计数组中找到正确的位置,输出到结果数组 int[] sortedArray = new int[array.length]; for (int i = array.length - 1; i>=0;--i){ sortedArray[countArray[array[i]-min]-1] = array[i]; countArray[array[i]-min]--; } return sortedArray; }补充说明1.当数列最大和最小值差距过大时，空间开销太大，不适合用计数排序2.当数列元素不是整数时，也不适合用计数排序桶排序简介桶排序的出现就是为了解决计数排序不适用的2种情景。桶排序同样也是一种线性时间的排序算法。类似于计数排序所创建的统计数组，桶排序需要创建若干个桶来协助排序复杂度时间复杂度：O(n)空间复杂度：O(n)代码实现//桶排序 public static double[] bucketSort(double[] array){ double max = array[0]; double min = array[0]; //得到最大值与最小值 for (int i = 1;i<array.length; ++i){ if (array[i]>max) max = array[i]; if(array[i]<min) min = array[i]; } //创建桶 int bucketNum = array.length; ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum); for (int i = 0; i<array.length;++i){ bucketList.add(new LinkedList<Double>()); } //遍历原始数组,将每个元素放入桶 for (int i = 0; i<array.length; ++i){ int num = (int)((array[i] - min) * (bucketNum - 1) / (max - min)); bucketList.get(num).add(array[i]); } //对每个桶内部进行排序 for (int i = 0; i<bucketList.size();++i){ //调用Collections内部排序函数 Collections.sort(bucketList.get(i)); } //建立排好序的数组并返回 double[] sortedArrray = new double[array.length]; int index = 0; for (LinkedList<Double> list : bucketList){ for(double element:list){ sortedArrray[index++] = element; } } return sortedArrray; }完整代码package com.dataStructure; import java.lang.reflect.Array; import java.util.*; /** * author zbl * * datetime 2019.11.9 * */ public class Main { //冒泡排序 public static void sort(int[] array) { //记录最后一次交换的位置 int lastExchangeIndex = 0; //无序数列的边界，每次只需比较到这里为止 int sortBorder = array.length - 1; for (int i = 0; i < array.length - 1; ++i) { boolean flag = true; for (int j = 0; j < sortBorder; ++j) { if (array[j] > array[j + 1]) { array[j] = array[j] ^ array[j + 1]; array[j + 1] = array[j] ^ array[j + 1]; array[j] = array[j] ^ array[j + 1]; //更新最后一次交换的位置 lastExchangeIndex = j; flag = false; } } //更新边界 sortBorder = lastExchangeIndex; if (flag) break; } } //鸡尾酒排序 public static void jwSort(int[] array) { for (int i = 0; i < array.length / 2; ++i) { boolean flag = true; //奇数轮，从左往右 for (int j = i; j < array.length - 1; ++j) { if (array[j] > array[j + 1]) { array[j] = array[j] ^ array[j + 1]; array[j + 1] = array[j] ^ array[j + 1]; array[j] = array[j] ^ array[j + 1]; flag = false; } } if (flag) break; //重置标记 flag = true; //偶数轮，从右往左 for (int j = array.length - 1; j > i; --j) { if (array[j] < array[j - 1]) { array[j] = array[j] ^ array[j - 1]; array[j - 1] = array[j] ^ array[j - 1]; array[j] = array[j] ^ array[j - 1]; flag = false; } } if (flag) break; } } //快排 public static void quickSort(int[] array, int startIndex, int lastIndex) { //递归结束条件 if (startIndex >= lastIndex) return; //得到基准元素 int pivotIndex = singlePartition(array, startIndex, lastIndex); //根据基准元素,分成2部分进行排序 quickSort(array, startIndex, pivotIndex - 1); quickSort(array, pivotIndex + 1, lastIndex); } //快排辅助函数 双边循环 public static int partition(int[] array, int startIndex, int lastIndex) { //取第一个元素为基准元素 int pivot = array[startIndex]; int left = startIndex; int right = lastIndex; while (left != right) { //控制right指针比较并左移 while (left < right && array[right] > pivot) { --right; } //控制left指针比较并右移 while (left < right && array[left] <= pivot) { ++left; } //交换left和right指针所指向元素 if (left < right) { array[left] = array[left] ^ array[right]; array[right] = array[left] ^ array[right]; array[left] = array[left] ^ array[right]; } } //pivot和指针重合点交换 array[startIndex] = array[left]; array[left] = pivot; return left; } //快排非递归实现 public static void NoQuickSort(int[] array, int startIndex, int lastIndex){ //用栈实现非递归快排 Stack<Map<String,Integer>> quickSortStack = new Stack<Map<String, Integer>>(); //整个数列的起止下标入栈 Map rootParam = new HashMap(); rootParam.put("startIndex",startIndex); rootParam.put("endIndex",lastIndex); quickSortStack.push(rootParam); //栈非空 while(!quickSortStack.isEmpty()){ //栈顶元素出栈 Map<String,Integer> param = quickSortStack.pop(); //得到基准元素位置 int pivotIndex = singlePartition(array,param.get("startIndex"),param.get("endIndex")); //根据基准元素将数列分成2部分 if(param.get("startIndex") < pivotIndex - 1){ Map<String,Integer> leftParam = new HashMap<String,Integer>(); leftParam.put("startIndex",param.get("startIndex")); leftParam.put("endIndex",pivotIndex - 1); quickSortStack.push(leftParam); } if(pivotIndex + 1 < param.get("endIndex")){ Map<String,Integer> rightParam = new HashMap<String,Integer>(); rightParam.put("startIndex",pivotIndex + 1); rightParam.put("endIndex",param.get("endIndex")); quickSortStack.push(rightParam); } } } //快排辅助函数 单边循环 public static int singlePartition(int[] array, int startIndex, int lastIndex){ //取第一个元素为基准元素 int pivot = array[startIndex]; int mark = startIndex; for (int i = startIndex + 1;i<=lastIndex;++i){ if (array[i] < pivot){ mark++; int p = array[mark]; array[mark] = array[i]; array[i] = p; //请勿用下列方式进行两值得交换，此处会发生i==mark ,使得异或值变为零 // array[mark] = array[i]^array[mark]; // array[i] = array[i]^array[mark]; // array[mark] = array[i]^array[mark]; } } array[startIndex] = array[mark]; array[mark] = pivot; return mark; } //堆排序 升序 public static void heapSort(int[] array){ //把无序数组构建成大顶堆 for (int i = (array.length - 2) / 2;i>=0;--i){ downAdjust(array,i,array.length); } //输出构建好的大顶堆 // System.out.println(Arrays.toString(array)); //循环删除堆顶元素,调整堆产生新的堆顶 for (int i = array.length - 1;i>0;--i){ //最后一个元素和第一个元素交换 array[i] = array[0]^array[i]; array[0] = array[0]^array[i]; array[i] = array[0]^array[i]; //执行下沉操作 downAdjust(array,0,i); } } //堆排辅助函数,下沉操作 public static void downAdjust(int[] array, int parentIndex, int length){ //temp保存根结点信息 int temp = array[parentIndex]; int childIndex = parentIndex * 2 + 1; //大顶堆 while (childIndex < length){ //如果有右孩子,且右孩子大于左孩子的值，则定位到右孩子 if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]){ childIndex++; } //如果父节点大于任何一个孩子的值,则直接跳出 if (temp >= array[childIndex]) break; //无需赋值,单向交换 array[parentIndex] = array[childIndex]; parentIndex = childIndex; childIndex = parentIndex * 2 + 1; } //最后赋值 array[parentIndex] = temp; } //计数排序 public static int[] countSort(int[] array){ int max = array[0]; int min = array[0]; //得出数组最大值与最小值 for (int i = 1; i<array.length;++i){ if (array[i]>max){ max = array[i]; } if (array[i]<min) { min = array[i]; } } //创建数组 int[] countArray = new int[max - min + 1]; //计数 for (int i = 0; i<array.length;++i ){ countArray[array[i]-min]++; } //统计数组做变形,后面的元素等于前面的元素相加 for (int i = 1; i<countArray.length;++i){ countArray[i] += countArray[i - 1]; } //倒序遍历原始数组,从统计数组中找到正确的位置,输出到结果数组 int[] sortedArray = new int[array.length]; for (int i = array.length - 1; i>=0;--i){ sortedArray[countArray[array[i]-min]-1] = array[i]; countArray[array[i]-min]--; } return sortedArray; } //桶排序 public static double[] bucketSort(double[] array){ double max = array[0]; double min = array[0]; //得到最大值与最小值 for (int i = 1;i<array.length; ++i){ if (array[i]>max) max = array[i]; if(array[i]<min) min = array[i]; } //创建桶 int bucketNum = array.length; ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum); for (int i = 0; i<array.length;++i){ bucketList.add(new LinkedList<Double>()); } //遍历原始数组,将每个元素放入桶 for (int i = 0; i<array.length; ++i){ int num = (int)((array[i] - min) * (bucketNum - 1) / (max - min)); bucketList.get(num).add(array[i]); } //对每个桶内部进行排序 for (int i = 0; i<bucketList.size();++i){ //调用Collections内部排序函数 Collections.sort(bucketList.get(i)); } //建立排好序的数组并返回 double[] sortedArrray = new double[array.length]; int index = 0; for (LinkedList<Double> list : bucketList){ for(double element:list){ sortedArrray[index++] = element; } } return sortedArrray; } public static void main(String[] args) { // write your code here double[] array = new double[]{2.22,1.2,3.2,4.9,5.3,7.8}; array = bucketSort(array); System.out.println("桶排序：\n" + Arrays.toString(array)); int[] arr1 = new int[] {2,3,1,9,5,3,4}; arr1 = countSort(arr1); System.out.println("计数排序：\n" + Arrays.toString(arr1)); arr1 = new int[] {2,3,1,9,5,3,4}; heapSort(arr1); System.out.println("堆排序：\n" + Arrays.toString(arr1)); arr1 = new int[] {2,3,1,9,5,3,4}; NoQuickSort(arr1,0,arr1.length - 1); System.out.println("非递归快排：\n" + Arrays.toString(arr1)); arr1 = new int[] {2,3,1,9,5,3,4}; quickSort(arr1,0,arr1.length - 1); System.out.println("快排：\n" + Arrays.toString(arr1)); arr1 = new int[] {2,3,1,9,5,3,4}; jwSort(arr1); System.out.println("鸡尾酒排序：\n" + Arrays.toString(arr1)); arr1 = new int[] {2,3,1,9,5,3,4}; sort(arr1); System.out.println("冒泡排序：\n" + Arrays.toString(arr1)); } }各排序算法复杂度总结参考文献王红梅，胡明，王涛编著. 数据结构（C++版）（第二版）[M]. 清华大学出版社.魏梦舒(@程序员小灰)著. 漫画算法—小灰的算法之旅 [M]. 电子工业出版社.版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
欢迎移步博主CSDN：CSDN博客数据结构之二叉堆与优先队列的学习简介二叉堆本质上是一种完全二叉树，采用顺序结构进行存储，它分为两种类型最大堆最小堆最大堆的任何一个节点都大于或等于它的左右孩子节点最小堆的任何一个节点都小于或等于它的孩子节点二叉堆的用途与基本操作的实现二叉堆是实现堆排序和优先队列的基础。下面我们将用代码实现最小堆的上浮，下沉操作完整java代码二叉堆Heap类基本操作代码实现：package com.dataStructure.Heap; import java.lang.reflect.Array; import java.util.Arrays; /** * author zbl * * datetime 2019.11.4 * */ //二叉堆 public class Heap { //采用数组存储二叉堆 private int [] array; @Override public String toString() { return "Heap{" + "array=" + Arrays.toString(array) + '}'; } //构造函数 public Heap(int [] array , int length){ this.array = Arrays.copyOf(array,length); } //上浮调整 public void upAdjust(){ int childIndex = array.length - 1; int parentIndex = (childIndex - 1) / 2; //暂存最后一个节点数据 int tmp = array[childIndex]; //小顶堆 while(childIndex > 0 && tmp<array[parentIndex]){ array[childIndex] = array[parentIndex]; childIndex = parentIndex; parentIndex = (childIndex - 1) / 2; } array[childIndex] = tmp; } //下沉调整 public void downAdjust(int parentIndex){ int childIndex = parentIndex * 2 + 1; int tmp = array[parentIndex]; while(childIndex < array.length - 1){ //如果有右孩子，且右孩子小于左孩子，则定位到右孩子 if(childIndex + 1 < array.length && array[childIndex + 1] < array[childIndex]) childIndex++; //如果父节点最小，跳出 if(tmp <= array[childIndex]) break; //父节点下沉 array[parentIndex] = array[childIndex]; parentIndex = childIndex; childIndex = parentIndex * 2 + 1; } array[childIndex] = tmp; } } 主函数： package com.dataStructure; import com.dataStructure.Heap.Heap; /** * author zbl * * datetime 2019.11.4 * */ public class Main { public static void main(String[] args) { int[] array = new int[]{8,7,6,5,4,3,2,1}; Heap heap = new Heap(array,8); heap.upAdjust(); System.out.println(heap.toString()); } } 优先队列的实现最大优先队列,无论入队顺序如何,都是当前优先级最大的元素优先出队最小优先队列,无论入队顺序如何,都是当前优先级最小的元素优先出队下面是最小优先队列的实现代码二叉堆Heap类基本操作代码实现：package com.dataStructure.Heap; import java.lang.reflect.Array; import java.util.Arrays; /** * author zbl * * datetime 2019.11.5 * */ //二叉堆 public class Heap { //采用数组存储二叉堆 protected int [] array; //队列实际长度 protected int size; public int[] getArray() { return array; } public void setArray(int[] array) { this.array = array; } @Override public String toString() { return "Heap{" + "array=" + Arrays.toString(this.array) + '}'; } //空构造函数 public Heap(){} //构造函数 public Heap(int [] array){ this.array = Arrays.copyOf(array,array.length); } //上浮调整 public void upAdjust(){ int childIndex = this.size - 1; int parentIndex = (childIndex - 1) / 2; //暂存最后一个节点数据 int tmp = this.array[childIndex]; //小顶堆 while(childIndex > 0 && tmp<this.array[parentIndex]){ this.array[childIndex] = this.array[parentIndex]; childIndex = parentIndex; parentIndex = (childIndex - 1) / 2; } this.array[childIndex] = tmp; } //下沉调整 public void downAdjust(int parentIndex){ int childIndex = parentIndex * 2 + 1; int tmp = this.array[parentIndex]; while(childIndex < this.size - 1){ //如果有右孩子，且右孩子小于左孩子，则定位到右孩子 if(childIndex + 1 < this.size && this.array[childIndex + 1] < this.array[childIndex]) childIndex++; //如果父节点最小，跳出 if(tmp <= this.array[childIndex]) break; //父节点下沉 this.array[parentIndex] = this.array[childIndex]; parentIndex = childIndex; childIndex = parentIndex * 2 + 1; } this.array[childIndex] = tmp; } } 最小优先队列PriorityQueue 类的实现：package com.dataStructure.Heap; import java.util.Arrays; /** * author zbl * * datetime 2019.11.5 * */ public class PriorityQueue extends Heap { public PriorityQueue(){ this.array = new int[32]; } //下沉调整 构建缺省值 public void downAdjust(){ super.downAdjust(0); } //出队 public int deQueue() throws Exception{ //队列为空 if(this.size<0) throw new Exception("队列为空"); //获取堆顶元素 int x = this.array[0] ; this.array[0] = this.array[--this.size]; downAdjust(); return x; } //入队 public void enQueue(int key){ //长度超出范围 if(this.size >= this.array.length){ resize(); } this.array[this.size++] = key; upAdjust(); } //扩容 public void resize(){ //容量翻倍 int newSize = this.size * 2; this.array = Arrays.copyOf(this.array,newSize); } } 主函数:package com.dataStructure; import com.dataStructure.Heap.Heap; import com.dataStructure.Heap.PriorityQueue; /** * author zbl * * datetime 2019.11.5 * */ public class Main { public static void main(String[] args) throws Exception{ PriorityQueue priorityQueue = new PriorityQueue(); priorityQueue.enQueue(3); System.out.println(priorityQueue.toString()); priorityQueue.enQueue(5); System.out.println(priorityQueue.toString()); priorityQueue.enQueue(10); System.out.println(priorityQueue.toString()); priorityQueue.enQueue(2); System.out.println(priorityQueue.toString()); priorityQueue.enQueue(7); System.out.println(priorityQueue.toString()); System.out.println(priorityQueue.deQueue()); System.out.println(priorityQueue.deQueue()); } } 参考文献魏梦舒(@程序员小灰)著. 漫画算法--小灰的算法之旅 [M]. 电子工业出版社.
欢迎移步博主CSDN：CSDN博客数据结构之树与二叉树的学习（一）简介本文主要对数据结构中的树与二叉树进行学习，之前我们学习了数据的线性结构(线性表),但数据之间不只有这种简单的一对一关系，更多时候是一对多，甚至多对多的结构，而树结构作为一种比线性结构更复杂的数据结构，比较适合于描述具有层次关系的数据，即数据间的一对多关系。树定义树中常常将数据元素称之为结点，树是n个结点的集合。当n=0时，称为空树；任意一颗非空树都满足一下几个条件:有且仅有一个特定的称为根的结点当n>1时，除根结点之外的其余结点被分为m个互不相交的有限集合，其中每一个集合又是一棵树基本术语结点的度与树的度叶子结点与分支结点孩子结点、双亲结点、兄弟结点路径、路径长度祖先、子孙结点的层数、树的深度(高度)层序编号有序树、无序树森林二叉树定义二叉树是n个结点的有限集合，该集合或者为空集，或者由一个根结点和2棵互不相交的、分别称为根节点的左子树和柚子乎上的二叉树构成。二叉树的特点每个结点最多有2棵子树二叉树是有序的，次序不能颠倒基本术语斜树满二叉树完全二叉树二叉树的遍历简介二叉树的存储可以采用顺序存储和连接存储两种方式，相应的代码实现也有些许区别，不过其思想都是一致的，下面我们针对链接存储结构来实现二叉树的几种遍历方式。二叉树的构造及其基本操作：package com.dataStructure; /** * author zbl * * datetime 2019.11.266666 * */ //结点类 public class TreeNode<T> { //指向下一个结点 public TreeNode leftChild; public TreeNode rightChild; public T data; TreeNode(T data){ this.data = data; } } 构架二叉树函数代码实现：此处采用迭代左子树实现，创建的是一棵左斜树//创建二叉树 private TreeNode creatBiTree(LinkedList<T> inputList){ TreeNode<T> tmp = null; //判空 if(inputList == null || inputList.isEmpty()){ return null; } //存数 T data = inputList.removeFirst(); if(data != null){ tmp = new TreeNode(data); tmp.leftChild = this.creatBiTree(inputList); tmp.rightChild = this.creatBiTree(inputList); } //返回根结点 return tmp; }前序遍历输出顺序：根节点、左子树、右子树递归代码实现：//前序遍历 递归实现 private void preOrder(TreeNode<T> node){ if (node != null){ System.out.println(node.data); preOrder(node.leftChild); preOrder(node.rightChild); } }非递归代码实现：//前序遍历 非递归 private void preOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; while(tmp != null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 while(tmp != null){ System.out.println(tmp.data); stack.push(tmp); tmp = tmp.leftChild; } //如果节点没有左孩子，则弹出栈顶，访问节点右孩子 if(!stack.isEmpty()){ tmp = stack.pop(); tmp = tmp.rightChild; } } } 中序遍历输出顺序：左子树、根节点、右子树递归代码实现：//中序遍历 递归实现 private void inOrder(TreeNode<T> node){ if (node != null){ inOrder(node.leftChild); System.out.println(node.data); inOrder(node.rightChild); } }非递归代码实现：//中序遍历 非递归 private void inOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; //当节点不为空，且栈不为空 while(tmp != null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 while(tmp != null){ stack.push(tmp); tmp = tmp.leftChild; } //访问叶子节点 System.out.println(tmp.data); //栈非空，说明还未遍历完 if(!stack.isEmpty()){ //父节点出栈 tmp = stack.pop(); //访问父节点 System.out.println(tmp.data); //访问右子树 tmp = tmp.rightChild; } } }后序遍历输出顺序：左子树、右子树、根节点递归代码实现：//后序遍历 递归实现 private void postOrder(TreeNode<T> node){ if (node != null){ postOrder(node.leftChild); postOrder(node.rightChild); System.out.println(node.data); } }非递归代码实现：//后序遍历 非递归 private void postOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; while(tmp != null || !stack.isEmpty()){ while(tmp != null){ stack.push(tmp); tmp = tmp.leftChild; } if(!stack.isEmpty()){ tmp = stack.pop(); //若为叶子节点，访问 if(tmp.rightChild == null) System.out.println(tmp.data); tmp = tmp.rightChild; } } }层序遍历按照从根节点到叶子节点的层次关系进行遍历，属于广度优先遍历。非递归代码实现：//层序遍历 非递归实现 public void LerverOrder(){ Queue<TreeNode> queue = new LinkedList<TreeNode>(); //根节点入队 queue.offer(node); System.out.println("层序遍历开始"); while(!queue.isEmpty()){ TreeNode<T> tmp = queue.poll(); System.out.println(tmp.data); if(tmp.leftChild != null) queue.offer(tmp.leftChild); if(tmp.rightChild != null) queue.offer(tmp.rightChild); } System.out.println("层序遍历结束"); }完整Java代码BiTreeOrder遍历接口：package com.dataStructure; public interface BiTreeOrder { //前序遍历 public void PreOrder(); //中序遍历 public void InOrder(); //后序遍历 public void PostOrder(); //层序遍历 public void LerverOrder(); }ReBiTree递归实现类：package com.dataStructure; import sun.reflect.generics.tree.Tree; import java.util.LinkedList; import java.util.Queue; /** * author zbl * * datetime 2019.11.266666 * */ public class ReBiTree<T> implements BiTreeOrder{ //存根结点 protected TreeNode<T> node = null; //构造函数 public ReBiTree(LinkedList<T> inputList){ this.node = this.creatBiTree(inputList); } //空构造函数 public ReBiTree() { } // public void addBiTree() //创建二叉树 private TreeNode creatBiTree(LinkedList<T> inputList){ TreeNode<T> tmp = null; //判空 if(inputList == null || inputList.isEmpty()){ return null; } //存数 T data = inputList.removeFirst(); if(data != null){ tmp = new TreeNode(data); tmp.leftChild = this.creatBiTree(inputList); tmp.rightChild = this.creatBiTree(inputList); } //返回根结点 return tmp; } //前序遍历 public void PreOrder(){ System.out.println("前序遍历开始："); preOrder(this.node); System.out.println("前序遍历结束："); } //前序遍历 递归实现 private void preOrder(TreeNode<T> node){ if (node != null){ System.out.println(node.data); preOrder(node.leftChild); preOrder(node.rightChild); } } //中序遍历 public void InOrder(){ System.out.println("中序遍历开始："); inOrder(this.node); System.out.println("中序遍历结束："); } //中序遍历 递归实现 private void inOrder(TreeNode<T> node){ if (node != null){ inOrder(node.leftChild); System.out.println(node.data); inOrder(node.rightChild); } } //后序遍历 public void PostOrder(){ System.out.println("后序遍历开始："); postOrder(this.node); System.out.println("后序遍历结束："); } //后序遍历 递归实现 private void postOrder(TreeNode<T> node){ if (node != null){ postOrder(node.leftChild); postOrder(node.rightChild); System.out.println(node.data); } } //层序遍历 非递归实现 public void LerverOrder(){ Queue<TreeNode> queue = new LinkedList<TreeNode>(); //根节点入队 queue.offer(node); System.out.println("层序遍历开始"); while(!queue.isEmpty()){ TreeNode<T> tmp = queue.poll(); System.out.println(tmp.data); if(tmp.leftChild != null) queue.offer(tmp.leftChild); if(tmp.rightChild != null) queue.offer(tmp.rightChild); } System.out.println("层序遍历结束"); } } NoReBiTree非递归实现类：package com.dataStructure; import sun.reflect.generics.tree.Tree; import java.util.LinkedList; import java.util.Stack; /** * author zbl * * datetime 2019.11.266666 * */ public class NoReBiTree<T> extends ReBiTree{ //构造函数 public NoReBiTree(LinkedList<T> inputList){ super(inputList); } //前序遍历 非递归 private void preOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; while(tmp != null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 while(tmp != null){ System.out.println(tmp.data); stack.push(tmp); tmp = tmp.leftChild; } //如果节点没有左孩子，则弹出栈顶，访问节点右孩子 if(!stack.isEmpty()){ tmp = stack.pop(); tmp = tmp.rightChild; } } } //中序遍历 非递归 private void inOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; //当节点不为空，且栈不为空 while(tmp != null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 while(tmp != null){ stack.push(tmp); tmp = tmp.leftChild; } //访问叶子节点 System.out.println(tmp.data); //栈非空，说明还未遍历完 if(!stack.isEmpty()){ //父节点出栈 tmp = stack.pop(); //访问父节点 System.out.println(tmp.data); //访问右子树 tmp = tmp.rightChild; } } } //后序遍历 非递归 private void postOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; while(tmp != null || !stack.isEmpty()){ while(tmp != null){ stack.push(tmp); tmp = tmp.leftChild; } if(!stack.isEmpty()){ tmp = stack.pop(); //若为叶子节点，访问 if(tmp.rightChild == null) System.out.println(tmp.data); tmp = tmp.rightChild; } } } } TreeNode节点类：package com.dataStructure; /** * author zbl * * datetime 2019.11.266666 * */ //结点类 public class TreeNode<T> { //指向下一个结点 public TreeNode leftChild; public TreeNode rightChild; public T data; TreeNode(T data){ this.data = data; } } Main主函数:package com.dataStructure; import java.util.LinkedList; /** * author zbl * * datetime 2019.11.266666 * */ public class Main { public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<Integer>(); //二叉树值 linkedList.add(1); linkedList.add(2); linkedList.add(4); linkedList.add(null);linkedList.add(null); linkedList.add(5); linkedList.add(null);linkedList.add(null); linkedList.add(3); linkedList.add(null);linkedList.add(6); ReBiTree<Integer> noReBiTree = new ReBiTree<Integer>(linkedList); noReBiTree.PreOrder(); noReBiTree.InOrder(); noReBiTree.PostOrder(); noReBiTree.LerverOrder(); } } 参考文献王红梅，胡明，王涛编著. 数据结构（C++版）（第二版）[M]. 清华大学出版社.魏梦舒(@程序员小灰)著. 漫画算法--小灰的算法之旅 [M]. 电子工业出版社.
欢迎移步博主CSDN：CSDN博客数据结构----链表单链表单链表是用一组任意的存储单元存放线性表的元素，这组存储单元可以连续也可以不连续，甚至可以零散的分布在内存中的任意位置。简单来说就是在逻辑上连续，在物理上不连续的存储单元。代码实现：（以下代码起始位置为0）/* * @Author: zbl * @Date: 2019-11-01 16:03:37 * @Last Modified by: zbl * @Last Modified time: 2019-11-01 17:28:40 */ #include <iostream> using namespace std; //定义结点 template <class T> struct Node{ T data; Node<T>* next = NULL; }; //单链表的定义 template<class T> class LinkList{ private: //头结点 Node<T>* head; //链表长度 int length; public: //无参构造函数 LinkList(){} //有参构造函数 LinkList(T a[],int n); //析构函数 ~LinkList(); //定位元素x的位置 int locate(T x); //获取位置i的元素 T get(int i); //在i位置插入元素x void insert(int i , T x); //删除i位置的元素 T Delete(int i); //打印单链表 void display(); //获取单链表长度 int getLength(){return length;} }; //有参构造函数 template<class T> LinkList<T>::LinkList(T a[],int n){ length = n; Node<T>* tmp = new Node<T>(); head = tmp; int i = 0; while(i<n){ Node<T>* node = new Node<T>(); node->data = a[i++]; tmp->next = node; tmp = tmp->next; } delete tmp; //下标从0开始 head = head->next; } //析构函数 template <class T> LinkList<T>::~LinkList(){ length = 0; Node<T>* p = head; while(p->next != NULL){ Node<T>* tmp = p; p = p->next; tmp->next = NULL; delete tmp; } delete p; head = NULL; } //定位元素x的位置 template <class T> int LinkList<T>::locate(T x){ if(head == NULL) throw "链表为空!"; Node<T>* next = head; int i = 0; while(next != NULL){ if(next->data == x) return i; ++i; next = next->next; } //未找到 return -1; } //获取位置i的元素 template <class T> T LinkList<T>::get(int i){ if(i < 0) throw "下溢"; if(i > length - 1) throw "上溢"; Node<T>* next = head; while(i--){ next = next->next; } return next->data; } //在i位置插入元素x template <class T> void LinkList<T>::insert(int i , T x){ if(i < 0) throw "下溢"; if(i > length) throw "上溢"; //新建结点 Node<T>* node = new Node<T>(); node->data = x; //头插 if(i == 0){ node->next = head; head = node; } else{ Node<T>* tmp = head; while(--i){ tmp = tmp->next; } node->next = tmp->next; tmp->next = node; } length++; } //删除i位置的元素 template <class T> T LinkList<T>::Delete(int i){ if(i < 0) throw "下溢"; if(i > length - 1) throw "上溢"; Node<T>* del = head; //头删 if(i == 0){ head = head->next; } else{ Node<T>* tmp = head; while (--i) { tmp = head->next; } del = tmp->next; tmp->next = tmp->next->next; } T x = del->data; //释放空间 delete del; length--; return x; } //打印单链表 template <class T> void LinkList<T>::display(){ Node<T>* tmp = head; while(tmp != NULL) { cout<<tmp->data<<" "; tmp = tmp->next; } cout<<endl; } int main() { int a[10] = {1,2,3,4,5,6,7,8,9,10}; LinkList<int> linkList(a,10); linkList.display(); cout<<"头插：";linkList.insert(0,0);linkList.display();cout<<linkList.getLength()<<endl; cout<<"尾插：";linkList.insert(11,11);linkList.display();cout<<linkList.getLength()<<endl; cout<<"插入：";linkList.insert(2,22);linkList.display();cout<<linkList.getLength()<<endl; cout<<"删除位置2的元素"<<linkList.Delete(2)<<" ";linkList.display();cout<<linkList.getLength()<<endl; cout<<"查找位置为2的元素"<<linkList.get(2)<<endl;cout<<linkList.getLength()<<endl; cout<<"查找元素2所在的位置"<<linkList.locate(2)<<endl;cout<<linkList.getLength()<<endl; return 0; }运行结果：循环链表在单链表的基础上，如果将终端节点的指针域由空指针改为指向头结点，就使得整个链表形成了一个环，这种头尾相接的单链表称为循环链表。暂未进行编码实现双链表在单链表的基础上，添加一个指向其前驱结点的指针域，这样就形成了双链表。双链表使得找前驱结点变得简单。暂未进行编码实现参考文献王红梅，胡明，王涛编著. 数据结构（C++版）（第二版）[M]. 清华大学出版社.
欢迎移步博主CSDN：CSDN博客数据结构----顺序表简介线性表是一种最基本、最简单的数据结构，数据元素之间仅具有单一的前驱和后继关系。线性表是线性结构的典型代表。线性表的两种存储方式：顺序存储链接存储下面我们将分别对这两种方式进行学习并用代码实现。顺序表顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中，在计算机中一般采用数组进行存储(因为数组元素存放在一组地址连续的存储单元中)代码实现：#include <iostream> #define MAX_SIZE 100 using namespace std; /* * @Author: zbl * @Date: 2019-10-31 11:29:23 * @Last Modified by: zbl * @Last Modified time: 2019-10-31 11:33:51 */ template <class T> class SeqList { public: SeqList(T a[],int n); SeqList(); virtual ~SeqList(); int getLength(); T get(int i); int find(T x); void insert(int i,T x); T remove(int i); bool isEmpty(); void dispaly(); private: T data[MAX_SIZE]; int length; }; //构造函数 template <class T> SeqList<T>::SeqList(T a[], int n) { cout<<MAX_SIZE<<endl; if(n > MAX_SIZE) throw "参数非法!"; //初始化 for (int i = 0; i < n; ++i) { data[i] = a[i]; } length = n; } //无参构造函数 template <class T> SeqList<T>::SeqList(){ length = 0; //初始化 memset(data, 1, sizeof(data)); } //析构函数 template <class T> SeqList<T>::~SeqList() { //dtor } //获取长度 template <class T> int SeqList<T>::getLength(){ return length; } //获取i位置的元素 template <class T> T SeqList<T>::get(int i){ if(i < 0) throw "下溢"; else if(i > length - 1) throw "上溢"; else return data[i]; } //查找x元素的位置 template <class T> int SeqList<T>::find(T x){ for (int i = 0; i < length; ++i) { if(x == data[i]) return i; } //未找到 return -1; } //在i位置插入元素x template <class T> void SeqList<T>::insert(int i ,T x){ if(length == MAX_SIZE) throw "线性表已满!"; if(i<0||i>length) throw "参数非法!"; //头插 if(i==0){ for (int j = length; j > 0; --j) { data[j] = data[j-1]; } data[i] = x; } //尾插 else if(i==length){ data[i] = x; } //中间 else { for (int j = length; j > i; --j) { data[j] = data[j - 1]; } data[i] = x; } length++; } //删除位置为i的元素 template <class T> T SeqList<T>::remove(int i){ if(i<0||i>length-1) throw "参数非法!"; T x = data[i]; for (int j = i; i < length; ++i) { data[j] = data[j + 1]; } length--; return x; } //判断顺序表是否为空 template <class T> bool SeqList<T>::isEmpty() { return length==0?true:false; } //打印顺序表 template <class T> void SeqList<T>::dispaly(){ for (int i = 0; i < length; ++i) { cout<<data[i]<<" "; } cout<<endl; } int main() { int a[5] = {2,1,22,33,12}; //创建线性表 SeqList<int> seqlist(a,5); cout<<"第一次输出线性表："<<endl; seqlist.dispaly(); cout<<"查找元素22的位置："<<seqlist.find(22)<<endl; cout<<"插入元素5，头插"<<endl; seqlist.insert(0,5); seqlist.dispaly(); cout<<"插入元素25，尾插"<<endl; seqlist.insert(6,25); seqlist.dispaly(); cout<<"插入元素100"<<endl; seqlist.insert(3,100); seqlist.dispaly(); cout<<"删除位置为3的元素"<<seqlist.remove(3)<<endl; cout<<"线性表长度："<<seqlist.getLength()<<endl; return 0; }运行结果：由于开始我是将SeqList类的定义和实现分开在2个文件中写的，导致在编译时main函数报错，原因在于在使用模板类时不能将类的定义与实现分开写，这样在使用时编译器找不到类中函数的实现，报错信息如下：undefined reference to `SeqList<int>::SeqList(int*, int)' undefined reference to `SeqList<int>::xxx undefined reference to `SeqList<int>::xxx undefined reference to `SeqList<int>::xxx undefined reference to `SeqList<int>::xxx undefined reference to `SeqList<int>::xxx参考文献王红梅，胡明，王涛编著. 数据结构（C++版）（第二版）[M]. 清华大学出版社.