Warshall and Warshall Floyd Algorithm C++ code

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
int main()
{
    int n,i,j,k,m,p;
    cout<<"\nEnter the number of nodes:";
    cin>>n;
    fflush(stdin);
    char name[n][3],ch;
    int recon[n][n];
    int adj[n][n],path[n][n];
    for(i=0;i<n;i++)
   {
     cout<<"\n\a\aEnter the name on node:";
     cin>>name[i];
    for(j=0;j<n;j++)
    {
         fflush(stdin);
         cout<<"\n\nEnter element at position ("<<i+1<<","<<j+1<<") : ";
         cin>>adj[i][j];
         if(i!=j)
         {cout<<"\n\nIs this path direct?(Y/N):";
         cin>>ch;}
         else
         ch='n';
         if(ch=='y' || ch=='Y')
         recon[i][j]=i+1;
         else
         recon[i][j]=0;
         path[i][j]=adj[i][j];
    }
   }
    system("cls");
    cout<<"\nThe adjacency matrix::\n\n";
    cout<<" ";
    for(i=0;i<n;i++)
    {
        cout<<"  ";
        cout<<name[i];
    }
    cout<<endl;
    for(i=0;i<n;i++)
    {
        cout<<name[i]<<" ";
        for(j=0;j<n;j++)
        {
           cout<<adj[i][j];
           cout<<"   ";
        }
        cout<<endl;
    }
cout<<"\nEnter:\n1:Warshall's Law\n2:Warshall Floyd law\nYour choice:";
cin>>i;
system("cls");
if(i==1)
{
    for(k=0;k<n;k++)
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(path[i][k]*path[k][j]==1)
                path[i][j]=1;
            }
        }
       if(k!=n-1)
       cout<<"\n\nAfter pass "<<k+1<<" for k="<<k<<" the intermediate path matrix::\n\n";
       else
       cout<<"\n\nFinal Path matrix::\n\n";
       cout<<" ";
    for(m=0;m<n;m++)
    {

        cout<<"  ";
        cout<<name[m];
    }
    cout<<endl;
    for(m=0;m<n;m++)
    {
        cout<<name[m]<<" ";
        for(p=0;p<n;p++)
        {
           cout<<path[m][p];
           cout<<"   ";
        }
        cout<<endl;
    }
    }
}
else if(i==2)
{
     for(k=0;k<n;k++)
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if((path[i][k]+path[k][j])<path[i][j])
               {
                path[i][j]=path[i][k]+path[k][j];
                recon[i][j]=recon[k][j];
               }
            }
        }
       if(k!=n-1)
       cout<<"\n\nAfter pass "<<k+1<<" for k="<<k<<" the intermediate path matrix::\n\n";
       else
       cout<<"\n\nFinal Path matrix::\n\n";
       cout<<" ";
    for(m=0;m<n;m++)
    {

        cout<<"  ";
        cout<<name[m];
    }
    cout<<endl;
    for(m=0;m<n;m++)
    {
        cout<<name[m]<<" ";
        for(p=0;p<n;p++)
        {
           cout<<path[m][p];
           cout<<"   ";
        }
        cout<<endl;
    }
    }
    //*******************************************************
       cout<<"\a\a\n\n\nReconstructed Path matrix::\n\n";
       cout<<" ";
    for(m=0;m<n;m++)
    {

        cout<<"  ";
        cout<<name[m];
    }
    cout<<endl;
    for(m=0;m<n;m++)
    {
        cout<<name[m]<<" ";
        for(p=0;p<n;p++)
        {
           cout<<recon[m][p];
           cout<<"   ";
        }
        cout<<endl;
    }
}
else
cout<<"\a\a\nWrong call!!";
return 0;
}

Minimum Spanning Tree Prim's Algorithm C++ code

