TOPOLOGICAL SORT OF A GRAPH

TOPOLOGICAL SORT OF A GRAPH

The following code shows the implementation of  TOPOLOGICAL SORT.

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

Program for sorting the elements using topological sort

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

#include<iostream.h>

#include<conio.h>

#define MAX 20

class TOPOLOGY

{

 private:

int Q[MAX];

 public:

int front,rear,G[MAX][MAX];

TOPOLOGY();

int Build_Graph();

void Display(int);

void Insert_Q(int vertex);

int Delete_Q();

int Compute_Indeg(int node,int n);

};

TOPOLOGY::TOPOLOGY()

{

 front=-1;

 rear=-1;

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

  for(int j=0;j<MAX;j++)

   G[i][j]=0;

}

int TOPOLOGY::Build_Graph()

{

 int i,n,edges,V1,V2;

 cout<<"Enter number of vertices : ";

 cin>>n;

 cout<<"\n Enter the total number of edges ";

 cin>>edges;

 for(i=1;i<=edges;i++)

 {

cout<<"Enter edge "<<i<<"(-99 -99 to quit): ";

cin>>V1;

cin>>V2;

if((V1==-99) && (V2==-99))

break;

if( V1 > n || V2 > n)

{

cout<<"Error!!!\n";

break;

}

if( V1 <=0 || V2 <=0)

{

cout<<"Error!!!\n";

break;

}

else

G[V1][V2]=1;

}

return n;

}

void TOPOLOGY::Insert_Q(int vertex)

{

if (rear==MAX-1)

cout<<"Queue Overflow\n";

else

{

if (front==-1) /*Empty Queue condition*/

front=0;

rear=rear+1;

Q[rear] = vertex;/* Insering node into the Q*/

}

}

int TOPOLOGY::Delete_Q()

{

int item;

if (front == -1 || front > rear)

{

cout<<"Queue Underflow\n";

return -1;

}

else

{

item=Q[front];

front=front+1;

return item;

}

}

int TOPOLOGY::Compute_Indeg(int node,int n)

{

int v1,indeg_count=0;

for(v1=1;v1<=n;v1++)

if( G[v1][node] == 1 )//checking for incoming edge

indeg_count++;

return indeg_count++;

}

void TOPOLOGY::Display(int n)

{

int V1,V2;

for(V1=1;V1<=n;V1++)

{

for(V2=1;V2<=n;V2++)

cout<<" "<<G[V1][V2];

cout<<"\n";

}

}

void main()

{

int i,j=0,k,n;

TOPOLOGY obj;

int b[MAX],indegree[MAX];

clrscr();

n=obj.Build_Graph();

cout<<"The adjacency matrix is :\n";

obj.Display(n);

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

{

indegree[i]=obj.Compute_Indeg(i,n);

if( indegree[i]==0 )

obj.Insert_Q(i);

}

while(obj.front<=obj.rear)

{

k=obj.Delete_Q();

b[j++]=k;

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

{

if( obj.G[k][i]==1 )

{

obj.G[k][i]=0;

indegree[i]=indegree[i]-1;

if(indegree[i]==0)

obj.Insert_Q(i);

}

}

}

cout<<"The result of after topological sorting is ...\n";

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

cout<<"  "<<b[i];

cout<<endl;

getch();

}

If there is an y problem in understanding the code,please inform me so that i can help you.Good day.

DJISKTRA'S ALGORITHM : SHORTEST PATH ALGORITHM

DJISKTRA'S ALGORITHM : SHORTEST PATH ALGORITHM

This algorithm is used to find shortest distance between a starting vertex and an ending vertex.Following code explains the concept:

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

This program finds the shortest path using Dijkstra’s algorithm using

Priority queue

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

#include<iostream.h>

#include<conio.h>

#define member 1

#define nomember 0

#define infinity 999

#define MAX 10

class SP

{

private:

int G[MAX][MAX],Q[MAX];

public:

int front,rear,n;

void Build_Graph();

void dikstra(int,int);

void insert_Q(int);

int Delete_Q(int);

};

void SP::Build_Graph()

{

int i,j,V1,V2;

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

{

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

{

cout<<"\n Enter the edge of V"<<i<<" to V"<<j<<": ";

cin>>G[i][j]; //read the wt of the edge

}

cout<<"\n";

}

}

void SP::insert_Q(int index)

{

Q[index]=1;//node with smallest path is inserted

}

int SP::Delete_Q(int i)

{

 if(Q[i]==1)//smallest path node

return i;

 return infinity;//if it is not a smallest path node

}

