Implimentation of Kruskal's algorithm

Abstract

Graph theory is a branch of mathematics that examines the . properties of graphs. It has a relatively long history in classical mathematics. There are many applications of graph theory to some areas of physics, chemistry, communication science, computer technology, electrical and civil engineering, architecture, operational research, genetics, psychology, sociology, economics, anthropology, and linguistics. In graph theory, the problem was first solved by Leonhard Euler (1707 — 1783). He has used graphs to solve the famous K6énigsberg Bridge problem. In the history of mathematics, it is one of the problems in graph theory to be formally discussed. In mathematics and computer science, graph theory studies the properties of graphs. Typically, a graph is design as a set of dots (the vertices) connected by links (the edges). A graph with a number assigned to each edge is called a weighted graph, are used to model road networks, communication networks, computer systems, etc. In these cases the weights could be distance, cost, or time, etc. The minimum spanning tree problem is the simplest and one of the most central models in the field of combinatorial problem. Two “greedy” algorithms are available in graph theory, which find a minimum spanning tree for connected weighted graph. One such algorithm is called the Kruskal’s Algorithm and the other is called the Prim’s Algorithm. Our purpose is to implement the Kruskal’s algorithm by writing a suitable computer program using the Microsoft Visual Basic. The first step of the program is to enter the relevant values of the problem. The second step is to find the minimum spanning tree and calculate the minimum cost, distance or time according to the request. This program can be used to solve many problems in industry such as highways, telephone lines, television cables and computer networks etc.