Graph Theory and Algorithms Implementation

About Graph Theory and Algorithms Implementation

Graphs are used to solve many real-life problems. Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a vertex(or node). Each node is a structure and contains information like person id, name, gender, locale etc. We are going to start our discussion by looking at the basic terms of graph theory and them jump on to discuss graph theory related algorithms and then implement those with c++. Following are the types of algorithms we are going to discuss in this course. In this Course we shall Implement many Importants Algorithms like DFS ,BFS, Kruskals, PRims and Dijastra's Algorithms. We shall understand how to find path in a given graph ,Directed Graphs ,Spanning Trees ,Minimum spanning trees etc. Minimal Spanning Tree A spanning tree whose sum of weight (or length) of all its edges is less than all other possible spanning tree of graph G is known as a minimal spanning tree or minimum cost spanning tree. To implement the minimum cost-spanning tree, the following two methods are used −

Prim’s Algorithm

Kruskal’s Algorithm Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a