DS programs

program 1:
/* stack ADT*/
#include<iostream>
#include<stdlib.h>
using namespace std;

class queue
{
              int qary[5];
              int rear, front;
      public:
              queue()
                {
                     rear=-1;
                     front=-1;
                }
              void insert(int x)
               {
                   if(rear >  4)
                    {
                       cout <<"queue is full";
                       front=rear=-1;
                       return;
                    }
                    qary[++rear]=x;
                    //cout <<"inserted" <<x;
               }
               void delet()
               {
                   if(front==rear)
                     {
                         cout <<"queue is empty";
                         return;
                     }
                     cout <<"\n"<<"Deleted element is: " <<qary[++front];
                }
              void display()
               {
                   if(rear==front)
                     {
                          cout <<" queue is empty";
                          return;
                     }
                   cout<<"\n"<<"Elements in queue are: "<<"\n";
                   for(int i=front+1;i<=rear;i++)
                   cout <<qary[i]<<" ";
               }
};

int main()
{
      int ch;
      queue qu;
      qu.insert(15);
      qu.insert(25);
      qu.insert(35);
      qu.display();
      qu.delet();
      qu.display();
       return (0);
}

Output:
Elements in queue are:
15 25 35
Deleted element is: 15
Elements in queue are:
25 35

/* queue ADT*/

#include<iostream>
#include<stdlib.h>
using namespace std;
class stack
{
             int ary[5];
             int top;
      public:
             stack()
              {
                top=-1;
               }
             void push(int x)
              {
                 if(top >  4)
                       {
                           cout <<"stack is full";
                           return;
                       }
                 ary[++top]=x;
                 //cout <<"inserted" <<x;
               }
             void pop()
               {
                  if(top <0)
                   {
                         cout<<"stack is empty";
                         return;
                    }
                    cout<<"\n"<<"Deleted element : "<<ary[top--];
                }
             void display()
               {
                   if(top<0)
                    {
                            cout <<" stack is empty";
                            return;
                    }
                     cout<<"\n"<<"Elements in the stack:"<<"\n";
                    for(int i=top;i>=0;i--)
                    cout <<ary[i] <<" ";
                }
};

main()
{
     stack st;
     st.push(15);
     st.push(25);
     st.push(35);
     st.display();
     st.pop();
     st.display();
return (0);
}
Output:
Elements in the stack:
35 25 15
Deleted element : 35
Elements in the stack:
25 15

program 2:

/* Program to convert infix to postfix*/
#include <iostream>
#include<string.h>
using namespace std;
class Stack
      {
public:
char opd[20];
char opr[20];
int Max;
int rtop;
int dtop;
Stack()
 {
   Max = 20;
   dtop =-1;
   rtop=-1;
}
int od_Empty();
int or_Empty();
int orFull();
int odFull();
char odpop();
char orpop();
void odpush(char Element);
void orpush(char Element);
void convert(char infx[]);
void postfx();
    };
char Stack :: odpop()
    {
if(!od_Empty())
  {
     return(opd[dtop--]);
  }
    }
char Stack :: orpop()
      {
if(!or_Empty())
 {
    return(opr[rtop--]);
                }
     }
int Stack :: od_Empty()
    {
if(dtop ==-1)
return 1;
else
return 0;
   }
int Stack :: or_Empty()
    {
if(rtop ==-1)
return 1;
else
return 0;
   }
int Stack :: odFull()
   {
if(dtop == Max-1)
return 1;
else
return 0;
   }
int Stack :: orFull()
   {
if(rtop == Max-1)
return 1;
else
return 0;
   }
void Stack :: odpush(char Ele)
 {
    if(!odFull())
    {
    if(Ele!='('&&Ele!='['&&Ele!='{')
      {
        opd[++dtop] = Ele;
      } 
    }
 }
void Stack :: orpush(char Element)
    {
         if(!orFull())
           {
               opr[++rtop] = Element;
           }
    }