void SP::dikstra(int src,int dest)

{

int small,dist[10],current,start,new1;

int temp,i;

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

{

Q[i]=0;

dist[i]=infinity;

}

Q[src]=1;//starting from source vertex

dist[src]=0;//initial distance is zero

current=src; //consider source node as current node

while(current!=dest)//while not reaching to dest

{

small=infinity;

start=dist[current];//start from the current node

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

{

if(Q[i]==0)

{

new1=start+G[current][i];

if(new1<dist[i])

dist[i]=new1;

if(dist[i]<small)//finding the smallest dist

{                //from current node

small=dist[i];

temp=i;        //mark it

}

}

}

/*Priority Q is maintained for

stroing the nodes of smallest distances

from the source vertex */

current=temp;//smallest node number

insert_Q(current);//inserted in the priority Q

}

}

void main()

{

   int src,dest,path_node,k;

   SP obj;

   clrscr();

   cout<<"\n Program for shortest path algorithm using priority Queue";

   cout<<"\n Enter the number of vertices: ";

   cin>>obj.n;

   obj.Build_Graph();

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

   cin>>src;

   cout<<"\n Enter the destination: ";

   cin>>dest;

   obj.dikstra(src,dest);

   cout<<"\n The Shortest path is ...\n";

   obj.front=1;obj.rear=obj.n;

   while(obj.front<=obj.rear)

    {

         path_node=obj.Delete_Q(obj.front);

         if(path_node!=infinity)

                    cout<<"    "<<path_node;//printing smallest path

          obj.front++;

    }

    getch();

}

If you have any problem in understanding the code,kindly comment and notify me and i will get back to you as soon as possible.

ADJACENCY LIST REPRESENTATION OF A GRAPH AND BREADTH FIRST TRAVERSAL(BFS)

ADJACENCY LIST REPRESENTATION OF A GRAPH AND BREADTH FIRST TRAVERSAL(BFS) USING TEMPLATES

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

A program to create a Graph. The graph is represented using

Adjacency List and traversing the graph in Breadth First Search

Order.

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

#include<iostream.h>

#include <conio.h>

#include <stdlib.h>

#define     MAX      10

#define TRUE 1

#define FALSE 0

template <class T>

class Lgraph

{

private:

typedef struct Gnode

{

T vertex;

struct Gnode *next;

}node;

node *head[MAX];

int visited[MAX];

T Queue[MAX];

int front,rear;

public:

void init();

void create();

void bfs(T);

};

template <class T>

void Lgraph<T>::init()

{

int V1;

for ( V1 = 0; V1 < MAX; V1++)

visited[V1] = FALSE;

front = rear = -1;

for ( V1 = 0; V1 < MAX; V1++)

head[V1] = NULL;

}

/*

--------------------------------------------------------------------------

The create function

It creates the graph using adjacency list

It is called By main

--------------------------------------------------------------------------

*/

template <class T>

void Lgraph<T>::create()

{

T V1, V2;

char ans='y';

node *New,*first;

cout<<"\n\nEnter the vertices no. beginning with 0";

do

{

cout<<"\nEnter the Edge of a graph \n";

cin>>V1>>V2;

// creating link from V1 to V2

New = new node;

if ( New == NULL )

cout<<"Insufficient Memory\n";

New -> vertex = V2;

New -> next = NULL;

first = head[V1];

if ( first == NULL )

head[V1] = New;

else

{

while ( first -> next != NULL )

first = first-> next;

first -> next = New;

}

// creating link from V2 to V1

New = new node;

if ( New == NULL )

cout<<"Insufficient Memory\n";

New -> vertex = V1;

New -> next = NULL;

first = head[V2];

if ( first == NULL )

head[V2] = New;

else

{

while ( first -> next != NULL )

first = first-> next;

first -> next = New;

}

cout<<"\nWant to add more edges?(y/n)";

ans=getche();

}while(ans=='y');

}

/*

--------------------------------------------------------------------------

The bfs Function

It displays the graph in breadth first search manner

Input:Any vertex V1

It is called by main

--------------------------------------------------------------------------

*/

template <class T>

void Lgraph<T>::bfs(T V1)

{

T i;

node *first;

Queue[++rear] = V1;

while ( front != rear)

{

i = Queue[++front];

if ( visited[i] == FALSE )

{

cout<<endl<<i;

visited[i] = TRUE;

}

first = head[i];

while ( first != NULL )

{

if ( visited[first->vertex] == FALSE )

Queue[++rear] = first->vertex;

first = first -> next;

}

}

}

