Djecstra

#include<iostream>

#define INFINITY 999

using namespace std;

class Dijkstra{

private:

int adjMatrix[15][15];

int predecessor[15],distance[15];

bool mark[15]; //keep track of visited node

int source;

int numOfVertices;

public:

/*

* Function read() reads No of vertices, Adjacency Matrix and source

* Matrix from the user. The number of vertices must be greather than

* zero, all members of Adjacency Matrix must be postive as distances

* are always positive. The source vertex must also be positive from 0

* to noOfVertices - 1

*/

void read();

/*

* Function initialize initializes all the data members at the begining of

* the execution. The distance between source to source is zero and all other

* distances between source and vertices are infinity. The mark is initialized

* to false and predecessor is initialized to -1

*/

void initialize();

/*

* Function getClosestUnmarkedNode returns the node which is nearest from the

* Predecessor marked node. If the node is already marked as visited, then it search

* for another node.

*/

int getClosestUnmarkedNode();

/*

* Function calculateDistance calculates the minimum distances from the source node to

* Other node.

*/

void calculateDistance();

/*

* Function output prints the results

*/

void output();

void printPath(int);

};

void Dijkstra::read(){

cout<<"Enter the number of vertices of the graph(should be > 0)\n";

cin>>numOfVertices;

while(numOfVertices <= 0) {

cout<<"Enter the number of vertices of the graph(should be > 0)\n";

cin>>numOfVertices;

}

cout<<"Enter the adjacency matrix for the graph\n";

cout<<"To enter infinity enter "<<INFINITY<<endl;

for(int i=0;i<numOfVertices;i++) {

cout<<"Enter the (+ve)weights for the row "<<i<<endl;

for(int j=0;j<numOfVertices;j++) {

cin>>adjMatrix[i][j];

while(adjMatrix[i][j]<0) {

cout<<"Weights should be +ve. Enter the weight again\n";

cin>>adjMatrix[i][j];

}

}

}

cout<<"Enter the source vertex\n";

cin>>source;

while((source<0) && (source>numOfVertices-1)) {

cout<<"Source vertex should be between 0 and"<<numOfVertices-1<<endl;

cout<<"Enter the source vertex again\n";

cin>>source;

}

}

void Dijkstra::initialize(){

for(int i=0;i<numOfVertices;i++) {

mark[i] = false;

predecessor[i] = -1;

distance[i] = INFINITY;

}

distance[source]= 0;

}

int Dijkstra::getClosestUnmarkedNode(){

int minDistance = INFINITY;

int closestUnmarkedNode;

for(int i=0;i<numOfVertices;i++) {

if((!mark[i]) && (minDistance >= distance[i])) {

minDistance = distance[i];

closestUnmarkedNode = i;

}

}

return closestUnmarkedNode;

}

void Dijkstra::calculateDistance(){

initialize();

int minDistance = INFINITY;

int closestUnmarkedNode;

int count = 0;

while(count < numOfVertices) {

closestUnmarkedNode = getClosestUnmarkedNode();

mark[closestUnmarkedNode] = true;

for(int i=0;i<numOfVertices;i++) {

if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0)) {

if(distance[i] > distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]) {

distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i];

predecessor[i] = closestUnmarkedNode;

}

}

}

count++;

}

}

void Dijkstra::printPath(int node){

if(node == source)

cout<<(char)(node + 97)<<"..";

else if(predecessor[node] == -1)

cout<<"No path from “<<source<<”to "<<(char)(node + 97)<<endl;

else {

printPath(predecessor[node]);

cout<<(char) (node + 97)<<"..";

}

}

void Dijkstra::output(){

for(int i=0;i<numOfVertices;i++) {

if(i == source)

cout<<(char)(source + 97)<<".."<<source;

else

printPath(i);

cout<<"->"<<distance[i]<<endl;

}

}

int main(){

Dijkstra G;

G.read();

G.calculateDistance();

G.output();

return 0;

}

BFS

#include <iostream>

#include <ctime>

using namespace std;

/****************************************************************

Performs the Breadth-First Graph search for both directed and

undirected graphs. This algorithm explores all the findable nodes

in "layers".

@author Bibek Subedi

*****************************************************************/

/****************************************************************

Class Queue represent a Queue data structure which is First In

First Out [FIFO] structured. It has operations like Enqueue which

adds an element at the rear side and Dequeue which removes the

element from front.

*****************************************************************/

struct node {

int info;

node *next;

};

class Queue {

private:

node *front;

node *rear;

public:

Queue();

~Queue();

bool isEmpty();

void enqueue(int);

int dequeue();

void display();

};

void Queue::display(){

node *p = new node;

p = front;

if(front == NULL){

cout<<"\nNothing to Display\n";

}else{

while(p!=NULL){

cout<<endl<<p->info;

p = p->next;

}

}

}

Queue::Queue() {

front = NULL;

rear = NULL;

}

Queue::~Queue() {

delete front;

}

void Queue::enqueue(int data) {

node *temp = new node();

temp->info = data;

temp->next = NULL;

if(front == NULL){

front = temp;

}else{

rear->next = temp;

}

rear = temp;

}

int Queue::dequeue() {

node *temp = new node();

int value;

if(front == NULL){

cout<<"\nQueue is Emtpty\n";

}else{

temp = front;

value = temp->info;

front = front->next;

delete temp;

}

return value;

}

bool Queue::isEmpty() {

return (front == NULL);

}

/************************************************************

Class Graph represents a Graph [V,E] having vertices V and

edges E.

************************************************************/