void Stack :: convert(char infx1[])
    {
             char chr;
            int n=strlen(infx1);
            for(int i=0; i<n; i++)
              {
                 if(isalpha(infx1[i]))
                        odpush(infx1[i]);
                 else if ((infx1[i]==')')||(infx1[i]==']')||(infx1[i]=='}'))
                        {
                          odpush(orpop());
                          opr[rtop--]='\0';
                        } 
                 else
                        orpush(infx1[i]);
               }
                 for(int x=0;x<=rtop;x++)
                   {
                        chr=orpop();
                        if(chr!='('&& chr!='{'&& chr!='[')
                           odpush(chr);
                   }       
                for(int x=0;x<=dtop;x++)
                    {
                        cout<<opd[x];
                    }
    }
int main()
    {
       Stack S;
       char infx[]="{[(A*C)+D]/E}";
       cout<<"Infix Expression:"<<infx;
       cout<<"\n"<<"Postfix Conversion :";
       S.convert(infx);
       return 0;
    }
Output:
Infix Expression: {[(A*C)+D]/E}
Postfix Conversion : AC*D+E/
  
program 4:

/*program to check for nested Parenthesis balance*/
#include<iostream>
#include<stdlib.h>
using  namespace std;
class  Node
{
public:
   char data;
   Node *next;
};
class StkList
  {
            Node *Head;
            public:
              StkList()
            {
                        Head=NULL;
              }
            void  push(char Ndata);
            char  pop();
            int  isMatchingPair(char ch1, char ch2);
            void checkPB(char exp[]);
  };
void StkList:: push(char Ndata)
{
            Node *Newnode = new Node();
            Newnode->data=Ndata;
            Newnode->next=Head;
            Head=Newnode;
}
char StkList::pop()
  {
    char val;
            if(Head==NULL)
      {
            return '\0';
              }
            else
              {
                        val=Head->data;
                        Head=Head->next;
                        return val;
                        } 
  }
int StkList::isMatchingPair(char ch1, char ch2)
{
if (ch1 == '(' && ch2 == ')')
            return 1;
else if (ch1 == '{' && ch2 == '}')
            return 1;
else if (ch1 == '[' && ch2 == ']')
            return 1;
else
            return 0;
}
void StkList:: checkPB(char exp[])
{
   int i = 0;
 
  while (exp[i])
   {
                        if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
                        push(exp[i]);

                        if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
                        {
                                   
                                    if (Head == NULL)
                                        {
                                                cout<<"\n" <<" NOT Balanced "; 
                                                break;
                                        }
                           else if ( !isMatchingPair(pop(), exp[i]) )  //if NOT matching
                                                            {
                                                             cout<<"\n" <<" NOT Balanced "; 
                                                    break;
                                                   }
                }
            i++;
  }
             
if (Head == NULL)
            cout<<"\n" <<" Balanced ";      
else
            cout<<"\n"<<"Not Balanced "; 
}

int main()
{
StkList Sobj;    
char exp[100] = "{()}[]";
cout<<"Given expression is:  "<<exp;
Sobj.checkPB(exp);
return 0;
}

Output:
Given expression is:  {()}[]
Balanced

program 6(c):

/* Program to search for an element in the list: */
#include <iostream>
using namespace std;

class Node
   {
            public :
            int data;
            Node *link;
   };
class Llist
  {
            private:
            Node *Head, *Tail;
            public:
            Llist()
             {
                        Head = NULL;
                        Tail=NULL;
             }
             ~Llist();
            void Create(int value);
            void Search(int val);
            void Display();
  };
  Llist::~Llist()
  {
            Node *Temp;
            while(Head != NULL)
               {
                  Temp = Head;
                  Head = Head->link;
                  delete Temp;
               }
  }
void Llist::Create(int value)
  {
            Node *Newnode;
            Newnode = new Node;
            Newnode->data=value;
            Newnode->link = NULL;
          if(Head==NULL)
           {
             Head=Newnode;
              Tail=Newnode;
            }
                        else
                        {
                         Tail->link=Newnode;
                         Tail=Newnode;
                }
  }