#define INFINITY 0
#define MAXEDGE 15
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
void node(int i);
using namespace std;
int n,y=-1,arr[10];
struct group
{
   char name;
   int use;
}ob[MAXEDGE];
int main()
{
    int i,j,d,c1,c2,minimum,x,cnt;
    cout<<"\nEnter the number of nodes:";
    cin>>n;
    fflush(stdin);
    int adj[n][n];
    for(i=0;i<n;i++)
   {
    cout<<"\n\a\aEnter the name on node:";
    cin>>ob[i].name;
    ob[i].use=0;
    for(j=0;j<n;j++)
    {
         fflush(stdin);
         cout<<"\n\nEnter cost at position ("<<i+1<<","<<j+1<<") : ";
         cin>>adj[i][j];
    }
   }
    system("cls");
    cout<<"\nThe adjacency matrix::\n\n";
    cout<<" ";
    for(i=0;i<n;i++)
    {
        cout<<"  ";
        cout<<ob[i].name;
    }
    cout<<endl;
    for(i=0;i<n;i++)
    {
        cout<<ob[i].name<<" ";
        for(j=0;j<n;j++)
        {
           cout<<adj[i][j];
           cout<<"   ";
        }
        cout<<endl;
    }
cout<<"\n\n";
system("pause");
system("cls");
//DISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAYDISPLAY
cout<<"MST vertex set          partial MST set                 chosen edge\n\n";
node(0);
for(i=0;i<n-1;i++)
{
    d=0;
    cnt=0;
    for(int q=0;q<23-(2*(i+1));q++)
    cout<<" ";
    for(x=0;x<=y;x++)
    for(j=0;j<n;j++)
    {
        if(adj[arr[x]][j]!=INFINITY && (ob[arr[x]].use==0 || ob[j].use==0))
        {
            if(d++==0)
            {
            minimum=adj[arr[x]][j];
            c1=arr[x];
            c2=j;
            }
            cout<<"("<<ob[arr[x]].name<<","<<ob[j].name<<")"<<",";
            cnt++;
            if(adj[arr[x]][j]<minimum)
            {
                minimum=adj[arr[x]][j];
                c1=arr[x];
                c2=j;
            }
        }
    }
    for(int q=0;q<32-(6*cnt);q++)
    cout<<" ";
    cout<<"("<<ob[c1].name<<","<<ob[c2].name<<")";
    node(c2);
}
return 0;
}
void node(int i)
{
    arr[++y]=i;
    ob[i].use=1;
    cout<<"\n\n{";
    for(int j=0;j<=y;j++)
    {
        cout<<ob[arr[j]].name;
        if(j!=y)
        cout<<",";
    }
    cout<<"}";
}

Single and Doubly Linked List Implementation with addition and removal of nodes, C++ code

#include<iostream>
using namespace std;
#include<conio.h>
#include<stdlib.h>
int display(void);
int single(int d,int count);
int doubly(int d,int cnt);
void out(int c);
void outy(int cn);



struct single_ll
{
       int data;
       struct single_ll *e;
}*f,*l,*t,*q,*n;

struct double_ll
{
       int entry;
       struct double_ll *nxt;
       struct double_ll *prev;
}*first,*last,*temp,*m,*r;

int ch,p=0,z;
int main()
{   f=NULL;
    first=NULL;
    int dec,count=0,cnt=0;
    char c='Y';
    while(c=='Y' || c=='y')
    {             system("cls");
                  cout<<"\n"<<"Choose:";
                  cout<<"\n"<<"1==Single Linked List";
                  cout<<"\n"<<"2==Doubly Linked List";
                  cout<<"\n"<<"Your choice (1 or 2) : ";
                  cin>>ch;
                  if(ch==1)
                  {

                  dec=display();
                  count=single(dec,count);

                  }
                  else if(ch==2)
                  {

                  dec=display();
                  cnt=doubly(dec,cnt);

                  }
                  else
                  cout<<"\n"<<"You entered a wrong choice!!";
                  cout<<"\n"<<"Want to continue by re-entering your choice?(Y/N): ";
                  cin>>c;
    }
    cout<<"\n"<<"ThankYou!! Have A Nice Day :) "<<"\n"<<"\n";
    getch();
}

int display(void)
{   int d;
    cout<<"\n"<<"Choose:";
    cout<<"\n"<<"1>Adding node"<<"\n"<<"2>Deleting node"<<"\n"<<"3>Displaying the contents"<<"\n";
    cout<<"\n"<<"Your choice : ";
    cin>>d;
    return d;
}

