Feb 18, 2022
Application of Prims’ and Kruskals’ algorithms towards Network Topology
A network topology is a significant procedure of a network where devices (nodes) are interconnected in the network using network lines such as ethernet. The topology also describes the process of transferring data between the connection of the network. Thus, the importance of computer network topology is significantly increasing in most of the organization’s regular activities due to the growing utilization of electronic devices such as computers. With the growing significance, the network should be set up in such a way so that the topology of the network is required minimal cost to develop. In this article, we implement two greedy algorithms to solve a computer network topology by using the minimum spanning tree problem. The results from both algorithms show consistency. A comparative analysis of time complexity is explained.
In this project, we consider the problem of designing a small network of computers in an office . The objective is to generate the network in such a way so that all the computers in the office get connected to each other by constructing Ethernet lines. Ethernet is Local Area Network (LAN) technology that can be used as a protocol to connect multiple systems on the LAN network connection. Apart from LAN, it is also used in Metropolitan Area Network (MAN), Wide Area Network (WAN) network, etc. Each possible link (the connection between two computers in the office) and the associated construction cost are illustrated in the following figure :
The construction costs are primarily decided based on the distance of the links and some restrictions due to physical boundaries. We leverage a minimum spanning tree of the network to investigate the minimal cost to connect all the computers.
The objective of this project is to implement a greedy algorithm to find the minimum spanning tree. We will implement some standard greedy algorithms such as Kruskal’s minimum spanning tree, and Prim’s Minimum Spanning Tree, and finally compare the performance of the algorithms considering time complexity.
The greedy algorithm is a massively used algorithm in optimization problems. The greedy algorithm follows heuristically solves the problem by making locally optimal choices at each stage of the problem. Using the local optimal approach, it investigates a global solution for the problem. Greedy algorithms do not guarantee a global solution but generate a locally optimal solution that is approximate to a global solution with a reasonable time duration. Greedy algorithms are quite successful in some problems, such as Prim’s algorithm and Kruskal’s algorithm to find a minimum spanning tree, Huffman encoding to compress data, or Dijkstra’s algorithm to find the shortest path (distance) from one vertex to all other vertices in a graph. To solve our computer network topology problem, we implemented Prim’s and Kruskal’s algorithms to investigate the minimum spanning tree for a weighted network.
Prim’s algorithm is one of the famous greedy algorithms that find the minimum spanning tree of a graph. A graph is fed into the algorithm and it finds the minimum spanning tree i.e. finds a subset of the edges of that graph that form a tree including all the vertices and has minimum weights among all the generated trees. The steps in Prim’s algorithms are followed:
Kruskal’s algorithm is another greedy algorithm that finds the minimum spanning tree of an undirected connected graph. It finds an edge of the least possible weight that connects any two trees in the forest. It follows the following steps:
We implement both algorithms on our data set. An adjacency matrix is formed from the given network and it is used as input for both algorithms. The adjacency matrix is shown in the following figure.
The results of using both algorithms are listed below in table 1 prim’s algorithm and in table Kruskal’s algorithm. Figure 2 shows the minimum spanning tree.
Both algorithms produce identical results where the minimum cost to the computer network is 13. Additionally, the generated minimum spanning tree is also the same for both methods.
In this article, we implement two greedy algorithms to solve a computer network topology by using a minimum spanning tree problem. The results from both algorithms show consistency. We explored that both the greedy algorithms produce identical results.
Your membership fee will directly support and inspire Mohammad Masum and thousands of other writers you read. You’ll also get full access to every story on Medium — https://masum-math8065.medium.com/membership
Schedule a DDIChat Session in Data Science / AI / ML / DL:
Apply to be a DDIChat Expert here.
Ways to work with DDI: https://datadriveninvestor.com/collaborate
Visit us at https://www.datadriveninvestor.com/
Gain Access to Expert View — Subscribe to DDI Intel: https://ddintel.datadriveninvestor.com/
empowerment through data, knowledge, and expertise. subscribe to DDIntel at https://ddintel.datadriveninvestor.com
Box Tech Blog
Machine Learning Enthusiast | Student of Life |
Text to speech
Greedy Algorithms for Computer Network Topology | by Masum – DataDrivenInvestor