Solved programming problem

Finding Component of a Graph in C++.

Source code

#include <iostream>

#define size 100

using namespace std;

int q[size+1];

int f=0,r=0;

int n,len=0;

int graph[100][100];

char vertex[26];

char visit_array[100];

void create()

{

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

    {

        vertex[i] = 65+i;

    }

    cout<<"Insert total Vertex Number: "<<endl;

    cin>>n;

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

    {

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

        {

            graph[i][j]=0;

        }

    }

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

    {

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

        {

            cout<<vertex[i]<<vertex[j]<<": "<<endl;

            cin>>graph[i][j];

            if(graph[i][j]==1)

            {

                graph[j][i]=1;

            }

        }

    }

}

void visit(char c)

{

    visit_array[len++]=c;

}

int is_visit(char c)

{

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

    {

        if(c==visit_array[i])

        {

            return 1;

        }

    }

    return 0;

}

void enqueue(char c)

{

    r = (r+1)%(size+1);

    q[r]=c;

}

char dequeue()

{

    f = (f+1)%(size+1);

    char ch = q[f];

    q[f]='';

    return ch;

}

void find_adj(char c)

{

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

    {

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

        {

            if((graph[i][j]==1)&& vertex[i]==c)

            {

                if(is_visit(vertex[j])==0)

                {

                    enqueue(vertex[j]);

                }

            }

        }

    }

}

void BFS()

{

    while(f!=r)

    {

        char v=dequeue();

        find_adj(v);

        if(is_visit(v)==0)

        {

            visit(v);

        }

    }

}

int main()

{

   create();

   int count=0;

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

   {

       if(is_visit(vertex[i])==0)

       {

           enqueue(vertex[i]);

           count++;

           BFS();

       }

   }

   cout<<"Component: "<<count<<endl;

   return 0;

}

Output

Insert total Vertex Number:
5
AB:
1
AC:
0
AD:
0
AE:
1
BC:
0
BD:
0
BE:
0
CD:
0
CE:
0
DE:
1
Component: 2

Join the discussion

Add your comment