int single(int d,int count)
{
     switch(d)
     {
              case 1:{
                      int flag=0;
                      if(count<0)
                      count=0;
                      if(count==0)
                      {
                      cout<<"\n"<<"Link List is empty"<<"\n";
                      cout<<"You can only add first node"<<endl;
                      f=new single_ll;
                      cout<<"\n"<<"Enter the data in the node:";
                      cin>>f->data;
                      f->e=NULL;
                      l=f;
                      cout<<"\n"<<"Node added at position 1";
                      count++;
                      }

                      else
                      {
                      cout<<"\n"<<"The list has "<<count<<" nodes";
                      cout<<"\n"<<"Where you want to add the node?(Enter position.,eg.1 or 2...)";
                      cin>>p;
                      z=p;

                      if(p<0 || p>(count+1))
                      {
                      cout<<"\n"<<"Wrong Entry!!";
                      flag=1;

                      }

                      else if(p>1 && p<(count+1))
                      {

                      t=new single_ll;
                      n=f;

                      //Logic for inserting in b//

                      while((p--)!=1)
                      {
                      q=n;
                      n=n->e;
                      }
                      q->e=t;
                      t->e=n;
                      q=NULL;
                      n=NULL;
                      cout<<"\n"<<"Enter the data for the node:";
                      cin>>t->data;

                      }

                      else if(p==1)
                      {
                      t=new single_ll;
                      cout<<"\n"<<"Enter the data for the node:";
                      cin>>t->data;
                      t->e=f;
                      f=t;
                      t=NULL;
                      }

                      else if(p==(count+1))
                      {
                      t=new single_ll;
                      cout<<"\n"<<"Enter the data for the node:";
                      cin>>t->data;
                      l->e=t;
                      t->e=NULL;
                      l=t;
                      t=NULL;
                      }
                      count++;
                      if(flag==0)
                      cout<<"\n"<<"Node added at position "<<z;
                      }

                      return count;
                      }
                      break;
              case 2: {

                      if(count<0)
                      count=0;
                      int flag=0;
                      if(count==0)
                      {
                      cout<<"\n"<<"List is empty!";
                      flag=1;
                      }

                      else
                      {
                      if(count>0)
                      cout<<"\n"<<"The list has "<<count<<" node(s)";
                      cout<<"\n"<<"Which node to delete(Enter position.,eg.1 or 2...):";
                      cin>>p;
                      z=p;

                      //Logic for deletion
                      if(p<=count)
                      {

                      if(p>1 && p<(count+1))
                      {
                      t=f;
                      while(p--!=1)
                      {
                      q=t;
                      t=t->e;
                      }
                      q->e=t->e;
                      t=NULL;
                      }

                      else if(p==1)
                      {
                      t=f;
                      f=f->e;
                      t=NULL;
                      }

                      if(flag==0)
                      {
                      cout<<"\n"<<"Deleted node is node"<<z;
                      return --count;
                      }
                      }


                      else
                      {
                      cout<<"\n"<<"Wrong entry!!";
                      return count;
                      }
                      }
                      }
                      break;
              case 3: {
                      out(count);
                      return count;
                      }
              break;
              default:cout<<"\n"<<"Wrong Choice!";
              }
              }

void out(int c)
{
     if(c==0)
     cout<<"\n"<<"List is empty!";
     else
     {   cout<<"\n";
         t=f;
         do
         {
         cout<<t->data<<"-->>";
         t=t->e;
         }
         while(t!=NULL);
     }
}

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

