C++ program to implement AVL Tree

An AVL tree is another balanced binary search tree. Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time. Addition and deletion operations also […]

Read More

C++ Program to Implement Floyd Warshall Algorithm

Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices, though it does not return details of the paths themselves. […]

Read More

Program to implement Binary Search Tree C++

A Binary Search Tree is a Binary Tree data structure ( a tree in which each node has at most two children ) which has the following properties: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys […]

Read More

Program to implement Depth First Search C++

What is Depth First Search? Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. A version of depth-first search was […]

Read More

Minimum Spanning Tree using Prim’s Algorithm

What is Spanning Tree? The idea behind minimum spanning trees is simple: given a graph with weighted edges, find a tree of edges with the minimum total weight. What is a spanning tree? A graph that satisfies these three properties: connected, acyclic, and consisting of |V| – 1 edges. (In fact, any two of the three […]

Read More

Program Shortest Path using Kruskal algorithm in cpp

The following program illustrates Kruskal algorithm in cpp to find Shortest Path.   #include <iostream.h> #include <graphics.h> #include <string.h> #include <stdlib.h> #include <conio.h> #define MAX_VERTICES 10 #define MAX_EDGES 15 /*************************************************************************/ //——————————- Vertex ——————————// /*************************************************************************/ class Vertex { public: int x; int y; int label; private: char Label[5]; public: Vertex( ) { } ~Vertex( ) { […]

Read More

Program for Shortest path using Dijkstra Algorithm in c++

The following program illustrates the Shortest Path using Dijkstra Algorithm in C++:   #include <iostream.h> #include <conio.h> #define MAX_NODE 50 struct node{ int vertex; int weight; node *next; }; struct fringe_node{ int vertex; fringe_node *next; }; node *adj[MAX_NODE]; //For storing Adjacency list of nodes.int totNodes; //No. of Nodes in Graph.constint UNSEEN=1,FRINGE=2,INTREE=3; //status of node.int status[MAX_NODE];//status […]

Read More

Program to implement Breadth First Search C++

What is Breadth First Search? Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph) and explores the neighbor nodes first, before moving to the next level neighbors. Compare BFS with the equivalent, but more memory-efficient iterative […]

Read More