void Llist::Search(int  val)
  {
            Node  *temp = Head;
            int  pos=0;
            char  flag='f';
           if(temp == NULL)
               cout << "The List is empty";
            else
              {
                while((temp != NULL) && (flag=='f'))
                   {
                        pos++;    
                        if(temp->data==val)
                           {
                                     flag='t';
                                      break;
                           }
                        temp = temp->link;
                   }
              if(flag=='t') 
                cout << val<<"  is found at position  :  "<<pos<<endl;
              else
                cout <<val<<"  is Not in the list"<<endl;
              }
  }
int main()
  {
            Llist L1;
            L1.Create(35);
            L1.Create(45);
            L1.Create(55);
            L1.Create(65);
            L1.Search(50);
            L1.Search(65);
            return 0;
  }
Output:
50  is Not in the list
65  is found at position  :  4

program 6(d):
/* program to sort the elements in linked list using singly linked list  */

#include <iostream>
using namespace std;

class   Node
   {
                public :
                int   data;
                Node *  link;
   };
class   Llist
  {
                private:
                Node *Head;
                public:
                Llist()
                 {
                   Head = NULL;
                 }
                 ~Llist();
                void  Create(int value);
            Node* sortList(Node* headptr);
                void Display();
  };
  Llist::~Llist()
  {
                Node *Temp;
                while(Head != NULL)
                   {
                      Temp = Head;
                  Head = Head->link;
                  delete Temp;
                   }
  }

void Llist::Create(int value)
  {
                Node *Newnode;
                Newnode = new Node;
                Newnode->data=value;
                Newnode->link = NULL;
          if(Head==NULL)
           {
             Head=Newnode;
                }
                else
                 {
                   Newnode->link=Head;
                   Head=Newnode;
                 }
  }
Node*  Llist :: sortList(Node* headptr)
{
    int  temp1;
    Node *   curr=NULL;
    Node *   curnext=NULL;
    for(bool  didSwap = true;  didSwap;  )
         {
            didSwap = false;
            for(curr = headptr;    curr->link != NULL;    curr = curr->link)
                  {
                    curnext=curr->link;
                    if(curr->data > curnext->data)
                                {
                            temp1 = curr->data;
                            curr->data = curnext->data;
                            curnext->data = temp1;
                            didSwap = true;
                        }
              }
        }
    return headptr;
}


void Llist::Display()
  {
                Node *temp = Head;
                if(temp == NULL)
                   cout << "Empty List";
                else
                  {
                     temp=sortList(Head);
                     while(temp != NULL)
                       {
                                cout << temp->data << "\t";
                                temp = temp->link;
                       }
              }
            cout << endl;
   }
int main()
  {
    Llist   L1;
    L1.Create(50);
    L1.Create(45);
    L1.Create(55);
    L1.Create(35);
    cout<<"After sorting the list is :"<<"\n";
    L1.Display();
   return 0;
  }

program 7(d):
/* soting using DLL */
#include <iostream>
using namespace std;

class DLL_Node
{
   public:
   int data;
   DLL_Node *prev, *next;
   DLL_Node()
     {
       prev = next = NULL;
     }
};
class DList
  {
            private:
            DLL_Node *Head;
            public:
            DList()
             {
                        Head = NULL;
             }
             ~DList();
            void Create(int value);
            DLL_Node* sortList(DLL_Node* headptr);
            void Display();
  };
  DList::~DList()
  {
            DLL_Node *Temp;
            while(Head != NULL)
               {
                  Temp = Head;
                  Head = Head->next;
                  delete Temp;
               }
  }

void DList::Create(int value)
  {
            DLL_Node *Newnode;
            Newnode = new DLL_Node;
            Newnode->data=value;
            Newnode->next = NULL;
            Newnode->prev = NULL;
          if(Head==NULL)
           {
             Head=Newnode;
           }
            else
             {
               Head->prev=Newnode;
               Newnode->next=Head;
               Head=Newnode;
             }
  }