/*

--------------------------------------------------------------------------

The main function

--------------------------------------------------------------------------

*/

void main ( )

{

// Local declarations

char ans;

Lgraph <int> gr;

int V1;

gr.init();

gr.create();

clrscr();

cout<<"Enter the Vertex from which you want to traverse :";

cin>>V1;

cout<<"The Breadth First Search of the Graph is \n";

gr.bfs(V1);

getch();

}

If you have any query regarding the code,please notify me so that i can help you at my best.Good day.

IMPLEMENTATION OF KRUSKAL'S ALGORITHM

IMPLEMENTATION OF KRUSKAL'S ALGORITHM

It is on of the algorithms to find MST(minimum spanning tree) of a graph.Just keep the following two steps in mind regarding Kruskal's  algorithm:

1. Start from the edge having lowest cost and then select the edge having next lowest possible cost.If many edges have the same weight,you can select any one of them and then again from them and so on.
2. But during the first step,Keep in mind that you don't form any loop i.e. closed path.

The following code illustrates the concept:

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

Implementation of Kruskal's Algorithm

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

#include<iostream.h>

#define INFINITY 999

template <class T>

class KRUSKAL

{

 private:

typedef struct Graph

{

          int v1;

  int v2;

  T cost;

}GR;

GR G[20];

 public:

int tot_edges,tot_nodes;

void create();

void spanning_tree();

void get_input();

int Minimum(int);

};

int Find(int v2,int parent[])

{

 while(parent[v2]!=v2)

 {

v2=parent[v2];

 }

 return v2;

}

void Union(int i,int j,int parent[])

{

 if(i<j)

parent[j]=i;

 else

parent[i]=j;

}

template <class T>

void KRUSKAL<T>::get_input()

{

 cout<<"\n Enter Total number of nodes: ";

 cin>>tot_nodes;

 cout<<"\n Enter Total number of edges: ";

 cin>>tot_edges;

}

template <class T>

void KRUSKAL<T>::create()

{

 for(int k=0;k<tot_edges;k++)

 {

cout<<"\n Enter Edge in (V1 V2)form ";

cin>>G[k].v1>>G[k].v2;

cout<<"\n Enter Corresponding Cost ";

cin>>G[k].cost;

 }

}

template <class T>

int KRUSKAL<T>::Minimum(int n)

{

 int i,small,pos;

 small=INFINITY;

 pos=-1;

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

 {

if(G[i].cost<small)

{

small=G[i].cost;

pos=i;

}

 }

 return pos;

}

template <class T>

void KRUSKAL<T>::spanning_tree()

{

int count,k,v1,v2,i,j,tree[10][10],pos,parent[10];

T sum;

count=0;

k=0;

sum=0;

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

parent[i]=i;

while(count!=tot_nodes-1)

{

pos=Minimum(tot_edges);//finding the minimum cost edge

if(pos==-1)//Perhaps no node in the graph

break;

v1=G[pos].v1;

v2=G[pos].v2;

i=Find(v1,parent);

j=Find(v2,parent);

if(i!=j)

{

tree[k][0]=v1;//storing the minimum edege in array tree[]

tree[k][1]=v2;

k++;

count++;

sum+=G[pos].cost;//accumulating the total cost of MST

Union(i,j,parent);

}

G[pos].cost=INFINITY;

}

if(count==tot_nodes-1)

{

cout<<"\n Spanning tree is..."<<endl;

cout<<"\n------------------------"<<endl;

for(i=0;i<tot_nodes-1;i++)

{

cout<<"["<<tree[i][0];

cout<<" - ";

cout<<tree[i][1]<<"]"<<endl;

}

cout<<"\n------------------------"<<endl;

cout<<"Cost of Spanning Tree is = "<<sum<<endl;

}

else

{

cout<<"There is no Spanning Tree"<<endl;

}

}

void main()

{

 KRUSKAL <int> obj;

 cout<<"\n\t Graph Creation ";

 obj.get_input();

 obj.create();

 obj.spanning_tree();

}

Test this code and i hope it will be clear otherwise feel free to ask.Good day.

DEPTH FIRST TRAVERSAL/SEARCH

DEPTH FIRST TRAVERSAL/SEARCH (C++ CODE):

