Thursday, February 7, 2013

Amazon question-Program to Find the number of connected graphs in the given matrix

consider the following diagram.
if the adjacent position is 1 we can traverse through that element and we can form a graph.So the number of graphs that we can form is 2.The solution for this question is very simple . Check every element in the matrix and if the element is 1 increase the count by 1 and change its connected elements (or nodes) to 0 .

Code: (in C)

int find_no_of_graphs(int** array,int rows,int cols)
{
    int i,j,count=0;
    for(i=0;i < m;i++)
   {
            for(j=0;j < n;j++)
           {
                 if(array[i][j]==1)
                {
                       //if the element is 1 increment the graph count and set it's connected elements to 0.
                         find_connected_positions(array,i,j);
count++;
                  }
              }
       }
     return count;
}

void find_connected_positions(int** array,int i,int j,int rows ,int cols)
{
      array[i][j]=0;
      if(i-1>=0)
     {
if(array[i-1][j]==1)
find_connected_positions(array,i-1,j,rows,cols);
if(j-1>=0)
{
if(array[i-1][j-1]==1)
find_connected_positions(array,i-1,j-1,rows,cols);
}
if(j+1 < cols)
{
if(array[i-1][j+1]==1)
find_connected_positions(array,i-1,j+1,rows,cols);
}
       }
    if(i+1 < rows)
   {
if(array[i+1][j]==1)
find_connected_positions(array,i+1,j,rows,cols);
if(j-1>=0)
{
if(array[i+1][j-1]==1)
find_connected_positions(array,i+1,j-1,rows,cols);
}
if(j+1 < cols)
{
if(array[i+1][j+1]==1)
find_connected_positions(array,i+1,j+1,rows,cols);
}
       }
     if(j-1>=0)
     {
if(array[i][j-1]==1)
find_connected_positions(array,i,j-1,rows,cols);
       }
      if(j+1 < cols)
     {
if(array[i][j+1]==1)
find_connected_positions(array,i,j+1,rows,cols);
       }
}

Please let me know if there is any bug in the above code and your suggestions are always welcome .

No comments: