Data Structure and Algorithm

/****************************************************
APPLICATION : Program to Simulate Deterministic Finite Automata (DFA)
CODED BY    : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE         : 2010 - December - 10
*****************************************************/

#include <iostream.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>

struct Node //Structure to represent a Node or Vertices of a Graph
{
char data[10];
struct Node *next,*head; //Pointers to next node and Start
struct Adjacent *adj; //Pointer to Adjacent node
};

struct Adjacent //Structure to represent Adjacent node of a Graph
{
char data;
struct Node *next;
struct Adjacent *adj; //Pointer for next Adjacent
};

Node *New,*top; //Global Variables for New node and Pointer to Top
void create()
{
New = new Node; //Create a node
New -> next = NULL;
New -> adj = NULL;
}

void CreateVertices(Node *&n,char *Item) //Function to Create a Vertices of a Graph
{
if(n == NULL) //if first node
  {
   n = new Node; //Create a node
   strcpy(n -> data,Item); //Insert Data
   n -> next = NULL;
   n -> adj = NULL;
   n -> head = n; //Initialize head
   top = n; //Update top
   return;
  }

create(); //Create a node
strcpy(New -> data,Item); //Insert Item
top -> next = New; //Assign new node to next of top
top = New; //Update top
}

void LinkVertices(Node *&n)
{
Adjacent *a,*ptr;
int inputSize;
char *inputString;
cout << "\nHow many inputs? ";
cin >> inputSize;
inputString = new char[inputSize];
cout << "\nEnter Input Alphabets : ";
for(int j = 0;j < inputSize;j++)
  cin >> inputString[j];

Node *temp = n -> head;
while(temp != NULL) //Until last
{
  int flag = 0,i = 0;
  char ch[10];
  do
   {
    cout << "\nEnter Transition (" << temp -> data <<  ", " << inputString[i] << ") : ";
    cin >> ch; //Scan Adjacent
    a = new Adjacent; //Create an Adjacent
    a -> data = inputString[i++]; //Insert Data
    a -> adj = NULL;
    a -> next = NULL;
    if(flag == 0) //if first Adjacent
     {
      temp -> adj = a;
      ptr = a;
      flag++; //Increase flag
     }

    else
     {
      ptr -> adj = a;
      ptr = a;
     }

   Node *tmp = n -> head;
   while(tmp != NULL)
    {
     if(strcmpi(tmp -> data,ch) == 0)
      a -> next = tmp;
     tmp = tmp -> next;
    }

   }while(i < inputSize);
   temp = temp -> next;
  }
}

char* CurrentState(Node *n,char *state, char input)
{
Node *temp = n -> head, *tmp;
Adjacent *a;
char nextState[10] = "";
while(temp != NULL)
  {
   if (strcmpi(temp -> data,state) == 0)
    {
     a = temp -> adj;
     while(a != NULL)
     {
      if (a -> data == input)
       {
    tmp = a -> next;
    strcpy(nextState,tmp -> data);
    return nextState;
       }
      a = a -> adj;
     }
    }
   temp = temp -> next;
  }
return nextState;
}

char* Transition(Node *n,char *state, char *inputString)
{
int len = strlen(inputString);
int i = 0;
char chrTemp;
while(i < len)
  {
   chrTemp = inputString[i++];
   strcpy(state,CurrentState(n,state,chrTemp));
   if (i != len)
   {
    chrTemp = inputString[i++];
    strcpy(state,CurrentState(n,state,chrTemp));
   }
  }
return state;
}

void display(Node *n)
{
if(n == NULL)
  {
   cout << "Nothing to Display.";
   return;
  }

Node *temp = n, *tmp;
Adjacent *a;
while(temp != NULL) //Until Last
  {
   cout << temp -> data << ' '; //Print first data
   a = temp -> adj; //go to adjacent node
   while(a != NULL) //Until last of adjacent
    {
     tmp = a -> next;
     cout << tmp -> data << ' '; //print adjacent
     a = a -> adj; //goto next adjacent
    }
   cout << endl;
   temp = temp -> next; //goto next Node
  }
}

int main()
{
int m;
char startState[10],finalState[10];
Node *nd = NULL;
cout << "How Many States? "; //Number of Nodes on a Graph
cin >> m;

cout << "\nState(s) Name : "; //Input the name of Vertices
for(int i = 0;i < m;i++)
  {
   char strBuf[15],strTemp[10];
   strcpy(strBuf,"Q");
   itoa(i,strTemp,10);
   strcat(strBuf, strTemp);
   strcat(strBuf, "\0");
   if (i == 0)
    strcpy(startState,strBuf);
   CreateVertices(nd,strBuf);
   cout << strBuf << " ";
  }

cout << "\n\nEnter Final State : ";
cin >> finalState;

LinkVertices(nd);
cout << "\nThe Transition Table is\n";
cout << "-----------------------\n";
display(nd);
cout << endl;
char inputString[50];
cout << endl << "Enter a String : ";
cin >> inputString;

char State[10];
strcpy(State,Transition(nd,startState,inputString));
if (strcmpi(State,finalState) == 0)
  cout << "\nString Accepted";
else
  cout << "\nInvalid String";
getch();
return 0;
}

OUTPUT

Let’s Check the DFA that accept all the strings that ends with 00

 

Download Original File

DFA.cpp

/****************************************
APPLICATION : Depth First Search (DFS)
CODED BY    : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE     : 2010 - October - 12
****************************************/

#include "iostream.h"
#include "conio.h"

struct Node //Structure to represent a Node or Vertices of a Graph
{
int status;
char data;
struct Node *next,*head; //Pointers to next node and Start
struct Adjacent *adj; //Pointer to Adjacent node
};

struct Adjacent //Structure to represent Adjacent node of a Graph
{
struct Node *next;
struct Adjacent *adj; //Pointer for next Adjacent
};

Node *New,*top; //Global Variables for New node and Pointer to Top
void create()
{
New = new Node; //Create a node
New -> status = false;
New -> next = NULL;
New -> adj = NULL;
}

void CreateVertices(Node *&n,char Item) //Function to Create a Vertices of a Graph
{
if(n == NULL) //if first node
  {
   n = new Node; //Create a node
   n -> data = Item; //Insert Data
   n -> status = false;
   n -> next = NULL;
   n -> adj = NULL;
   n -> head = n; //Initialize head
   top = n; //Update top
   return;
  }

create(); //Create a node
New -> data = Item; //Insert Item
top -> next = New; //Assign new node to next of top
top = New; //Update top
}

void LinkVertices(Node *&n)
{
Adjacent *a,*ptr;
cout << "\nEnter Link for each Vertices (0 as Last Input): ";
Node *temp = n -> head,*tmp;
while(temp != NULL) //Until last
{
  cout << "\nEnter Adjacents of " << temp -> data << " : ";
  int flag = 0;
  char ch;
  do
   {
    cin >> ch; //Scan Adjacent
    a = new Adjacent; //Create an Adjacent
    a -> adj = NULL;
    a -> next = NULL;
    if(flag == 0) //if first Adjacent
     {
      temp -> adj = a;
      ptr = a;
      flag++; //Increase flag
     }

    else
     {
      ptr -> adj = a;
      ptr = a;
     }

   tmp = n -> head; //from start
   while(tmp != NULL) //Until end
    {
     if(tmp -> data == ch) //if node found
      a -> next = tmp; //Link adjacent
     tmp = tmp -> next;
    }
   }while(ch != '0');
   temp = temp -> next;
  }
}

void DFS(Node *n,char Item)
{
int top = -1;
char stack[30]; //Create a Stack
stack[++top] = Item; //Push starting Item
cout << Item << ' ';
Node *temp,*tmp;
char ch = Item;

while(top >= 0) //until stack is empty
{
  temp = n;
  while(temp -> data != ch) //goto starting node
   temp = temp -> next;
  temp -> status = true; //update status

  Adjacent *a = temp -> adj;
  while(a -> adj != NULL)
   {
    tmp = a -> next;
    if(tmp -> status == false)
     {
      stack[++top] = tmp -> data; //save adjacents to stack
      tmp -> status = true; //update status
     }
    a = a -> adj; //goto next adjacent
   }

  ch = stack[top];
  if(top != 0)
   cout << stack[top] << ' '; //output top of stack
  --top;
}
}

int main()
{
int m;
char ch;
Node *nd = NULL;
cout << "How Many Vertices? "; //Number of Nodes on a Graph
cin >> m;

cout << "\nEnter Vertices Name : "; //Input the name of Vertices
for(int i = 0;i < m;i++)
  {
   cin >> ch;
   CreateVertices(nd,ch); //Create Vertices of a Graph
  }

LinkVertices(nd); //Link the Vertices of a Graph
cout << "\nFind nodes reachable from : ";
cin >> ch;
cout << "\nThe nodes reachable from " << ch << " : ";
DFS(nd,ch); //Depth First Traversal
getch();
}

OUTPUT

How Many Vertices? 9

Enter Vertices Name : A B C D E F G J K

Enter Link for each Vertices (0 as Last Input):
Enter Adjacents of A : F C B 0

Enter Adjacents of B : G C 0

Enter Adjacents of C : F 0

Enter Adjacents of D : C 0

Enter Adjacents of E : D C J 0

Enter Adjacents of F : D 0

Enter Adjacents of G : C E 0

Enter Adjacents of J : D K 0

Enter Adjacents of K : E G 0

Find node reachable from : J

The nodes reachable from J : J K G C F E D

Download Original File

Depth First Search (DFS).cpp

/****************************************
APPLICATION : Breadth First Search (BFS)
CODED BY    : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE     : 2010 - October - 13
****************************************/

#include "iostream.h"
#include "conio.h"

struct Node //Structure to represent a Node or Vertices of a Graph
{
int status;
char data;
struct Node *next,*head; //Pointers to next node and Start
struct Adjacent *adj; //Pointer to Adjacent node
};

struct Adjacent //Structure to represent Adjacent node of a Graph
{
struct Node *next;
struct Adjacent *adj; //Pointer for next Adjacent
};

Node *New,*top; //Global Variables for New node and Pointer to Top
void create()
{
New = new Node; //Create a node
New -> status = false;
New -> next = NULL;
New -> adj = NULL;
}

void CreateVertices(Node *&n,char Item) //Function to Create a Vertices of a Graph
{
if(n == NULL) //if first node
  {
   n = new Node; //Create a node
   n -> data = Item; //Insert Data
   n -> status = false;
   n -> next = NULL;
   n -> adj = NULL;
   n -> head = n; //Initialize head
   top = n; //Update top
   return;
  }

create(); //Create a node
New -> data = Item; //Insert Item
top -> next = New; //Assign new node to next of top
top = New; //Update top
}

void LinkVertices(Node *&n)
{
Adjacent *a,*ptr;
cout << "\nEnter Link for each Vertices (0 as Last Input): ";
Node *temp = n -> head,*tmp;
while(temp != NULL) //Until last
{
  cout << "\nEnter Adjacents of " << temp -> data << " : ";
  int flag = 0;
  char ch;
  do
   {
    cin >> ch; //Scan Adjacent
    a = new Adjacent; //Create an Adjacent
    a -> adj = NULL;
    a -> next = NULL;
    if(flag == 0) //if first Adjacent
     {
      temp -> adj = a;
      ptr = a;
      flag++; //Increase flag
     }

    else
     {
      ptr -> adj = a;
      ptr = a;
     }

   tmp = n -> head; //from start
   while(tmp != NULL) //Until end
    {
     if(tmp -> data == ch) //if node found
      a -> next = tmp; //Link adjacent
     tmp = tmp -> next;
    }
   }while(ch != '0');
   temp = temp -> next;
  }
}

void BFS(Node *n,char from,char to) //Breadth First Search
{
char Queue[30],Origin[30];
int Front = -1,Rear = -1,k = -1,flag;
char ch = from;
Node *temp,*tmp;
Queue[++Rear] = from;
++Front;
Origin[++k] = '#';
while(ch != to)
{
  temp = n;
  flag = false; //suppose that there is no path between two nodes
  while(temp != NULL)
  {
   if(temp -> data == ch)
    {
     flag = true; //there is a path
     temp -> status = true; //update status
     break;
    }
   temp = temp -> next;
  }

  if(flag == false)
    break;

  Adjacent *a = temp -> adj; //goto Adjacent node
  while(a -> adj != NULL)
  {
   tmp = a -> next;
   if(tmp -> status == false)
    {
     Queue[++Rear] = tmp -> data; //Add to Queue
     Origin[++k] = temp -> data; //Save Origin
     tmp -> status = true; //update status
    }
   a = a -> adj;
  }
  ch = Queue[++Front];
}

//Backtrack and Print
if(flag != false)
{
  ch = to;
  flag = false;
  for(int j = (k+1);j > 1;j--)
   {
    if(flag == true)
     ch = Origin[j];
    char c = Origin[j - 1];

    if(c != ch)
    {
     temp = n;
     while(temp -> data != c)
      temp = temp -> next;
     Adjacent *a = temp -> adj;
     while(a -> adj != NULL)
      {
       flag = false;
       tmp = a -> next;
       if(tmp -> data == ch)
       {
        cout << tmp -> data << " <- ";
        flag = true;
        break;
       }
       a = a -> adj;
      }
    }
   }
  cout << from;
}

else
  cout << "There is no path between " << from << " to " << to;
}

int main()
{
int m;
char c,ch;
Node *nd = NULL;
cout << "How Many Vertices? "; //Number of Nodes on a Graph
cin >> m;

cout << "\nEnter Vertices Name : "; //Input the name of Vertices
for(int i = 0;i < m;i++)
  {
   cin >> ch;
   CreateVertices(nd,ch); //Create Vertices of a Graph
  }

LinkVertices(nd); //Link the Vertices of a Graph
cout << "\nFind Minimum Path From : ";
cin >> c;
cout << "To : ";
cin >> ch;
cout << " \nThe Minimum Path from (" << c << " to " << ch << ") : ";
BFS(nd,c,ch);
getch();
}

OUTPUT

How Many Vertices? 9

Enter Vertices Name : A B C D E F G J K

Enter Link for each Vertices (0 as Last Input):
Enter Adjacents of A : F C B 0

Enter Adjacents of B : G C 0

Enter Adjacents of C : F 0

Enter Adjacents of D : C 0

Enter Adjacents of E : D C J 0

Enter Adjacents of F : D 0

Enter Adjacents of G : C E 0

Enter Adjacents of J : D K 0

Enter Adjacents of K : E G 0

Find Minimum Path From : A
To : J

The Minimum Path from (A to J) : J <- E <- G <- B <- A

Download Original File

Breadth First Search (BFS)

How Many Vertices? 9

Enter Vertices Name : A B C D E F G J K

Enter Link for each Vertices (0 as Last Input):
Enter Adjacents of A : F C B 0

Enter Adjacents of B : G C 0

Enter Adjacents of C : F 0

Enter Adjacents of D : C 0

Enter Adjacents of E : D C J 0

Enter Adjacents of F : D 0

Enter Adjacents of G : C E 0

Enter Adjacents of J : D K 0

Enter Adjacents of K : E G 0

Graph Created : The Adjacency Matrix is
-----------------------------------------------------------
A F C B
B G C
C F
D C
E D C J
G C E
J D K
K E G

Download Original File

Graph.cpp

/*******************************************************
APPLICATION : Program to create Adjacency Matrix (using Linked List)
CODED BY    : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE     : 2010 - October - 12
********************************************************/

#include "iostream.h"
#include "conio.h"

struct Node //Structure to represent a Node or Vertices of a Graph
{
char data;
struct Node *next,*head; //Pointers to next node and Start
struct Adjacent *adj; //Pointer to Adjacent node
};

struct Adjacent //Structure to represent Adjacent node of a Graph
{
char data;
struct Adjacent *adj; //Pointer for next Adjacent
};

Node *New,*top; //Global Variables for New node and Pointer to Top
void create()
{
New = new Node; //Create a node
New -> next = NULL;
New -> adj = NULL;
}

void CreateVertices(Node *&n,char Item) //Function to Create a Vertices of a Graph
{
if(n == NULL) //if first node
  {
   n = new Node; //Create a node
   n -> data = Item; //Insert Data
   n -> next = NULL;
   n -> adj = NULL;
   n -> head = n; //Initialize head
   top = n; //Update top
   return;
  }

create(); //Create a node
New -> data = Item; //Insert Item
top -> next = New; //Assign new node to next of top
top = New; //Update top
}