DLL_Node*  DList :: sortList(DLL_Node* headptr)
{
    int  temp;
    DLL_Node*  curr=NULL;
    DLL_Node*  curtafter=NULL;
    for(bool  didSwap = true;  didSwap;  )
         {
            didSwap = false;
            for(curr = headptr;    curr->next != NULL;    curr = curr->next)
              {
                    curtafter=curr->next;
                    if(curr->data > curtafter->data)
                        {
                            temp = curr->data;
                            curr->data = curtafter->data;
                            curtafter->data = temp;
                            didSwap = true;
                        }
              }
        }
    return headptr;
}


void DList::Display()
  {
            DLL_Node  *temp = Head;
            if(temp == NULL)
               cout << "The List is empty";
            else
              {
                 temp=sortList(Head);   
     while(temp != NULL)
                   {
                        cout << temp->data << "\t";
                        temp = temp->next;
                   }
              }
            cout << endl;
   }
int main()
  {
            DList L1;
            L1.Create(65);
            L1.Create(35);
            L1.Create(55);
            L1.Create(45);
            cout<<"After sorting the list is :"<<"\n";
            L1.Display();
            return 0;
  }

Output:
After sorting the list is :
35           45           55           65

program 14:

#include <iostream>
using   namespace   std;
class   Node
 {
    int   key;
    Node*   left;
    Node*  right;
  public:
    Node() 
      {
        key=-1;
        left=NULL;
        right=NULL;
     }
        void   setKey(int  aKey)
               {
                   key = aKey;
              }
        void   setLeft(Node*  aLeft) 
             {
                 left = aLeft;
            }
    void   setRight(Node* aRight)
            {
                right = aRight;
            }
    int   Key()
             {
                return key;
            }
    Node*   Left()
            {
                 return left;
            }
    Node*  Right()
           {
                return right;
           }
};
class  Tree
 {
     Node*  root;
public:
     Tree();
     ~Tree();
     Node*  Root ()
           {
                return  root;
            }
     void   addNode(int  key);
     void   inOrder(Node* n);
     void   preOrder(Node* n);
     void   postOrder(Node* n);
private:
     void   addNode(int key, Node* leaf);
     void   freeNode(Node* leaf);
};
Tree::Tree()  
          {
            root = NULL;
          }
Tree::~Tree()  
          {
             freeNode(root);
          }
void Tree::freeNode(Node* leaf)
         {
              if ( leaf != NULL )
                {
                     freeNode(leaf->Left());
                     freeNode(leaf->Right());
                   delete leaf;
                }
         }

void   Tree::addNode(int   key)
  {
                                 // Adding at the root when No elements in the tree      
     if ( root == NULL )
     {
        cout << "add root node ... "<< key << endl;
        Node*   n = new Node();
        n->setKey(key);
        root = n;
     }
   else
     {
       cout << "add other node ... " << key << endl;
       addNode(key, root);
     }
}

void   Tree::addNode(int   key, Node*   leaf)
   {
    if ( key <= leaf->Key() )
     {
       if ( leaf->Left() != NULL )
          addNode(key, leaf->Left());
       else
        {
          Node* n = new Node();
          n->setKey(key);
          leaf->setLeft(n);
        }
    }
    else
           {
              if ( leaf->Right() != NULL )
                   addNode(key, leaf->Right());
              else
                   {
                        Node*   n = new Node();
                        n->setKey(key);
                        leaf->setRight(n);
                   }
           }
}

void Tree::inOrder(Node* n)
  {
    if ( n )
     {
       inOrder(n->Left());
       cout << n->Key() << " ";
       inOrder(n->Right());
    }
}

void Tree::preOrder(Node* n)
  {
    if ( n )
     {
       cout << n->Key() << " ";
       preOrder(n->Left());
       preOrder(n->Right());
    }
}

void Tree::postOrder(Node* n)
 {
    if ( n )
     {
       postOrder(n->Left());
       postOrder(n->Right());
       cout << n->Key() << " ";
    }
}

