C++ program for MST using Kruskal algorithm

C++ program for MST using Kruskal algorithm

#include <iostream>

using namespace std;

int find(int);

int uni(int,int);

int parent[9];

int main()

{

      int i,j,a,b,u,v,n,count=1;

      int min,mincost=0,cost[9][9];

      cout<<"\nEnter the number of nodes:";

      cin>>n;

      cout<<"\nEnter the adjacency matrix:\n";

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

      {

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

            {

                  cin>>cost[i][j];

                  if(cost[i][j]==0)

                        cost[i][j]=999;

            }

      }

      while(count < n)

      {

            min=999;

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

            {

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

                  {

                        if(cost[i][j] < min)

                        {

                              min=cost[i][j];

                              a=u=i;

                              b=v=j;

                        }

                  }

            }

            u=find(u);

            v=find(v);

            if(uni(u,v))

            {

                  cout<<"\nEdge"<<count++ <<" : " <<a<<"->"<<b<<" Cost= "<<min;

                  mincost +=min;

            }

            cost[a][b]=cost[b][a]=999;

      }

      cout<<"\nMinimun 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 number of nodes:4

Enter the adjacency matrix:

0 5 1 4

0 0 0 3

0 2 0 0

0 0 3 0

Edge1 : 0->2 Cost= 1

Edge2 : 2->1 Cost= 2

Edge3 : 1->3 Cost= 3

Minimun cost=6

C++ program for MST using Prims algorithm

C++ program for MST using Prims algorithm

#include <iostream>

using namespace std;

int main()

{

      int a,b,u,v,n,i,j,count=1;

      int visited[10]= {0},min,mincost=0,cost[10][10];

      cout<<"\nEnter the number of nodes:";

      cin>>n;

      cout<<"\nEnter the adjacency matrix:\n";

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

      {

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

            {

                  cin>>cost[i][j];

                  if(cost[i][j]==0)

                        cost[i][j]=999;  //replace all 0 with highest number

            }

      }

      visited[0]=1;

      cout<<"\n";

      while(count<n)

      {

            min=999;

            for(i=0;i<n;i++)// finding min. cost in matrix

            {

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

                  {

                        if(cost[i][j]<min)

                        {

                              if(visited[i]!=0)

                              {

                                    min=cost[i][j];

                                    a=u=i;

                                    b=v=j;

                              }

                        }

                  }

            }

            if(visited[u]==0 || visited[v]==0)

            {

                  cout<<"\nEdge"<<count++ <<" : " <<a<<"->"<<b<<" Cost= "<<min;

                  mincost+=min;

                  visited[b]=1;

            }

            cost[a][b]=cost[b][a]=999;  //replace processed min cost by highest number

      }

      cout<<"\nMinimun cost="<<mincost;

      return 0;

}

Output:

Enter the number of nodes:4

Enter the adjacency matrix:

0 5 1 4

0 0 0 3

0 2 0 0

0 0 3 0

Edge1 : 0->2 Cost= 1

Edge2 : 2->1 Cost= 2

Edge3 : 1->3 Cost= 3

Minimun cost=6

C++ program on Depth First Search on Graph

C++ program for Adjacency Matrix Representation of Graph and Depth First Search

 #include <iostream>

using namespace std;

void DFS(int);

int G[10][10],visited[10],n;    //n is no of vertices and graph is sorted in array G[10][10]

int main()

{

    int i,j;

    cout<<"Enter number of vertices:";

      cin>>n;

    //read the adjacency matrix

      cout<<"\nEnter adjacency matrix of the graph:";

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

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

                  cin>>G[i][j];

      //display the adjacency matrix

      cout<<"\n **Adjacency matrix**\n";

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

             {

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

                        cout<<G[i][j];

                  cout<<"\n";

             }

    //visited is initialized to zero

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

        visited[i]=0;

    cout<<"\n DFS of the graph:";

    DFS(0);

    return 0;

}

void DFS(int i)

{

    int j;

      cout<<i;

    visited[i]=1;

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

       if(!visited[j]&&G[i][j]==1)

            DFS(j);

}

Output:

Enter number of vertices:3

Enter adjacency matrix of the graph:0

1

0

0

0

1

1

1

0

 **Adjacency matrix**

010

001

110

 DFS of the graph:012

C++ Program for Breadth First Search on Graph

Program for Adjacency Matrix Representation of Graph and Breadth First Search

#include <iostream>

#include <queue>

using namespace std;

#define initial 1

#define waiting 2

#define visited 3

#define MAX 100

int state[MAX];

int n;

int G[10][10];

void BF_Traversal();

void BFS(int v);

int main()

{

      int i,j;

      cout<<"Enter number of vertices:";

      cin>>n;

      //read the adjacency matrix

      cout<<"\nEnter adjacency matrix of the graph:";

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

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

                  cin>>G[i][j];

      //display the adjacency matrix

      cout<<"\n **Adjacency matrix**\n";

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

      {

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

                  cout<<G[i][j];

            cout<<"\n";

      }

      BF_Traversal();

      return 0;

}

void BF_Traversal()

{

      int v;

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

            state[v] = initial;

      cout<<"Enter Start Vertex for BFS: \n";

      cin>>v;

      BFS(v);

}

void BFS(int v)

{

      int i;

      queue<int> q;

      q.push(v);

      state[v] = waiting;

      while(!q.empty())

      {

            int v = q.front();

            q.pop();

            cout <<v<<"\t" ;

            state[v] = visited;

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

            {

                  if(G[v][i] == 1 && state[i] == initial)

                  {

                        q.push(i);

                        state[i] = waiting;

                  }

            }

      }

      cout<<"\n";

}

Output:

Enter number of vertices:4

Enter adjacency matrix of the graph:0

1

1

1

1

0

1

1

1

1

0

1

1

1

1

0

 **Adjacency matrix**

0111

1011

1101

1110

Enter Start Vertex for BFS:

0

0      1      2      3