int doubly(int d,int cnt)
{

     switch(d)
     {
              case 1:{
                      int flag=0;
                      if(cnt<0)
                      cnt=0;
                      if(cnt==0)
                      {
                      cout<<"\n"<<"Link List is empty"<<"\n";
                      cout<<"You can only add first node"<<endl;
                      first=new double_ll;
                      cout<<"\n"<<"Enter the data in the node:";
                      cin>>first->entry;
                      first->nxt=NULL;
                      first->prev=NULL;
                      last=first;
                      cout<<"\n"<<"Node added at position 1";
                      cnt++;
                      }

                      else
                      {
                      cout<<"\n"<<"The list has "<<cnt<<" nodes";
                      cout<<"\n"<<"Where you want to add the node?(Enter position.,eg.1 or 2...)";
                      cin>>p;
                      z=p;

                      if(p<0 || p>(cnt+1))
                      {
                      cout<<"\n"<<"Wrong Entry!!";
                      flag=1;
                      return cnt;
                      }

                      else if(p>1 && p<(cnt+1))
                      {

                      temp=new double_ll;
                      m=first;

                      //Logic for inserting in b//

                      while((p--)!=1)
                      {
                      r=m;
                      m=m->nxt;
                      }
                      r->nxt=temp;
                      temp->nxt=m;
                      m->prev=temp;
                      temp->prev=r;
                      r=NULL;
                      m=NULL;
                      cout<<"\n"<<"Enter the data for the node:";
                      cin>>temp->entry;

                      }

                      else if(p==1)
                      {
                      temp=new double_ll;
                      cout<<"\n"<<"Enter the data for the node:";
                      cin>>temp->entry;
                      temp->nxt=first;
                      first->prev=temp;
                      first=temp;
                      temp=NULL;
                      }

                      else if(p==(cnt+1))
                      {
                      temp=new double_ll;
                      cout<<"\n"<<"Enter the data for the node:";
                      cin>>temp->entry;
                      last->nxt=temp;
                      temp->prev=last;
                      temp->nxt=NULL;
                      last=temp;
                      temp=NULL;
                      }
                      cnt++;
                      if(flag==0)
                      cout<<"\n"<<"Node added at position "<<z;
                      }

                      return cnt;
                      }
                      break;
              case 2: {

                      if(cnt<0)
                      cnt=0;
                      int flag=0;
                      if(cnt==0)
                      {
                      cout<<"\n"<<"List is empty!";
                      flag=1;
                      }

                      else
                      {
                      if(cnt>0)
                      cout<<"\n"<<"The list has "<<cnt<<" node(s)";
                      cout<<"\n"<<"Which node to delete(Enter position.,eg.1 or 2...):";
                      cin>>p;
                      z=p;

                      //Logic for deletion
                      if(p<=cnt)
                      {

                      if(p>1 && p<(cnt+1))
                      {
                      temp=first;
                      while(p--!=1)
                      {
                      r=temp;
                      temp=temp->nxt;
                      m=temp->nxt;
                      }
                      r->nxt=m;
                      m->prev=r;
                      temp=NULL;
                      }

                      else if(p==1)
                      {
                      temp=first;
                      first=first->nxt;
                      first->prev=NULL;
                      temp=NULL;
                      }

                      if(flag==0)
                      {
                      cout<<"\n"<<"Deleted node is node"<<z;
                      return --cnt;
                      }
                      }


                      else
                      {
                      cout<<"\n"<<"Wrong entry!!";
                      return cnt;
                      }
                      }
                      }
                      break;
              case 3: {
                      outy(cnt);
                      return cnt;
                      }
              break;
              default:cout<<"\n"<<"Wrong Choice!";
              }


}

void outy(int c)
{
     if(c==0)
     cout<<"\n"<<"List is empty!";
     else
     {   cout<<"\n";
         temp=first;
         do
         {
         cout<<temp->entry<<"-->>";
         temp=temp->nxt;
         }
         while(temp!=NULL);
     }
}

Implementing Kruskal's Algorithm Data Structure C++ code