int main()
  {
   Tree* tree = new Tree();
   tree->addNode(30);
   tree->addNode(10);
   tree->addNode(20);
   tree->addNode(40);
   tree->addNode(50);

   cout << "In order traversal" << endl;
   tree->inOrder(tree->Root());
   cout << endl;

   cout << "Pre order traversal" << endl;
   tree->preOrder(tree->Root());
   cout << endl;

   cout << "Post order traversal" << endl;
   tree->postOrder(tree->Root());
   cout << endl;

   delete tree;
   return 0;
}

Output:
add root node ... 30
add other node ... 10
add other node ... 20
add other node ... 40
add other node ... 50
In order traversal
10 20 30 40 50
Pre order traversal
30 10 20 40 50
Post order traversal
20 10 50 40 30

program 15:

/*Program for BFS*/

#include <iostream>
using namespace std;
class Queue
     {
private:
int Rear, Front;
int que[50];
int max;
int Size;
public:
Queue()
  {
      Size = 0; max = 50;
      Rear = -1;
      Front = -1;
   }
int Is_Empty();
int Is_Full();
void Add(int Element);
int Delete();
int getFront();
    };
void Queue :: Add(int Element)
   {
      if(!Is_Full())
         que[++Rear] = Element;
      Size++;
   }
int Queue :: Delete()
   {
if(!Is_Empty())
              {
                 Size=Size-1;
                   return(que[++Front]);
                 }
    }
int Queue :: getFront()
    {
if(!Is_Empty())
          return(que[Front + 1]);
    }
int Queue :: Is_Empty()
   {
if(Front == Rear)
                 return 1;
             else
                  return 0;
   }
int Queue :: Is_Full()
     {
if(Rear==max-1)
                    return 1;
else
                   return 0;
     }
class Graph
  {
private:
int Vertex; // Number of vertices
int Edge; // Number of edges
int Adj_Matrix[10][10]; // Adjacency matrix
public:
Graph()// Constructor
  {
            Vertex=0;
            Edge=0;
   }
//bool IsEmpty();
void Insert_Vertex(int n);
void Insert_Edge(int u, int v);
void BFS(int u);
};

   void Graph :: Insert_Vertex(int n)
   {
       Vertex=n;
       for(int  i=0; i<=n;i++)
                for(int  j=0;j<=n;j++)
                     Adj_Matrix[i][j]=0;
   }                
void Graph :: Insert_Edge(int u, int v)
   {
            Adj_Matrix[u][v]=1;
            Edge++;
   }  
void Graph :: BFS(int i)
   {
int  k, j,visited[Vertex];
Queue Q;
for(k = 1; k <= Vertex; k++)
       visited[k] = 0;
visited[i] = 1;
cout<<"\n"<<"Visited Vertex :"<<i;
Q.Add(i);
while(!Q.Is_Empty())
     {
   j = Q.Delete();
  for(k = 1; k <= Vertex; k++)
           {
if(Adj_Matrix[j][k] && !visited[k])
    {
                                     Q.Add(k);
                                     visited[k] = 1;
                        cout<<"\n"<<"Visited Vertex :"<<k;
   }
      }
    }
}
int main()
    {
            Graph G;
            G.Insert_Vertex(7);
            G.Insert_Edge(1,2);
            G.Insert_Edge(1,4);
            G.Insert_Edge(1,5);
            G.Insert_Edge(2,3);
            G.Insert_Edge(2,5);
            G.Insert_Edge(4,7);
            G.Insert_Edge(5,7);
            G.Insert_Edge(3,6);
            G.BFS(1);
            return 0;
    }
Output:
Visited Vertex :1
Visited Vertex :2
Visited Vertex :4
Visited Vertex :5
Visited Vertex :3
Visited Vertex :7
Visited Vertex :6

/* program for DFS*/
#include <iostream>
using namespace std;

class Stack
      {
private:
int Stk[50];
int Max;
int top;
public:
Stack()
    {
Max = 50;
top =-1;
     }
int pop();
void push(int Element);
int Is_Empty();
int IsFull();
      };
int Stack :: Is_Empty()
    {
if(top ==-1)
return 1;
else
return 0;
    }
int Stack :: IsFull()
      {
if(top == Max-1)
return 1;
else
return 0;
      }

