Posts

C++: Breadth First Search program using Adjacency Matrix

Image
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, sometimes referred to as a 'search key'[1]) and explores the neighbor nodes first, before moving to the next level neighbours. [wikipedia]

//This program uses Adjacency Matrix #include<iostream>
#include<queue>
#include<limits>
#include<vector>

class Graph
{
int vertexCount;
  //WHITE means Undiscovered, GRAY means Discovered, BLACK menas Processed
enumclass Color{ WHITE, GRAY, BLACK };

constint imax = std::numeric_limits<int>::max();

struct Vertex
  {
int id;
Color color;
size_t distance;

Vertex(constint vertex, Color clr, int imax) : id(vertex),
                                                      color(clr),
                                                      distance(imax)
                                                      {};
  };
  std::vector< std::vector<bool> > adjMatrix; //adja…

C++: Depth First Search program using Adjacency Matrix (Graph Algorithm)

Image
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.[wikipedia]

It explores edges out of the most recently discovered vertex v that still has unexplored edges leaving it. Once all of v's edges have been explored, the search "backtracks" to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the original source vertex. If any undiscovered vertices remain, then depth-first search selects one of them as a new source, and it repeats the search from that source. The algorithm repeats this entire process until it has discovered every vertex. [Introduction to Algorithm(CLSR)]

#include<iostream>
#include<vector>

class Graph
{
int vertexCount; //no of Vertices
enumclass Color { WHITE, GRAY, BLACK };

struct Vertex
  {
int id;
  Color color;
  Vertex(int vertex, Color clr) : id(vertex), color(clr) {}
  };
  std::vector< std::vector<bo…

C++: Binary Tree using STL

Image
In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. 

SPOJ Problem - CPTTRN6 - Character Patterns (Act 6)

This is a problem from SPOJ. We have to print a character pattern according to the input given.

We have input

33 1 2 1 4 4 1 2 2 5 3 2

SPOJ Problem - CPTTRN5 - Character Patterns (Act 5)

This is a problem from SPOJ. We have to print a character pattern according to the input given.

We have input 

33 1 24 4 12 5 2

Popular Posts

C++: Breadth First Search program using Adjacency Matrix

Check if the String is Palindrome (C++ & Java Program)

C++: Depth First Search program using Adjacency Matrix (Graph Algorithm)