# define INFINITY 0
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
int n,y=-1,k,flag;
struct group
{
    int cost,e1,e2;
}ob[12];
int main()
{
    int i,j,m,b,c=0,sum=0;
    cout<<"\nEnter the number of nodes:";
    cin>>n;
    fflush(stdin);
    char name[n];
    int adj[n][n],test[n],path[n][n],path_copy[n][n];
    for(i=0;i<n;i++)
   {
     cout<<"\n\a\aEnter the name on node:";
     cin>>name[i];
    for(j=0;j<n;j++)
    {
         fflush(stdin);
         cout<<"\n\nEnter cost at position ("<<i+1<<","<<j+1<<") : ";
         cin>>adj[i][j];
         path[i][j]=0;
         path_copy[i][j]=0;
         if(j>i && adj[i][j]!=INFINITY)
         {
         ob[++y].cost=adj[i][j];
         ob[y].e1=i;
         ob[y].e2=j;
         }
    }
   }
    system("cls");
    cout<<"\nThe adjacency matrix::\n\n";
    cout<<" ";
    for(i=0;i<n;i++)
    {
        cout<<"  ";
        cout<<name[i];
    }
    cout<<endl;
    for(i=0;i<n;i++)
    {
        cout<<name[i]<<" ";
        for(j=0;j<n;j++)
        {
           cout<<adj[i][j];
           cout<<"   ";
        }
        cout<<endl;
    }
    system("pause");
    system("cls");
    //Sort(Selection)
    for(i=0;i<=y;i++)
    {
        k=0;
        for(j=1;j<=y-i;j++)
        {
            if((ob[j].cost)>(ob[k].cost))
            k=j;
        }
        swap(ob[k],ob[j-1]);
    }
    cout<<"\nCost             Edge\n\n";
    for(i=0;i<=y;i++)
    {
        m=0;b=0,flag=1;
        for(j=0;j<i;j++)
        {
            if(ob[i].e1==ob[j].e1 || ob[i].e1==ob[j].e2)
            {m++;}
            if(ob[i].e2==ob[j].e1 || ob[i].e2==ob[j].e2)
            {b++;}
        }
        if(m>0 && b>0 && c<n-1)
        {
            //Warshall
            int f,g,k;
            for(k=0;k<n;k++)
            {
                for(f=0;f<n;f++)
                {
                    for(g=0;g<n;g++)
                    {
                        if(path[f][k]*path[k][g]==1)
                        path[f][g]=1;
                    }
                }
            }
            if(path[ob[i].e1][ob[i].e2]==1)
            flag=0;

            else
            {
                path_copy[ob[i].e1][ob[i].e2]=1;
                path_copy[ob[i].e2][ob[i].e1]=1;
                //For restoring path matrix
                for(int u=0;u<n;u++)
                {
                    for(int v=0;v<n;v++)
                    path[u][v]=path_copy[u][v];
                }
            }
        }
        else
        {
            path[ob[i].e1][ob[i].e2]=1;
            path[ob[i].e2][ob[i].e1]=1;

            path_copy[ob[i].e1][ob[i].e2]=1;
            path_copy[ob[i].e2][ob[i].e1]=1;
        }
        if(flag==1 && c<n-1)
        {
            cout<<ob[i].cost<<"               "<<"("<<name[ob[i].e1]<<","<<name[ob[i].e2]<<")"<<endl<<endl;
            c++;
            sum+=ob[i].cost;
        }
    }
    cout<<"----\n"<<sum<<endl<<endl;
    return 0;
}

Construct Graph and adding nodes and edges and displaying adjacency list using C++

#include<iostream>
#include<stdlib.h>
using namespace std;
void make_node(int n);
void add_edges();
void display();
int n;
struct edge;
struct node
{
    int data;
    struct node *below;
    struct edge *adj;
}*start,*temp,*last,*ptrx;

struct edge
{
    struct node *parent;
    struct edge *link;
}*first,*stop,*ptr;

int main()
{
    cout<<"\nEnter the number of nodes:";
    cin>>n;
    make_node(n);
    add_edges();
    display();
    return 0;
}

void make_node(int n)
{
    for(int i=0;i<n;i++)
    {
        if(start==nullptr)
        {
            start=new node;
            cout<<"\nEnter data in node "<<i+1<<" : ";
            cin>>start->data;
            start->below=nullptr;
            start->adj=nullptr;
            last=start;
        }
        else
        {
            temp=new node;
            cout<<"\nEnter data in node "<<i+1<<" : ";
            cin>>temp->data;
            last->below=temp;
            last=temp;
            last->below=nullptr;
            last->adj=nullptr;
            temp=nullptr;
        }
    }
}

