How to implement the minimum spanning tree algorithm of graphs using java
How to use java to implement the minimum spanning tree algorithm of a graph
Concept introduction:
Minimum Spanning Tree (MST) refers to a weighted In a directed or undirected graph, find a tree that contains all the vertices in the graph and has the smallest sum of weights. There are many minimum spanning tree algorithms, the two most classic algorithms are Prim's algorithm and Kruskal's algorithm.
Prim algorithm:
Prim algorithm is a point-based greedy algorithm that starts from a vertex and then gradually expands until the entire minimum spanning tree is generated. The following is a sample code for implementing Prim's algorithm using java:
import java.util.Arrays; public class PrimAlgorithm { // 表示无穷大 private static final int INF = Integer.MAX_VALUE; public static void primMST(int[][] graph) { int vertices = graph.length; // 创建一个数组用来保存最小生成树的顶点 int[] parent = new int[vertices]; // 创建一个数组用来保存每个顶点与最小生成树的最小权值 int[] key = new int[vertices]; // 创建一个数组用来标记顶点是否已经加入最小生成树 boolean[] mstSet = new boolean[vertices]; // 初始化key数组和mstSet数组的值 Arrays.fill(key, INF); Arrays.fill(mstSet, false); //将第一个顶点加入最小生成树 key[0] = 0; parent[0] = -1; for (int count = 0; count < vertices - 1; count++) { // 选择key值最小的顶点 int minKey = getMinKey(key, mstSet); mstSet[minKey] = true; // 更新与该顶点相邻的顶点的key值 for (int v = 0; v < vertices; v++) { if (graph[minKey][v] != 0 && !mstSet[v] && graph[minKey][v] < key[v]) { parent[v] = minKey; key[v] = graph[minKey][v]; } } } // 输出最小生成树 printMST(parent, graph); } // 获得key值最小的顶点 private static int getMinKey(int[] key, boolean[] mstSet) { int minKey = INF, minIndex = -1; for (int v = 0; v < key.length; v++) { if (!mstSet[v] && key[v] < minKey) { minKey = key[v]; minIndex = v; } } return minIndex; } // 输出最小生成树 private static void printMST(int[] parent, int[][] graph) { System.out.println("Edge Weight"); for (int i = 1; i < graph.length; i++) { System.out.println(parent[i] + " - " + i + " " + graph[i][parent[i]]); } } public static void main(String[] args) { int[][] graph = {{0, 2, 0, 6, 0}, {2, 0, 3, 8, 5}, {0, 3, 0, 0, 7}, {6, 8, 0, 0, 9}, {0, 5, 7, 9, 0}}; primMST(graph); } }
Kruskal algorithm:
Kruskal algorithm is a greedy algorithm based on edges. It selects edges in order from small to large in weight and only selects edges. No loop edges are generated until the entire minimum spanning tree is generated. The following is a sample code for using java to implement Kruskal's algorithm:
import java.util.*; class Edge implements Comparable<Edge> { int src, dest, weight; public int compareTo(Edge compareEdge) { return this.weight - compareEdge.weight; } } class KruskalAlgorithm { public List<Edge> kruskalMST(List<Edge> edges, int vertices) { List<Edge> result = new ArrayList<>(); Collections.sort(edges); int[] parent = new int[vertices]; for (int i = 0; i < vertices; i++) { parent[i] = i; } int count = 0, i = 0; while (count < vertices - 1) { Edge currentEdge = edges.get(i); int x = find(parent, currentEdge.src); int y = find(parent, currentEdge.dest); if (x != y) { result.add(currentEdge); union(parent, x, y); count++; } i++; } return result; } private int find(int[] parent, int vertex) { if (parent[vertex] != vertex) { parent[vertex] = find(parent, parent[vertex]); } return parent[vertex]; } private void union(int[] parent, int x, int y) { int xSet = find(parent, x); int ySet = find(parent, y); parent[xSet] = ySet; } public static void main(String[] args) { int vertices = 4; List<Edge> edges = new ArrayList<>(); edges.add(new Edge(0, 1, 10)); edges.add(new Edge(0, 2, 6)); edges.add(new Edge(0, 3, 5)); edges.add(new Edge(1, 3, 15)); edges.add(new Edge(2, 3, 4)); KruskalAlgorithm kruskal = new KruskalAlgorithm(); List<Edge> result = kruskal.kruskalMST(edges, vertices); System.out.println("Edge Weight"); for (Edge edge : result) { System.out.println(edge.src + " - " + edge.dest + " " + edge.weight); } } }
The above is a sample code for using java to implement Prim's algorithm and Kruskal's algorithm. They are both classic methods for implementing the minimum spanning tree algorithm of graphs. By learning and understanding these codes, you can better understand and master how to use Java to implement the minimum spanning tree algorithm of graphs.
The above is the detailed content of How to implement the minimum spanning tree algorithm of graphs using java. For more information, please follow other related articles on the PHP Chinese website!

Java is platform-independent because of its "write once, run everywhere" design philosophy, which relies on Java virtual machines (JVMs) and bytecode. 1) Java code is compiled into bytecode, interpreted by the JVM or compiled on the fly locally. 2) Pay attention to library dependencies, performance differences and environment configuration. 3) Using standard libraries, cross-platform testing and version management is the best practice to ensure platform independence.

Java'splatformindependenceisnotsimple;itinvolvescomplexities.1)JVMcompatibilitymustbeensuredacrossplatforms.2)Nativelibrariesandsystemcallsneedcarefulhandling.3)Dependenciesandlibrariesrequirecross-platformcompatibility.4)Performanceoptimizationacros

Java'splatformindependencebenefitswebapplicationsbyallowingcodetorunonanysystemwithaJVM,simplifyingdeploymentandscaling.Itenables:1)easydeploymentacrossdifferentservers,2)seamlessscalingacrosscloudplatforms,and3)consistentdevelopmenttodeploymentproce

TheJVMistheruntimeenvironmentforexecutingJavabytecode,crucialforJava's"writeonce,runanywhere"capability.Itmanagesmemory,executesthreads,andensuressecurity,makingitessentialforJavadeveloperstounderstandforefficientandrobustapplicationdevelop

Javaremainsatopchoicefordevelopersduetoitsplatformindependence,object-orienteddesign,strongtyping,automaticmemorymanagement,andcomprehensivestandardlibrary.ThesefeaturesmakeJavaversatileandpowerful,suitableforawiderangeofapplications,despitesomechall

Java'splatformindependencemeansdeveloperscanwritecodeonceandrunitonanydevicewithoutrecompiling.ThisisachievedthroughtheJavaVirtualMachine(JVM),whichtranslatesbytecodeintomachine-specificinstructions,allowinguniversalcompatibilityacrossplatforms.Howev

To set up the JVM, you need to follow the following steps: 1) Download and install the JDK, 2) Set environment variables, 3) Verify the installation, 4) Set the IDE, 5) Test the runner program. Setting up a JVM is not just about making it work, it also involves optimizing memory allocation, garbage collection, performance tuning, and error handling to ensure optimal operation.

ToensureJavaplatformindependence,followthesesteps:1)CompileandrunyourapplicationonmultipleplatformsusingdifferentOSandJVMversions.2)UtilizeCI/CDpipelineslikeJenkinsorGitHubActionsforautomatedcross-platformtesting.3)Usecross-platformtestingframeworkss


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

SublimeText3 Mac version
God-level code editing software (SublimeText3)

mPDF
mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

Notepad++7.3.1
Easy-to-use and free code editor

WebStorm Mac version
Useful JavaScript development tools
