In addition to Weibo, there is also WeChat
Please pay attention
WeChat public account
Shulou
2025-01-18 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Development >
Share
Shulou(Shulou.com)06/01 Report--
This article will explain in detail how to find the minimum spanning tree for Java. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.
1 Overview of minimum spanning tree
Spanning tree (SpanningTree): a spanning tree of a connected graph is a connected subgraph that contains all n vertices in the graph, but only 1 edges that are sufficient to form a tree. A spanning tree with n vertices has and only has 1 edge. If another edge is added to the spanning tree, it must be a ring.
Minimum spanning tree (Minimum Spanning Tree): in all spanning trees of a connected graph, the weights of all edges and the smallest spanning tree are called minimum spanning tree.
In life, graphic structure is the most widely used. For example, the common choice of communication network construction route, the village can be regarded as the vertex, if there is a communication path between the villages, it can be counted as the edge or arc between the two points, and the communication cost between the two villages can be regarded as the weight of the edge or arc.
The picture above is an example of how the choice of communication network construction route in life is mapped to the graphic structure. As a village, the vertex has the edge if there is a communication path between the villages, and the cost of communication between the villages is the weight of the edge.
A very common demand is to require that all villages that can communicate must communicate, and the cost of communication construction is minimal, after all, the funds are "limited" and the funds saved, hehe!
The above problem, transformed into a mathematical model, is the problem of finding the minimum spanning tree of a graph, that is, selecting a path that connects all connected vertices with minimum weights. There are many solutions to this problem, the most classical of which are Prim algorithm and Kruskal algorithm.
2 principle of Prim algorithm (Prim) 2.1,
The Prim algorithm starts with a vertex, assumes that all vertices are not connected, and gradually finds the edges with the least weight on each vertex to connect and construct the minimum spanning tree. Is to build the minimum spanning tree with the point as the target.
The specific steps are as follows: first, randomly select a vertex a, look for vertex a to connect all vertices, select a vertex with low weight to connect, and then find all vertices that are connected to these two vertices or all vertices that can be connected. select a vertex with a low weight to connect with one of the vertices Each time, select the shortest vertex from any connected end vertex (rather than the shortest vertex from the first vertex) to connect until all the vertices are connected, so that the minimum spanning tree is built.
2.2 case study
This case corresponds to the case in the following implementation code.
In the above figure, first select vertex An as the connected point, find vertex A to connect all vertices C, D, F, and select a vertex with low weight to connect. Here, select Amurc.
Then look for all vertices that can be connected to An or C (excluding connected points), find B, D, F, a total of four edges to choose from, Amure D, Amurf, Cmurb, Cmurd, select a vertex with low weight to connect with one of them, here obviously choose Amurd connection
Then look for all vertices that can be connected to An or C or D (excluding connected points), find B, F, a total of three edges to choose from, Cmurb, Dmurb, Amurf, select a vertex with low weight to connect with one of the vertices, here obviously choose Amurf connection
Then look for all vertices that can be connected to An or C or D or F (excluding connected points), find B, G, a total of three edges to choose from, Cmurb, Dmurb, Fmai G, select a vertex with low weight to connect with one of them, here obviously choose CmurB connection
Then look for all the vertices that can be connected to An or C or D or F or B (excluding connected points), find E and G, and there are two edges to choose from. Bmure E, Fmai G, select a vertex with low weight to connect with one of the vertices. Here you obviously choose Bmure connection.
Then look for all vertices that can be connected to An or C or D or F or B or E (excluding connected points), find G, there are two edges to choose from, Emurg G, Fmure G, choose a vertex with low weight to connect with one of them, here obviously choose EmurG connection
When all the vertices are connected, the minimum spanning tree has been built with a minimum weight of 23.
3Cruskal algorithm (Kruskal) 3.1principle
The Kruskal algorithm (Kruskal) builds the minimum spanning tree gradually according to the weight of the edge, which aims at the edge.
The specific steps are: treat each vertex of the weighted graph as a forest, then arrange the weights of each adjacent edge in the graph in ascending order, then extract the edge with the least weight from the arranged adjacent edge table, write the start and end vertices of the edge, connect the vertices to form a tree of the forest, then read the adjacent edges of the start and end vertices, and give priority to extracting the adjacent edges with small weights. Continue to connect the vertices to form the forest into a tree. The requirement for adding adjacent edges is that the adjacent edges added to the graph do not form a loop (ring). Do this over and over again until you have added an edge called nmur1. At this point, the minimum spanning tree is built.
3.2 case study
This case corresponds to the case in the following implementation code, and the traditional Kruskal algorithm process is as follows:
First, obtain the array of edge sets and sort them according to the weight from small to large. In the sorting in the code, you can directly use sort sorting, or you can implement heap sorting by yourself. The result after sorting is as follows:
Edge {from=A, to=C, weight=1}
Edge {from=D, to=A, weight=2}
Edge {from=A, to=F, weight=3}
Edge {from=B, to=C, weight=4}
Edge {from=C, to=D, weight=5}
Edge {from=E, to=G, weight=6}
Edge {from=E, to=B, weight=7}
Edge {from=D, to=B, weight=8}
Edge {from=F, to=G, weight=9}
Take out the first edge of the loop, Amurc, and judge that the minimum spanning tree that has been found will not form a loop, and the sum of weights will increase by 1. Continue.
The loop takes out the second edge DMurA, judging that the minimum spanning tree that has been found will not form a loop, and the sum of weights will be increased by 2. Continue.
Take out the third side of the loop, Amurf, and judge that the minimum spanning tree that has been found will not form a loop, and the sum of weights will increase by 3. Continue.
The loop takes out the fourth edge BMEC, and determines that the minimum spanning tree found will not form a loop, and the sum of weights will increase by 4. Continue.
The loop takes out the fifth edge Cmurd, and determines that it will form a loop with the minimum spanning tree that has been found. The edge will be discarded. Continue.
The loop takes out the 6th edge Emurg, and determines that the minimum spanning tree that has been found will not form a loop. The sum of weights will increase by 6. Continue.
The loop takes out the 7th edge Emurb, and determines that the minimum spanning tree found will not form a loop, and the sum of weights will increase by 7. Continue.
The loop takes out the 8th edge Dmurb, and determines that it will form a loop with the minimum spanning tree that has been found. The edge will be discarded. Continue.
Take out the 9th edge Fmurg in the loop and judge that it will form a loop with the minimum spanning tree that has been found. The edge will be discarded and continue.
At the end of the loop, the minimum spanning tree has been found, and the total weight of the minimum spanning tree is 23.
In the above steps, it is critical to judge whether to form a ring. The usual practice is to sort the vertices of the smallest spanning tree that have been found (from the starting point to the end point), and then each new edge is added. Use the starting point and end point of the newly added edge to take the minimum binary tree to find the same end point, which means that the minimum spanning tree plus this edge will form a ring, otherwise it will not. Then update the end of the sort.
4 implementation of weighted graph of adjacency matrix
The implementation here can construct a class of undirected weighted graph based on adjacency matrix, and provide the methods of depth-first traversal and breadth-first traversal, the method of obtaining the array of edge sets, and the methods of Prim and Kruskal to find the minimum spanning tree.
/ * * undirected weighted graph adjacency matrix implementation * {@ link MatrixPrimAndKruskal#MatrixPrimAndKruskal (E []) Edge []} construct undirected weighted graph * {@ link MatrixPrimAndKruskal#DFS ()} depth first traversal undirected weighted graph * {@ link MatrixPrimAndKruskal#BFS ()} breadth first traversal undirected weighted graph * {@ link MatrixPrimAndKruskal#toString ()} output undirected weighted graph * {@ link MatrixPrimAndKruskal#prim ()} Prim algorithm to achieve minimum spanning tree * {@ link MatrixPrimAndKruskal#kruskal ()} Kruskal algorithm Implement the minimum spanning tree * {@ link MatrixPrimAndKruskal#kruskalAndPrim ()} Kruskal algorithm combined with the Prim algorithm to achieve the minimum spanning tree * {@ link MatrixPrimAndKruskal#getEdges ()} to obtain the edge set array * * @ author lx * @ date 18:13 on 2020-5-14 * / public class MatrixPrimAndKruskal {/ * vertex array * / private Object [] vertexs / * adjacency matrix * / private int [] [] matrix; / * / private Edge [] edges Since it is a weighted graph, the upper limit of the weight of an edge is set here. The maximum weight of any edge cannot be greater than or equal to this value. In practical application, the value should be determined according to the actual situation * / private static final int NO_EDGE = 99. / * Edge object with weights, using * / private static class Edge {private E from; private E to; private int weight; public Edge (E from, E to, int weight) {this.from = from; this.to = to; this.weight = weight when building a weighted undirected graph } @ Override public String toString () {return "Edge {" + "from=" + from + ", to=" + to + ", weight=" + weight +'}' }} / * create an undirected weighted graph * * @ param vertexs vertex array * @ param edges edge object array * / public MatrixPrimAndKruskal (Object [] vertexs, Edge [] edges) {/ / initialize edge array this.edges = edges / / initialize the vertex array and add vertex this.vertexs = Arrays.copyOf (vertexs, vertexs.length); / / initialize the edge matrix and prepopulate the edge information this.matrix = new int [vertexs.length] [vertexs.length]; for (int I = 0; I)
< vertexs.length; i++) { for (int j = 0; j < vertexs.length; j++) { if (i == j) { this.matrix[i][j] = 0; } else { this.matrix[i][j] = NO_EDGE; } } } for (Edge edge : edges) { // 读取一条边的起始顶点和结束顶点索引值 int p1 = getPosition(edge.from); int p2 = getPosition(edge.to); //对称的两个点位都置为edge.weight,无向图可以看作相互可达的有向图 this.matrix[p1][p2] = edge.weight; this.matrix[p2][p1] = edge.weight; } } /** * 获取某条边的某个顶点所在顶点数组的索引位置 * * @param e 顶点的值 * @return 所在顶点数组的索引位置, 或者-1 - 表示不存在 */ private int getPosition(E e) { for (int i = 0; i < vertexs.length; i++) { if (vertexs[i] == e) { return i; } } return -1; } /** * 深度优先搜索遍历图,类似于树的前序遍历, */ public void DFS() { //新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点 boolean[] visited = new boolean[vertexs.length]; //初始化所有顶点都没有被访问 for (int i = 0; i < vertexs.length; i++) { visited[i] = false; } System.out.println("DFS: "); for (int i = 0; i < vertexs.length; i++) { if (!visited[i]) { DFS(i, visited); } } System.out.println(); } /** * 深度优先搜索遍历图的递归实现,类似于树的先序遍历 * 因此模仿树的先序遍历,同样借用栈结构,这里使用的是方法的递归,隐式的借用栈 * * @param i 顶点索引 * @param visited 访问标志数组 */ private void DFS(int i, boolean[] visited) { visited[i] = true; System.out.print(vertexs[i] + " "); // 遍历该顶点的所有邻接点。若该邻接点是没有访问过,那么继续递归遍历领接点 for (int w = firstVertex(i); w >= 0; w = nextVertex (I, w)) {if (! visited [w]) {DFS (w, visited) } / * breadth-first search graph, which is similar to the sequence traversal of a tree * so it simulates the sequence traversal of a tree and also borrows the queue structure * / public void BFS () {/ / auxiliary group queue Queue indexLinkedList = new LinkedList () / / create a new vertex access tag array. Each index corresponds to vertices in the vertex array with the same index boolean [] visited = new boolean [vertexs.length]; for (int I = 0; I)
< vertexs.length; i++) { visited[i] = false; } System.out.println("BFS: "); for (int i = 0; i < vertexs.length; i++) { if (!visited[i]) { visited[i] = true; System.out.print(vertexs[i] + " "); indexLinkedList.add(i); } if (!indexLinkedList.isEmpty()) { //j索引出队列 Integer j = indexLinkedList.poll(); //继续访问j的邻接点 for (int k = firstVertex(j); k >= 0; k = nextVertex (j, k)) {if (! visited [k]) {visited [k] = true; System.out.print (vertexs [k] + ""); / / continue to queue indexLinkedList.add (k) } System.out.println () } / * returns the index of the first adjacent vertex of vertex v. If it fails, it returns the index of-1 * * @ param v vertex v in the array * @ return returns the index of the first adjacent vertex of vertex v, or returns-1 * / private int firstVertex (int v) {/ / if the index is out of range,-1 if (v)
< 0 || v >(vertexs.length-1)) {return-1;} / * according to the law of the adjacency matrix: the vertex index v corresponds to the matrix [v] [I] row record of the edge two-dimensional matrix * starting with iS0 * / for (int iS0; I)
< vertexs.length; i++) { if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) { return i; } } return -1; } /** * 返回顶点v相对于w的下一个邻接顶点的索引,失败则返回-1 * * @param v 顶点索引 * @param w 第一个邻接点索引 * @return 返回顶点v相对于w的下一个邻接顶点的索引,失败则返回-1 */ private int nextVertex(int v, int w) { //如果索引超出范围,则返回-1 if (v < 0 || v >(vertexs.length-1) | | w
< 0 || w >(vertexs.length-1)) {return-1;} / * according to the law of the adjacency matrix: the vertex index v corresponds to the matrix [v] [I] row record of the edge two-dimensional matrix * since the index of the adjacency point w has been obtained, we start looking for * / for (int i=w+1; I) from i=w+1.
< vertexs.length; i++) { if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) { return i; } } return -1; } /** * 输出图 * * @return 输出图字符串 */ @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < vertexs.length; i++) { for (int j = 0; j < vertexs.length; j++) { stringBuilder.append(matrix[i][j]).append("\t"); } stringBuilder.append("\n"); } return stringBuilder.toString(); } /** * Prim算法求最小生成树 */ public void prim() { System.out.println("prim: "); //对应节点应该被连接的前驱节点,用来输出 //默认为0,即前驱结点为第一个节点 int[] mid = new int[matrix.length]; //如果某顶点作为末端顶点被连接,对应位置应该为true //第一个顶点默认被连接 boolean[] connected = new boolean[matrix.length]; connected[0] = true; //存储未连接顶点到已连接顶点的最短距离(最小权) int[] dis = new int[matrix.length]; //首先将矩阵第一行即其他顶点到0索引顶点的权值拷贝进去 System.arraycopy(matrix[0], 0, dis, 0, matrix.length); //存储路径长度 int sum = 0; //最小权值 int min; /*默认第一个顶点已经找到了,因此最多还要需要大循环n-1次*/ for (int k = 1; k < matrix.length; k++) { min = NO_EDGE; //最小权值的顶点的索引 int minIndex = 0; /*寻找权值最小的且未被连接的顶点索引*/ for (int i = 1; i < matrix.length; i++) { //排除已连接的顶点,排除权值等于0的值,这里权值等于0表示已生成的最小生成树的顶点都未能与该顶点连接 if (!connected[i] && dis[i] != 0 && dis[i] < min) { min = dis[i]; minIndex = i; } } //如果没找到,那么该图可能不是连通图,直接返回了,此时最小生成树没啥意义 if (minIndex == 0) { return; } //权值和增加 sum += min; //该新连接顶点对应的索引值变成true,表示已被连接,后续判断时跳过该顶点 connected[minIndex] = true; //输出对应的前驱顶点到该最小顶点的权值 System.out.println(vertexs[mid[minIndex]] + " --->"+ vertexs [minIndex] +" weight: "+ min); / * the minimum weights of all other vertices to connected vertices before the new vertex minIndex is added have been calculated, so you only need to update other unconnected vertices to see if minIndex has shorter weights, and if so, update to find the vertex with the least weight from the connected vertex * / for (int I = 1; I).
< matrix.length; i++) { //如果该顶点未连接 if (!connected[i]) { /*如果新顶点到未连接顶点i的权值不为0,并且比原始顶点到未连接顶点i的权值还要小,那么更新对应位置的最小权值*/ if (matrix[minIndex][i] != 0 && dis[i] >Matrix [minIndex] [I]) {/ / update the minimum weight dis [I] = matrix [minIndex] [I]; / / update the precursor node index as the newly added node index mid [I] = minIndex } System.out.println ("sum:" + sum);} / * Kruskal algorithm to find the traditional implementation of the minimum spanning tree, requires to know the edge set array, and vertex array * / public void kruskal () {System.out.println ("Kruskal:") / / since the edge set array is saved when creating the graph, you can just use / / Edge [] edges= getEdges (); / / this.edges=edges; / / sort the edge set array with a pair of Arrays.sort (this.edges, Comparator.comparingInt (o-> o.weight)) / / the index int [] vends = new int [this.edges.length] used to hold the final end point of each vertex in the existing minimum spanning tree; / / it is possible to know that the end point index range is [0dthis.edges.endthway1], so filling edges.length means there is no destination Arrays.fill (vends, this.edges.length); int sum = 0 For (Edge edge: this.edges) {/ / get the start index from int from = getPosition (edge.from) of the I edge; / / get the end index to int to = getPosition (edge.to) of the I edge; / / get the end point int m = getEndIndex (vends, from) of the vertex from in the "minimum spanning tree available" / / get the end point of vertex to in the "existing minimum spanning tree" int n = getEndIndex (vends, to) / / if no loop is formed, it can be added, otherwise it can be skipped directly, and the next edge will be judged by if (masking n) {/ / add the original end point index m to n vends [m] = n in the existing minimum spanning tree. System.out.println (vertexs [from] + "-->" + vertexs [to] + "weight:" + edge.weight); sum + = edge.weight;}} System.out.println ("sum:" + sum); / / System.out.println (Arrays.toString (this.edges)) } / * get the end point of vertex index I if there is no end point, return vertex index itself * * @ param vends vertex index in the minimum spanning tree * @ param I vertex index * @ return vertex index I end point if there is no end point return vertex index itself * / private int getEndIndex (int [] vends) Int I) {/ / the logic of circular search is used here to find the final destination while (vends [I]! = this.edges.length) {I = vends [I] } return I;} / * if there is no ready-made edge set array, then obtain the edge set array of the graph * * @ return graph according to the adjacency matrix structure * / private Edge [] getEdges () {List edges = new ArrayList () / * traversing the matrix array requires only half of the traversal * / for (int I = 0; I)
< vertexs.length; i++) { for (int j = i + 1; j < vertexs.length; j++) { //如果存在边 if (matrix[i][j] != NO_EDGE && matrix[i][j] != 0) { edges.add(new Edge(vertexs[i], vertexs[j], matrix[i][j])); //edges[index++] = new Edge(vertexs[i], vertexs[j], matrix[i][j]); } } } return edges.toArray(new Edge[0]); } /** * Kruskal结合Prim算法.不需要知道边集,只需要矩阵数组,和顶点数组 * 同样是求最小权值的边,但是有一个默认起点顶点,该起点可以是要求[0,顶点数量-1]之间的任意值,同时查找最小权的边。 * 可能会有Bug,目前未发现 */ public void kruskalAndPrim() { System.out.println("kruskalAndPrim: "); //已经找到的边携带的顶点对应的索引将变为true,其余未找到边对应的顶点将是false boolean[] connected = new boolean[matrix.length]; //这里选择第一个顶点为起点,表示以该顶点开始寻找包含该顶点的最小边 connected[0] = true; int sum = 0, n1 = 0, n2 = 0; //最小权值 int min; while (true) { min = NO_EDGE; /*找出所有带有已找到顶点的边中,最小权值的边,只需要寻找对称矩阵的一半即可*/ //第一维 for (int i = 0; i < matrix.length; i++) { //第二维 for (int j = i + 1; j < matrix.length; j++) { //排除等于0的,排除两个顶点都找到了的,这里实际上已经隐含了排除环的逻辑,如果某条边的两个顶点都找到了,那么如果算上该条边,肯定会形成环 //寻找剩下的最小的权值的边 if (matrix[i][j] != 0 && connected[i] != connected[j] && matrix[i][j] < min) { min = matrix[i][j]; n1 = i; n2 = j; } } } //如果没找到最小权值,该图可能不是连通图,或者已经寻找完毕,直接返回 if (min == NO_EDGE) { System.out.println(" sum:" + sum); return; } //已经找到的边对应的两个顶点都置为true connected[n1] = true; connected[n2] = true; //输出找到的边和最小权值 System.out.println(vertexs[n1] + " --->"+ vertexs [N2] +" weight: "+ min); sum + = min;}} public static void main (String [] args) {/ / vertex array Character [] vexs = {'Anodic,' baked, 'clocked,' dashed, 'eyed,' faded,'G'} / / Edge array, weighted values Edge [] edges = {new Edge ('A','C', 1), new Edge ('A','A', 2), new Edge ('A','C', 3), new Edge ('B,'C, 4), new Edge ('C') 'During, 5), new Edge ('estranged,' Globe, 6), new Edge ('estranged,' baked, 7), new Edge ('dashed,' baked, 8), new Edge ('faded,' Globe, 9)} / / Construction diagram MatrixPrimAndKruskal matrixPrimAndKruskal = new MatrixPrimAndKruskal (vexs, edges); / / output graph System.out.println (matrixPrimAndKruskal); / / depth-first traversal matrixPrimAndKruskal.DFS (); / / breadth-first traversal matrixPrimAndKruskal.BFS (); / / Prim algorithm output minimum spanning tree matrixPrimAndKruskal.prim () / / the Kruskal algorithm outputs the minimum spanning tree matrixPrimAndKruskal.kruskal (); / / the Kruskal algorithm combined with the Prim algorithm outputs the minimum spanning tree, which may have Bug, but matrixPrimAndKruskal.kruskalAndPrim () has not been found; / / get the edge set array Edge [] edges1 = matrixPrimAndKruskal.getEdges (); System.out.println (Arrays.toString (edges1));}} 5 adjacency table weighted graph implementation
The implementation here can construct a class of undirected weighted graph based on adjacency table, and provide the methods of depth-first traversal and breadth-first traversal, the method of obtaining the array of edge sets, and the methods of Prim and Kruskal to find the minimum spanning tree.
/ * undirected weighted graph adjacency table implementation * {@ link ListPrimAndKruskal#ListPrimAndKruskal (E []) Edge []} construct undirected weighted graph * {@ link ListPrimAndKruskal#DFS ()} depth first traversal undirected weighted graph * {@ link ListPrimAndKruskal#BFS ()} breadth first traversal undirected weighted graph * {@ link ListPrimAndKruskal#toString ()} output undirected weighted graph * {@ link ListPrimAndKruskal#prim ()} Prim algorithm to achieve minimum spanning tree * {@ link ListPrimAndKruskal#kruskal ()} Kruskal algorithm Implement the minimum spanning tree * {@ link ListPrimAndKruskal#getEdges ()} get the edge set array * * @ author lx * @ date 23:31 on 2020-5-14 * / public class ListPrimAndKruskal {/ * vertex classes * * @ param * / private class Node {/ * vertex information * / E data / * points to the first edge attached to the vertex * / LNode firstLNode; public Node (E data, LNode firstLNode) {this.data = data; this.firstLNode = firstLNode }} / * Edge Table Node Class * / private class LNode {/ * Index position of vertices pointed to by the edge * / int vertex; / * weight of the edge * / int weight / * pointer to the next edge * / LNode nextLNode;} / * edge object, with weights, using * / private static class Edge {private E from; private E to; private int weight when building a weighted undirected graph Public Edge (E from, E to, int weight) {this.from = from; this.to = to; this.weight = weight } @ Override public String toString () {return "Edge {" + "from=" + from + ", to=" + to + ", weight=" + weight +'}';} / * * vertex array * / private Node [] vertexs / * Edge array * / private Edge [] edges; / * because it is a weighted graph, the upper limit of the weight of an edge is set here. The maximum weight of any edge cannot be greater than or equal to this value. In practical application, the value should be determined according to the actual situation * / private static final int NO_EDGE = 99. / * create an undirected weighted graph * * @ param vexs vertex array * @ param edges edge 2D array * / public ListPrimAndKruskal (E [] vexs, Edge [] edges) {this.edges = edges; / * initialize the vertex array and add vertices * / vertexs = new Node [vexs.length]; for (int I = 0; I
< vertexs.length; i++) { vertexs[i] = new Node(vexs[i], null); } /*初始化边表,并添加边节点到边表尾部,即采用尾插法*/ for (Edge edge : edges) { // 读取一条边的起始顶点和结束顶点索引值 int p1 = getPosition(edge.from); int p2 = getPosition(edge.to); int weight = edge.weight; /*这里需要相互添加边节点,无向图可以看作相互可达的有向图*/ // 初始化lnode1边节点 LNode lnode1 = new LNode(); lnode1.vertex = p2; lnode1.weight = weight; // 将LNode链接到"p1所在链表的末尾" if (vertexs[p1].firstLNode == null) { vertexs[p1].firstLNode = lnode1; } else { linkLast(vertexs[p1].firstLNode, lnode1); } // 初始化lnode2边节点 LNode lnode2 = new LNode(); lnode2.vertex = p1; lnode2.weight = weight; // 将lnode2链接到"p2所在链表的末尾" if (vertexs[p2].firstLNode == null) { vertexs[p2].firstLNode = lnode2; } else { linkLast(vertexs[p2].firstLNode, lnode2); } } } /** * 获取某条边的某个顶点所在顶点数组的索引位置 * * @param e 顶点的值 * @return 所在顶点数组的索引位置, 或者-1 - 表示不存在 */ private int getPosition(E e) { for (int i = 0; i < vertexs.length; i++) { if (vertexs[i].data == e) { return i; } } return -1; } /** * 将lnode节点链接到边表的最后,采用尾插法 * * @param first 边表头结点 * @param node 将要添加的节点 */ private void linkLast(LNode first, LNode node) { while (true) { if (first.vertex == node.vertex) { return; } if (first.nextLNode == null) { break; } first = first.nextLNode; } first.nextLNode = node; } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < vertexs.length; i++) { stringBuilder.append(i).append("(").append(vertexs[i].data).append("): "); LNode node = vertexs[i].firstLNode; while (node != null) { stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append("-").append(node.weight).append(")"); node = node.nextLNode; if (node != null) { stringBuilder.append("->");} else {break;}} stringBuilder.append ("\ n ");} return stringBuilder.toString () } / * * the recursive implementation of the depth-first search traversal graph is similar to the preorder traversal of the tree * so it simulates the preorder traversal of the tree and also borrows the stack structure, which is the recursion of the method, the implicit borrowing stack * * @ param I vertex index * @ param visited access flag array * / private void DFS (int I) Boolean [] visited) {/ / Index is marked as true, indicating that visited [I] = true has been accessed System.out.print (vertexs [I] .data + "); / / get the vertex's edge header node LNode node = vertexs [I] .firstLNode; / / cycle through the vertex's adjacent points, and recursively search for while (node! = null) {if (! visited [node.vertex]) {DFS (node.vertex, visited) in the same way } node = node.nextLNode;}} / * depth first search traversal graph, similar to the preorder traversal of the tree, * / public void DFS () {/ / create a new vertex access tag array, corresponding to each index corresponding to the vertex array of vertices in the same index boolean [] visited = new boolean [vertexs.length] / / initialize all vertices without access to for (int I = 0; I
< vertexs.length; i++) { visited[i] = false; } System.out.println("DFS: "); /*循环搜索*/ for (int i = 0; i < vertexs.length; i++) { //如果对应索引的顶点的访问标记为false,则搜索该顶点 if (!visited[i]) { DFS(i, visited); } } /*走到这一步,说明顶点访问标记数组全部为true,说明全部都访问到了,深度搜索结束*/ System.out.println(); } /** * 广度优先搜索图,类似于树的层序遍历 * 因此模仿树的层序遍历,同样借用队列结构 */ public void BFS() { // 辅组队列 Queue indexLinkedList = new LinkedList(); //新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点 boolean[] visited = new boolean[vertexs.length]; //初始化所有顶点都没有被访问 for (int i = 0; i < vertexs.length; i++) { visited[i] = false; } System.out.println("BFS: "); for (int i = 0; i < vertexs.length; i++) { //如果访问方剂为false,则设置为true,表示已经访问,然后开始访问 if (!visited[i]) { visited[i] = true; System.out.print(vertexs[i].data + " "); indexLinkedList.add(i); } //判断队列是否有值,有就开始遍历 if (!indexLinkedList.isEmpty()) { //出队列 Integer j = indexLinkedList.poll(); LNode node = vertexs[j].firstLNode; while (node != null) { int k = node.vertex; if (!visited[k]) { visited[k] = true; System.out.print(vertexs[k].data + " "); //继续入队列 indexLinkedList.add(k); } node = node.nextLNode; } } } System.out.println(); } /** * Prim算法求最小生成树 */ public void prim() { System.out.println("prim: "); //对应节点应该被连接的前驱节点,用来输出 //默认为0,即前驱结点为第一个节点 int[] mid = new int[vertexs.length]; int start = 0; int min, tmp, sum = 0; int num = vertexs.length; //顶点间边的权值 //存储未连接顶点到已连接顶点的最短距离(最小权) int[] dis = new int[num]; // 初始化"顶点的权值数组", // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。 //首先将其他顶点到0索引顶点的权值存储进去 for (int i = 0; i < num; i++) { dis[i] = getWeight(start, i); } //如果某顶点作为末端顶点被连接,对应位置应该为true //第一个顶点默认被连接 boolean[] connected = new boolean[vertexs.length]; connected[0] = true; /*默认第一个顶点已经找到了,因此最多还要需要大循环n-1次*/ for (int k = 1; k < num; k++) { min = NO_EDGE; //最小权值的顶点的索引 int minIndex = 0; // 在未被加入到最小生成树的顶点中,找出权值最小的顶点。 for (int i = 1; i < vertexs.length; i++) { //排除已连接的顶点,排除权值等于0的值,因为这里默认顶点指向自己的权值为0 if (!connected[i] && dis[i] != 0 && dis[i] < min) { min = dis[i]; minIndex = i; } } //如果没找到,那么该图可能不是连通图,直接返回了,此时最小生成树没啥意义 if (minIndex == 0) { return; } //权值和增加 sum += min; //该新连接顶点对应的索引值变成true,表示已被连接,后续判断时跳过该顶点 connected[minIndex] = true; //输出对应的前驱顶点到该最小顶点的权值 System.out.println(vertexs[mid[minIndex]].data + " --->"+ vertexs [minIndex] .data +" weight: "+ min); / * the minimum weight of all other vertices to the connected vertex before the new vertex minIndex is added has been calculated, so you only need to update the other vertices to see if there are shorter weights for the newly connected vertex minIndex, and if so, update to find the vertex with the least weight from the connected vertex * / for (int I = 1; I)
< num; i++) { //如果该顶点未连接 if (!connected[i]) { // 获取minindex顶点到未连接顶点i的权值 tmp = getWeight(minIndex, i); /*如果新顶点到未连接顶点i的权值不为0,并且比原始顶点到未连接顶点i的权值还要小,那么更新对应位置的最小权值*/ if (tmp != 0 && dis[i] >Tmp) {dis [I] = tmp; / / Update the precursor node index mid [I] = minIndex;} System.out.println ("sum:" + sum) } / * try to get the weight of the edge from the beginning of the edge start to the end of the edge end, of course, you may not get the weight of * * @ param start edge start * @ param end edge end * @ return; if the start point and the end point are the same, return 0 If there is no edge between the beginning and end of the edge, return NO_EDGE * / private int getWeight (int start, int end) {/ / if start=end, then return 0 if (start= = end) {return 0;} / / get the first value of the edge table of the vertex LNode node = vertexs [start] .firstLNode / / Loop to find the edge table to see if you can find the corresponding index = end. If you can't find it, return NO_EDGE, indicating that the two vertices are not connected. While (node! = null) {if (end = = node.vertex) {return node.weight;} node = node.nextLNode;} return NO_EDGE } / * Kruskal algorithm to find the minimum spanning tree, it can be said that the adjacency matrix and the adjacency list are implemented in the same way * / public void kruskal () {/ / since the edge set array is saved when creating the graph, you can just use it here / / Edge [] edges= getEdges (); / / this.edges=edges / / an array of edge sets is sorted Arrays.sort (this.edges, Comparator.comparingInt (o-> o.weight)); / / the index int [] vends = new int [this.edges.length] used to hold the final end point of each vertex in the existing minimum spanning tree / / it is possible to know that the end index range is [0herothis.edges.futhmer1], so filling edges.length means there is no end point Arrays.fill (vends, this.edges.length); int sum = 0; for (Edge edge: this.edges) {/ / get the starting index from int from = getPosition (edge.from) of the first edge. / / get the end point index of edge I to int to = getPosition (edge.to); / / get the end point of vertex from in "existing minimum spanning tree" int m = getEndIndex (vends, from); / / get the end point of vertex to in "existing minimum spanning tree" int n = getEndIndex (vends, to) / / if no loop is formed, it can be added, otherwise it can be skipped directly, and the next edge will be judged by if (masking n) {/ / add the original end point index m to n vends [m] = n in the existing minimum spanning tree. System.out.println (vertexs [from] .data + "-->" + vertexs [to] .data + "weight:" + edge.weight); sum + = edge.weight;}} System.out.println ("sum:" + sum); / / System.out.println (Arrays.toString (this.edges)) } / * get the end point of vertex index I if there is no end point, return vertex index itself * * @ param vends vertex index in the minimum spanning tree * @ param I vertex index * @ return vertex index I end point if there is no end point return vertex index itself * / private int getEndIndex (int [] vends) Int I) {/ / the logic of circular search is used here to find the final destination while (vends [I]! = this.edges.length) {I = vends [I] } return I;} / * if there is no ready-made edge set array, then the edge set array of the graph * * @ return graph is obtained according to the adjacency table structure * / private Edge [] getEdges () {List edges = new ArrayList (); / / traversal vertex array for (int I = 0; I)
< vertexs.length; i++) { LNode node = vertexs[i].firstLNode; while (node != null) { //只需添加起点索引小于终点索引的边就行了 if (node.vertex >I) {edges.add (new Edge (vertexs [I] .data, vertexs [node.vertex] .data, node.weight));} node = node.nextLNode;}} return edges.toArray (new Edge [0]) } public static void main (String [] args) {/ / vertex array Character [] vexs = {'Agar,' baked, 'clocked,' dashed, 'eyed,' faded,'G'} / / Edge array, weighted values Edge [] edges = {new Edge ('A','C', 1), new Edge ('A','A', 2), new Edge ('A','C', 3), new Edge ('B,'C, 4), new Edge ('C') 'During, 5), new Edge ('estranged,' Globe, 6), new Edge ('estranged,' baked, 7), new Edge ('dashed,' baked, 8), new Edge ('faded,' Globe, 9)} / / build ListPrimAndKruskal listPrimAndKruskal = new ListPrimAndKruskal (vexs, edges); / / output diagram System.out.println (listPrimAndKruskal); / / depth-first traversal / / DFS: / / A C B E G F D listPrimAndKruskal.DFS (); / / breadth-first traversal / / BFS: / / A C DF B G E listPrimAndKruskal.BFS () / / Prim algorithm to find the minimum spanning tree listPrimAndKruskal.prim (); / Kruskal algorithm to find the minimum spanning tree listPrimAndKruskal.kruskal (); / / to get the edge set array Edge [] edges1 = listPrimAndKruskal.getEdges (); System.out.println (Arrays.toString (edges1)) }} this is the end of the article on "how to find the minimum spanning tree for Java". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.
Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.
Views: 291
*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.
Continue with the installation of the previous hadoop.First, install zookooper1. Decompress zookoope
"Every 5-10 years, there's a rare product, a really special, very unusual product that's the most un
© 2024 shulou.com SLNews company. All rights reserved.