void add_edges()
{
    int x,t;
    last=start;
    for(int i=0;i<n;i++,last=last->below)
    {
        cout<<"\nEnter number of edges in node "<<i+1<<" : ";
        cin>>x;
        ptrx=last;
        first=nullptr;
        for(int j=0;j<x;j++)
    {
        temp=start;
        if(first==nullptr)
        {
            first=new edge;
            cout<<"\nEnter the adjacent node "<<j+1<<" : ";
            cin>>t;
            for(int k=1;k<t;k++)
            temp=temp->below;
            first->parent=temp;
            first->link=nullptr;
            ptrx->adj=first;
            stop=first;
        }
        else
        {
            first=new edge;
            cout<<"\nEnter the adjacent node "<<j+1<<" : ";
            cin>>t;
            for(int k=1;k<t;k++)
            temp=temp->below;
            first->parent=temp;
            first->link=nullptr;
            stop->link=first;
            stop=first;
        }
    }
    }
}

void display()
{
    system("cls");
    cout<<"\nNode\t\t\tAdjacent node list";
    temp=start;
    for(int i=0;i<n;i++,temp=temp->below)
    {
        cout<<"\n"<<temp->data<<"\t\t\t\t";
        ptr=temp->adj;
        if(ptr!=nullptr)
        {
        while(ptr->link!=nullptr)
        {
            ptrx=ptr->parent;
            cout<<ptrx->data<<";";
            ptr=ptr->link;
        }
            ptrx=ptr->parent;
            cout<<ptrx->data;
        }
    }
}

Dijkstra's algorithm C++ code

# define SIZE 8
# define INFINITY 99
#include<iostream>
#include<stdlib.h>
using namespace std;
void build(int n);
void minimum(char key);
void table();
void print();
int n,c,mini,y,m;
int mat[SIZE][SIZE];
char name[SIZE];
struct adjac
{
    char node,k,hv;
    int dv,frend[7];
}ob[SIZE];

int main()
{
    cout<<"\nEnter the number of nodes:";
    cin>>n;
    build(n);
    table();
    system("cls");
    print();
}

void build(int n)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        cout<<"\nEnter the name of node "<<i+1<<" : ";
        cin>>name[i];
        ob[i].node=name[i];
        ob[i].dv=0;
        ob[i].hv='-';
        ob[i].k='F';
    }

    for(i=0;i<n;i++)
    {
        c=0;
        for(j=0;j<n;j++)
        {
            cout<<"\nEnter weight from node "<<name[i]<<" to node "<<name[j]<<" : ";
            cin>>mat[i][j];
            if(mat[i][j]!=0 && mat[i][j]!=INFINITY)
            {
                ob[i].frend[c++]=j;
            }
        }
         ob[i].frend[c]=-1;
         mat[i][i]=0;
    }
}

void table()
{
    int i,c,j;
    char key;
    cout<<"\nEnter the name of the key node:";
    cin>>key;
    minimum(key);
    for(j=0;j<n-1;j++)
    {
        minimum(ob[mini].node);
    }
}

void minimum(char key)
{
    int i;
     for(i=0;i<n;i++)
    {
        if(ob[i].k=='F')
        {
        if(ob[i].node==key)
        {
            ob[i].k='T';
            c=0;
            while(ob[i].frend[c]!=-1)
            {
                if(ob[ob[i].frend[c]].k=='F')
                {
                ob[ob[i].frend[c]].hv=ob[i].node;
                if(m++==c)
                ob[ob[i].frend[c]].dv+=mat[i][ob[i].frend[c]];
                else
                if(ob[ob[i].frend[c]].dv>ob[i].dv+mat[i][ob[i].frend[c]] || ob[ob[i].frend[c]].dv==0)
                ob[ob[i].frend[c]].dv=ob[i].dv+mat[i][ob[i].frend[c]];
                }
                c++;
            }
            break;
        }
        }
    }
    y=0;
    for(i=0;i<n;i++)
    {
    if(ob[i].dv!=0 && ob[i].k=='F')
    {
        if(y++==0)
        mini=i;
        if(ob[i].dv<ob[mini].dv)
        mini=i;
    }
    }
}

void print()
{
    int i;
    cout<<"\nNode       K            dv           hv\n\n";
    for(i=0;i<n;i++)
    {
        cout<<ob[i].node<<"          "<<ob[i].k<<"            "<<ob[i].dv<<"            "<<ob[i].hv<<endl<<endl;
    }

}