int Stack :: pop()
   {
if(!Is_Empty())
return(Stk[top--]);
   }
void Stack :: push(int Element)
    {
if(!IsFull())
Stk[++top] = Element;
     }
class Graph
     {
private:
int Vertex; // Number of vertices
int Adj_Matrix[10][10]; // Adjacency matrix
//int visited[10];
public:
Graph()// Constructor
  {
             Vertex=0;
   }
void Insert_Vertex(int n);
void Insert_Edge(int u, int v);
void DFS(int i);
   };

   void Graph :: Insert_Vertex(int n)
       {
       Vertex=n;
       for(int  i=0; i<=n;i++)
         for(int  j=0;j<=n;j++)
              Adj_Matrix[i][j]=0;
        }           
void Graph :: Insert_Edge(int u, int v)
   {
            Adj_Matrix[u][v]=1;
   }  
void Graph::DFS(int cur)
   {
Stack S;
int i, j, k, visited[10];
for( i=1; i<=Vertex; i++)
       visited[i] = 0;
S.push(cur);
while(!S.Is_Empty())
    {
j=S.pop();
if (visited[j]!=1)
   {
      visited[j]=1;
      cout<<"\n"<<"Visited Vertex :"<<j;
      for(k = 1; k <=Vertex; k++)
{
               if(Adj_Matrix[j][k] ==1)//&& !visited[k])
                    {
                          S.push(k);
                     }
                }
  }
      }
}
int main()
    {
            Graph G;
            G.Insert_Vertex(6);
            G.Insert_Edge(1,2);
            G.Insert_Edge(1,4);
            G.Insert_Edge(2,3);
            G.Insert_Edge(2,5);

            G.Insert_Edge(4,5);
            G.Insert_Edge(5,6);
            G.DFS(1);
            return 0;
    }
Output:
Visited Vertex :1
Visited Vertex :4
Visited Vertex :5
Visited Vertex :6
Visited Vertex :2
Visited Vertex :3

program 16:

/*Program for PRIM’s Algorithm*/

#include <iostream>
using namespace std;
#include <conio.h>
#define ROW 7
#define COL 7
#define infi 9999 
class Prims
{
   int AdjMat[ROW][COL],vertices;
   public:
   Prims();
   void CreateG();
   void PMST();
};

Prims :: Prims(){
     for(int i=0;i<ROW;i++)
       for(int j=0;j<COL;j++)
     AdjMat[i][j]=0;
}

void Prims :: CreateG()
{
    int i,j;
    cout<<"Enter Total No. of Vertices : ";
    cin>>vertices;
    cout<<"\n\nEnter weights in Adjacency Matrix (type zero(0) for no weight) : \n";
    for(i=0;i<vertices;i++)
        for(j=0;j<vertices;j++)
        cin>>AdjMat[i][j];

                        //Assign infinity to all AdjMat[i][j] where weight is 0.
    for(i=0;i<vertices;i++){
        for(j=0;j<vertices;j++){
           if(AdjMat[i][j]==0)
          AdjMat[i][j]=infi;
        }
    }
}

void Prims :: PMST(){
    int RowSelect[ROW],i,j,edges;
    int  min, x, y, fal=0,tru=1;

    for(i=0;i<vertices;i++)
       RowSelect[i]=fal;

    RowSelect[0]=tru;
    edges=0;

    while(edges < vertices-1){
       min=infi;

       for(i=0;i<vertices;i++)
       {
          if(RowSelect[i]==tru){
         for(j=0;j<vertices;j++){
            if(RowSelect[j]==fal){
               if(min > AdjMat[i][j])
               {
               min=AdjMat[i][j];
               x=i;
               y=j;
               }
            }
         }
          }
       }
       RowSelect[y]=tru;
       cout<<"\n"<<x+1<<" --> "<<y+1;
       edges=edges+1;
    }
}

int main(){
    Prims M;
    clrscr();
    M.CreateG();
    cout<<"\n Selected edges for Minimum Spanning Tree\n";
    M.PMST();
    return 0;
}
Output:
Enter Total No. of Vertices : 4
 