#include<iostream.h>
#include<conio.h>
class graph
{
public :
struct node
 {
 int data;
 node *next;
 }*head[20];
  graph()
 {
top=-1;front=-1;rear=-1;}
int front,rear,n,top,stack[20],queue[20];
void create();
void dfs();
void bfs();
void insert(int t)
 {
rear++;
queue[rear]=t;
 }
int deleteq()
 {
int t;
front++;
t=queue[front];
return t;
 }
int pop()
 {
int t;
  t=stack[top];
  top--;
  return t;
 }
 void push(int t)
 {
  top++;
  stack[top]=t;
 }
};
void graph :: bfs()
{
int num,sv,i,visited[20];
node *t;
cout<<"\n\nEnter starting vertex : ";
cin>>sv;
insert(sv);
for(i=0;i<=n;i++)
{
visited[i]=0;
}
cout<<"\n\nBFS traversal is  :\n";
while(front<rear)
{
num=deleteq();
if(visited[num]==0)
{
cout<<"   "<<num;
visited[num]=1;
}
t=head[num];
while(t!=NULL)
{
if(visited[t->data]==0)
insert(t->data);
t=t->next;
}
cout<<"\n";
      }
}

void graph :: dfs()
{
int num,sv,i,visited[20];
node *t;
cout<<"\n\nEnter the starting vertex :";
cin>>sv;
push(sv);
for(i=1;i<=n;i++)
{
visited[i]=0;
}
cout<<"\n\nThe DFS traversal is :";
while(top!=-1)
{
num=pop();
if(visited[num]==0)
{
cout<<"\t"<<num;
visited[num]=1;
}
t=head[num];
while(t!=NULL)
{
if(visited[t->data]==0)
push(t->data);
t=t->next;
}
      }
   }

void graph :: create()
{
int i,j;
char ans;
node *t,*t1,*p;
cout<<"\nEnter the number of nodes :";
cin>>n;
for(i=1;i<=n;i++)
{
head[i]=NULL;}
do
{
 t=new node;
 t->next=NULL;
 cout<<"\nEnter 2 vertices :";
 cin>>i>>j;
 t->data=j;
 if(head[i]==NULL)
{
 t1=new node;
 t1->next=NULL;
 t1->data=i;
 head[i]=t1;
}
 p=head[i];
 while(p->next!=NULL)
{
 p=p->next;
}
 p->next=t;
 cout<<"\nDo you want to continue (Y/N) :";
 cin>>ans;
}while(ans=='y'||ans=='Y');
}
void main()
{
int ch;
char choice;
clrscr();
graph obj;
obj.create();
do
{
cout<<"\n1.DFS \n2.BFS\n\tEnter your choice :";
cin>>ch;
switch(ch)
{
case 1:
obj.dfs();
break;
case 2:
obj.bfs();
break;
      default:
break;
}
cout<<"\nDo you want to continue (Y/N) :";
cin>>choice;
}while(choice=='y'||choice=='Y');
getch();

}

PRIM's ALGORITHM

PRIM's ALGORITHM (C++):

/*TITLE: TO IMPLEMENT PRIMS ALGORITHM.


#include<iostream.h>
#include<stdio.h>
#include<conio.h>
int weight[20][20],visited[20],d[20],p[20];
int v,e;

void creategraph()
{
int i,j,a,b,w;
cout<<"\nEnter number of vertices";
cin>>v;
cout<<"\nEnter number of edges";
cin>>e;
for(i=1;i<=v;i++)
  for(j=1;j<=v;j++)
    weight[i][j]=0;
for(i=1;i<=v;i++)
{
  p[i]=visited[i]=0;
  d[i]=32767;
}
for(i=1;i<=e;i++)
{
  cout<<"\nEnter edge a,b and weight w:";
  cin>>a>>b>>w;
  weight[a][b]=weight[b][a]=w;
}
}

void prim()
{
int current,totalvisited,mincost,i;
current=1;d[current]=0;
totalvisited=1;
visited[current]=1;
while(totalvisited!=v)
{
  for(i=1;i<=v;i++)
  {
    if(weight[current][i]!=0)
      if(visited[i]==0)
    if(d[i]>weight[current][i])
    {
      d[i]=weight[current][i];
      p[i]=current;
    }
  }
  mincost=32767;
  for(i=1;i<=v;i++)
  {
    if(visited[i]==0)
      if(d[i]<mincost)
      {
    mincost=d[i];
    current=i;
      }
  }
  visited[current]=1;
  totalvisited++;
}
mincost=0;
for(i=1;i<=v;i++)
  mincost+=d[i];
  cout<<"\nMinimum cost="<<mincost;

}

main()
{
clrscr();
creategraph();
prim();
getch();
}