Network topology is an important procedure of networking in which devices (nodes) are interconnected in a network using network paths such as ethernet. Topology also describes the process of data transfer between network connections. Thus, the importance of computer network topology is increasing significantly in most of the routine activities of organizations due to the increasing utilization of electronic devices such as computers. With the growing significance, the network must be arranged in such a way that the required network topology costs minimal to develop. In this article, we implement two greedy algorithms to solve a computer network topology using the minimum spanning tree problem. The results of both algorithms show consistency. A comparative analysis of time complexity is described.
In this project, we consider the problem of designing a small computer network in an office.
The objective is to generate the network in such a way that all the computers in the office are connected by making Ethernet lines. Ethernet is a Local Area Network (LAN) technology that can be used as a protocol to connect multiple systems over a LAN network connection. Apart from LAN, it is also used in Metropolitan Area Network (MAN), Wide Area Network (WAN) network, etc.
Construction costs are mainly decided based on the distance of the connections and some constraints due to physical boundaries. We use a minimum spanning tree of the network to study the minimum cost to connect all the computers.
The goal 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, Prim's Minimum Spanning Tree, and finally, we will compare the performance of the algorithms considering the complexity of time.
The greedy algorithm is widely used in optimization problems. The following greedy algorithm heuristically solves the problem by making locally optimal choices at each stage of the problem. Using the local optimal approach, study a global solution to the problem. Greedy algorithms do not guarantee a global solution but generate an optimal solution locally that is approximated to a global solution within a reasonable length of time.
Greedy algorithms find Prim's and Kruskal's algorithms to find the smallest span tree, the Huffman encoding to compress the data, and the shortest path (distance) from one vertex in the graph to all the other. Very successful on several issues, such as Dijkstra's algorithm. To solve the problem of computer network topology, we implemented Prim's and Kruskal's algorithms to investigate the minimum spanning tree of weighted networks.