Enter weights in Adjacency Matrix (type zero(0) for no weight) : 
 
10
4
2
7
8
10
8
6
0
11
0
15
5
7
0
0
Selected edges for Minimum Spanning Tree

1 --> 3
1 --> 2
2 --> 4

/*Program for Kruskals algorithm*/

#include <iostream>
#include <stdlib.h>
using namespace std;

    int i,j,k,a,b,u,v,n,ne=1;
    int min1,mincost=0,cost[9][9],parent[9];
    int find(int);
    int uni(int,int);
    int main()
    {
            cout<<"\n"<<"Enter the no. of vertices:";
            cin>>n;
            cout<<"\n"<<"Enter the cost adjacency matrix:";
            for(i=1;i<=n;i++)
            {
                        for(j=1;j<=n;j++)
                        {
                                    cin>>cost[i][j];
                                    if(cost[i][j]==0)
                                                cost[i][j]=999;
                        }
            }
            cout<<"\n"<<"The edges of Minimum Cost Spanning Tree are"<<"\n";
            while(ne < n)
            {
                        for(i=1,min1=999;i<=n;i++)
                        {
                                    for(j=1;j <= n;j++)
                                    {
                                                if(cost[i][j] < min1)
                                                {
                                                            min1=cost[i][j];
                                                            a=u=i;
                                                            b=v=j;
                                                }
                                    }
                        }
                        u=find(u);
                        v=find(v);
                        if(uni(u,v))
                        {
                          cout<<ne++<<" edge : ("<<a<<" , "<<b<<") , cost :"<<min1<<"\n";
                                    mincost +=min1;
                        }
                        cost[a][b]=cost[b][a]=999;
            }
            cout<<"\n"<<"Minimum cost :  "<<mincost;
            return 0;
    }
    int find(int i)
    {
            while(parent[i])
            i=parent[i];
            return i;
    }
    int uni(int i,int j)
    {
            if(i!=j)
            {
                        parent[j]=i;
                        return 1;
            }
            return 0;
    }
Output:
Enter the no. of vertices:4
Enter the cost adjacency matrix:
10
1
3
12
15
7
8
4
0
20
2
4
0
9
5
0
The edges of Minimum Cost Spanning Tree are
1 edge : (1 , 2) , cost :1
2 edge : (1 , 3) , cost :3
3 edge : (2 , 4) , cost :4

Minimum cost :  8


Comments

Post a Comment

Popular posts from this blog

DS unit-wise important questions

UNIT-I 4m questions(short type): 1) Define data structure 2) What is an ADT 3) Define algorithm, steps and characteristics 4) Define 1-D, 2-D and n-D arrays 5) Pros and cons of arrays 6) Briefly write about Stack ADT 7) Write how to convert infix to postfix expression 15m questions(essay): 1) Explain various types of data structures 2) Explain in detail analysis of algorithms 3) Algorithm design tools(pseudocode & flowchart) 4) Explain about string manipulation using arrays 5) Define stack. Explain different operations performed on stack 6) Describe in brief applications of stack 7) Pseudocode notations UNIT-II Short type: 1) Write in brief about recursion and its advantages 2) Write an algorithm on fibonacci series and factorial of given number 3) Iteration vs recursion 4) Define queue, circular queue and deque 5) Define Queue ADT 6) Define linked list, DLL and CLL 7) Advantages and disadvantages of linked list 8) Advantag...
Read more

web lab programs

Program 1: <html> <head> <title>text formatting tags</title> </head> <body bgcolor=red> <h1 align=center> different tag format </h1> <br> here the text with <b> bold</b> <br> here the text with <i>italic</i> <br> here the text with <u>underline</u> <br> here the text with <small>small </small> <br> here the text with <strong> strong </strong> here the text with <em> emphasise </em><br> here the text with <font size=6 color=red>font </font> <br> here the text with <s> strike </s> <br> here the text with <h1> header tag</h1> </body> </html> Program 2: <html> <head> <title> FONTS </title> </head> <body bgcolor=yellow> <center> <font color=red size=5 face="couriernew"...
Read more