class Graph {

private:

int n; /// n is the number of vertices in the graph

int **A; /// A stores the edges between two vertices

public:

Graph(int size = 2);

~Graph();

bool isConnected(int, int);

void addEdge(int u, int v);

void BFS(int);

};

Graph::Graph(int size) {

int i, j;

if (size < 2) n = 2;

else n = size;

A = new int*[n];

for (i = 0; i < n; ++i)

A[i] = new int[n];

for (i = 0; i < n; ++i)

for (j = 0; j < n; ++j)

A[i][j] = 0;

}

Graph::~Graph() {

for (int i = 0; i < n; ++i)

delete [] A[i];

delete [] A;

}

/******************************************************

Checks if two given vertices are connected by an edge

@param u vertex

@param v vertex

@return true if connected false if not connected

******************************************************/

bool Graph::isConnected(int u, int v) {

return (A[u-1][v-1] == 1);

}

/*****************************************************

adds an edge E to the graph G.

@param u vertex

@param v vertex

*****************************************************/

void Graph::addEdge(int u, int v) {

A[u-1][v-1] = A[v-1][u-1] = 1;

}

/*****************************************************

performs Breadth First Search

@param s initial vertex

*****************************************************/

void Graph::BFS(int s) {

Queue Q;

/** Keeps track of explored vertices */

bool *explored = new bool[n+1];

/** Initailized all vertices as unexplored */

for (int i = 1; i <= n; ++i)

explored[i] = false;

/** Push initial vertex to the queue */

Q.enqueue(s);

explored[s] = true; /** mark it as explored */

cout << "Breadth first Search starting from vertex ";

cout << s << ": " << endl;

/** Unless the queue is empty */

while (!Q.isEmpty()) {

/** Pop the vertex from the queue */

int v = Q.dequeue();

/** display the explored vertices */

cout << v << " ";

/** From the explored vertex v try to explore all the

connected vertices */

for (int w = 1; w <= n; ++w)

/** Explores the vertex w if it is connected to v

and and if it is unexplored */

if (isConnected(v, w) &&!explored[w]) {

/** adds the vertex w to the queue */

Q.enqueue(w);

/** marks the vertex w as visited */

explored[w] = true;

}

}

cout << endl;

delete [] explored;

}

int main() {

/** Creates a graph with 12 vertices */

Graph g(12);

/** Adds edges to the graph */

g.addEdge(1, 2); g.addEdge(1, 3);

g.addEdge(2, 4); g.addEdge(3, 4);

g.addEdge(3, 6); g.addEdge(4,7);

g.addEdge(5, 6); g.addEdge(5, 7);

clock_t t1;

t1 = clock();

/** Explores all vertices findable from vertex 1 */

g.BFS(1);

float diff = (double)(clock() - t1)/CLOCKS_PER_SEC;

cout <<endl<< "The time taken for Breadth first search: "<< diff << endl;

}

DFS

#include <iostream>

#include <ctime>

#include <malloc.h>

using namespace std;

struct node{

int info;

struct node *next;

};

class stack{

struct node *top;

public:

stack();

void push(int);

int pop();

bool isEmpty();

void display();

};

stack::stack(){

top = NULL;

}

void stack::push(int data){

node *p;

if((p=(node*)malloc(sizeof(node)))==NULL){

cout<<"Memory Exhausted";

exit(0);

}

p = new node;

p->info = data;

p->next = NULL;

if(top!=NULL){

p->next = top;

}

top = p;

}

int stack::pop(){

struct node *temp;

int value;

if(top==NULL){

cout<<"\nThe stack is Empty"<<endl;

}else{

temp = top;

top = top->next;

value = temp->info;

delete temp;

}

return value;

}

bool stack::isEmpty(){

return (top == NULL);

}

void stack::display(){

struct node *p = top;

if(top==NULL){

cout<<"\nNothing to Display\n";

}else{

cout<<"\nThe contents of Stack\n";

while(p!=NULL){

cout<<p->info<<endl;

p = p->next;

}

}

}

class Graph {

private:

int n;

int **A;

public:

Graph(int size = 2);

~Graph();

bool isConnected(int, int);

void addEdge(int x, int y);

void DFS(int, int);

};

Graph::Graph(int size) {

int i, j;

if (size < 2) n = 2;

else n = size;

A = new int*[n];

for (i = 0; i < n; ++i)

A[i] = new int[n];

for (i = 0; i < n; ++i)

for (j = 0; j < n; ++j)

A[i][j] = 0;

}

Graph::~Graph() {

for (int i = 0; i < n; ++i)

delete [] A[i];

delete [] A;

}

bool Graph::isConnected(int x, int y) {

return (A[x-1][y-1] == 1);

}

void Graph::addEdge(int x, int y) {

A[x-1][y-1] = A[y-1][x-1] = 1;

}

void Graph::DFS(int x, int required){

stack s;

bool *visited = new bool[n+1];

int i;

for(i = 0; i <= n; i++)

visited[i] = false;

s.push(x);

visited[x] = true;

if(x == required) return;

cout << "Depth first Search starting from vertex ";

cout << x << ": " << endl;

while(!s.isEmpty()){

int k = s.pop();

if(k == required) break;

cout<<k<<" ";

for (i = n; i >= 0; --i)

if (isConnected(k, i) &&!visited[i]) {

s.push(i);

visited[i] = true;

}

}

cout<<endl;

delete [] visited;

}

int main(){

Graph g(8);

g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(1, 4);

g.addEdge(2, 5); g.addEdge(2, 6); g.addEdge(4, 7);

g.addEdge(4, 8);

g.DFS(1, 4);

return 0;

}

Trees