Graph Traversal Algorithms For DBMS

When understanding the Database concepts, we will often encounter optimization problems related to database performance. Let’s understand one Graph Traversal Algorithms For DBMS and its solution.

Travelling salesman problem:

The Travelling Salesman Problem describes a salesman who must travel N cities. The order in which he visits the cities is not important, as long as he visits each one during his trip. Each city is connected to other close by cities. The effort for going from one city to another is defined by the distance between two cities. The salesman wants to keep the distance he travels as low as possible.

This problem can be represented in form of a graph, where the nodes represent the cities and edges represent the distance between any two cities.

undirected_graph

Minimum spanning tree:

Assume a graph where the nodes are numbered and all edges are given some weight. A minimum spanning tree (MST) is a subset of the edges of a graph that connects all the nodes with a minimum possible total edge weight. This tree represents the minimum possible cost of travelling all the nodes.

Prim’s algorithm :

In computer science, Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm creates this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

The logical steps of Prim’s algorithm are –

  1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.
  2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
  3. Repeat step 2 (until all vertices are in the tree).