The so-called authority chart means that each edge in the chart will have a corresponding one or a group of values. Normally, this value is just a number
For example: In a transportation network, the weight on the side may represent the distance or the transportation cost (obviously both are numbers). However, the weight on the edge may also be something else, such as a string or even a more complex data packet, which collects more data
The core idea of the Kruskar algorithm is: in the weighted connection graph, the smallest edge is constantly found in the edge set. If the edge meets the conditions for obtaining the minimum spanning tree, it is constructed until a minimum spanning tree is finally obtained.
Execution steps of the Kruskar algorithm:
Step 1: In the weighted connection graph, sort the weights of edges;
Step 2: Determine whether you need to select this edge (at this time, the edges in the figure have been sorted from small to large in weight). The basis for judgment is whether the two vertices of the edge are connected. If they are connected, continue to the next one; if they are not connected, then choose to connect them.
Step 3: Loop the second step until all the vertices in the graph are in the same connected component, which means the minimum spanning tree is obtained.
Regarding the implementation of the permission graph, see the following example:
Graph:
package kruskal;public class Graph {final int max=100;/* * Vertex node*/public class VexNode{int adjvex;int data;}VexNode[] vexNodes;int[] thevexs;//Vertex set int[][] edges = new int[max][max];//Edge set/* * Create graph*/public void createGraph(Graph graph,int[][] A,int[] vexs) {thevexs=vexs;for (int i = 0; i < vexs.length; i++) {for (int j = 0; j < vexs.length; j++) {graph.edges[i][j] = A[i][j];}}}/* * Output graph*/public void printGraph(Graph graph) {for (int i = 0; i < graph.thevexs.length; i++) {for (int j = 0; j < graph.thevexs.length; j++) {//If there is no path, output/if (graph.edges[i][j]==-1) {System.out.printf("%4s","/");} else {System.out.printf("%4d",graph.edges[i][j]);}}System.out.println("/n");}}}algorithm:
package kruskal;public class KruSkal {public class Edge{int start;int end;int weight;}public void SortEdge(Edge[] E,int e) {Edge temp;int j;for (int i = 0; i < e; i++) {temp=E[i];j=i-1;while (j>=0&&temp.weight<E[j].weight) {E[j+1] = E[j];j--;}E[j+1] = temp;}}public KruSkal(Graph graph) {int i,j,u1,v1,sn1,sn2,k;int[] vset = new int[100];Edge[] E = new Edge[100];k=0;for (i=0;i<graph.thevexs.length;i++) {for (j=0;j<=i;j++) {E[k] = new Edge();if (graph.edges[i][j]>0) {E[k].start=i;E[k].end=j;E[k].weight=graph.edges[i][j];k++;}}}SortEdge(E, k);for (i=0;i<graph.thevexs.length;i++) {vset[i]=i;}k=1;j=0;while (k<graph.thevexs.length) {u1=E[j].start;v1=E[j].end;sn1=vset[u1];sn2=vset[v1];if (sn1!=sn2) {System.out.printf("(%d,%d), weight: %d",u1,v1,E[j].weight);System.out.println("/n");k++;for (i=0;i<graph.thevexs.length;i++) {if (vset[i]==sn2) {vset[i]=sn1;}}}j++;}}}Test class:
package kruskal;public class Test {public static void main(String[] args) {int[] vexs = {0,1,2,3,4};int[][] A = {{0,1,3,4,7},{1,0,2,-1,-1},{3,2,0,5,8},{4,-1,5,0,6},{7,-1,8,6,0}};Graph graph = new Graph();graph.createGraph(graph, A, vexs);graph.printGraph(graph);KruSkal kruSkal = new KruSkal(graph);}}Summarize
The above is the entire content of this article about the code example of the Java language to implement the Cruzkal algorithm based on undirected authorized graphs. I hope it will be helpful to everyone. If you have any questions, please leave a message at any time. The editor will try his best to answer you.