void LinkVertices(Node *&n)
{
Adjacent *a,*ptr;
cout << "\nEnter Link for each Vertices (0 at Last Input): ";
Node *temp = n -> head;
while(temp != NULL) //Until last
{
  cout << "\nEnter Adjacents of " << temp -> data << " : ";
  int flag = 0;
  char ch = ' ';
  do
   {
    cin >> ch; //Scan Adjacent
    a = new Adjacent; //Create an Adjacent
    a -> data = ch; //Insert Data
    a -> adj = NULL;
    if(flag == 0) //if first Adjacent
     {
      temp -> adj = a;
      ptr = a;
      flag++; //Increase flag
     }

    else
     {
      ptr -> adj = a;
      ptr = a;
     }
   }while(ch != '0');
   temp = temp -> next;
  }
}

void display(Node *n)
{
if(n == NULL)
  {
   cout << "Graph is Empty.";
   return;
  }

Node *temp = n;
Adjacent *a;
while(temp != NULL) //Until Last
  {
   cout << temp -> data << ' '; //Print first data
   a = temp -> adj; //go to adjacent node
   while(a -> adj != NULL) //Until last of adjacent
    {
     cout << a -> data << ' '; //print adjacent
     a = a -> adj; //goto next adjacent
    }
   cout << endl;
   temp = temp -> next; //goto next Node
  }
}

int main()
{
int m;
char ch;
Node *nd = NULL;
cout << "How Many Vertices? "; //Number of Nodes on a Graph
cin >> m;

cout << "\nEnter Vertices Name : "; //Input the name of Vertices
for(int i = 0;i < m;i++)
  {
   cin >> ch;
   CreateVertices(nd,ch);
  }

LinkVertices(nd);
cout << "\nThe Adjacency Matrix is\n";
cout << "-----------------------\n";
display(nd);
getch();
}

OUTPUT

How Many Vertices? 9

Enter Vertices Name : A B C D E F G J K

Enter Link for each Vertices (0 as Last Input):
Enter Adjacents of A : F C B 0

Enter Adjacents of B : G C 0

Enter Adjacents of C : F 0

Enter Adjacents of D : C 0

Enter Adjacents of E : D C J 0

Enter Adjacents of F : D 0

Enter Adjacents of G : C E 0

Enter Adjacents of J : D K 0

Enter Adjacents of K : E G 0

The Adjacency Matrix is
-----------------------
A F C B
B G C
C F
D C
E D C J
G C E
J D K
K E G

Download Original File

Adjacency.cpp

/***************************************************************************
--> Suppose G is a simple directed graph with m nodes, and suppose the nodes of G have been ordered and are called v1,v2,...,vm. Then the adjacency matrix, A = (aij) of the graph G is the m*m matrix defined as follows:

                  aij = {1 if vi is adjacent to vj, that is, if there is an edge (vi,vj)
                        {0 otherwise

such a matrix A , which contains entries of only 0 and 1, is called a Bit or Boolean Matrix.
****************************************************************************/

#include "iostream.h"
#include "conio.h"

struct Adjacency_Matrix
{
char Vertices[30]; //Name of Vertices
int Adjacent[30][30]; //Adjacency Matrix
};

int main()
{
int m;
Adjacency_Matrix a;
cout << "How Many Vertices? "; //Number of Nodes on a Graph
cin >> m;

cout << "\nEnter Vertices Name : "; //Input the name of Vertices
for(int i = 0;i < m;i++)
  cin >> a.Vertices[i];

cout << "\nEnter Boolean Matrix :\n"; //Input Boolean Matrix
for(int i = 0;i < m;i++)
  for(int j = 0;j < m;j++)
   cin >> a.Adjacent[i][j];

cout << endl << "\nThe Adjacency List\n"; //Display Adjacency Matrix
cout << "------------------\n";
for(int i = 0;i < m;i++)
  {
   cout << a.Vertices[i];
   for(int j = 0;j < m;j++)
    {
     if(a.Adjacent[i][j] == 1)
      cout << ' ' << a.Vertices[j];
    }
   cout << endl;
  }

getch();
}

How Many Vertices? 4

Enter Vertices Name : X Y Z W

Enter Boolean Matrix :
0 0 0 1
1 0 1 1
1 0 0 1
0 0 1 0

The Adjacency List
----------------------
X W
Y X Z W
Z X W
W Z