Click here to Skip to main content
14,664,481 members
Rate this:
Please Sign up or sign in to vote.
See more:
I asked the user to enter adjacency matrix and i tried to check by the following code, but sometimes it gives me "Graph is not a tree" whatever the input was and sometimes it turns to an infinite loop and shows "enter number of nodes" forever

What I have tried:

#include <iostream>
#include <stdlib.h>
using namespace std;
int v;
bool isCycle(int u, bool visited[], int parent) {
    int **A;
    cout<< "Enter number of nodes \n";
   cin>>v;

   A=(int**)malloc(v*sizeof(int*));
   if(A==NULL)
   {
       cout<<"Out of memory";
       return 1;
   }

   for(int i=0;i<v;i++)
   {
       A[i]=(int*)malloc(v*sizeof(int));
    if(A[i]==NULL)
    {
       cout<<"Out of memory";
       return 1;
    }
   }
   cout<<"NOTE that your Adjacency Matrix contains ZEROs and ONEs ONLY \n";

   cout<<"Enter your Adjacency Matrix \n";

   for(int i=0;i<v;i++)     //Fill Matrix
   {
        for(int j=0;j<v;j++)
        {
        cin>>A[i][j];
        }
   }

   visited[u] = true;    //mark v as visited
   for(int b = 0; b<v; b++) {
      if(A[u][b]) {
         if(!visited[b]) {     //when the adjacent node v is not visited
            if(isCycle(b, visited, u)) {
               return true;
            }
         } else if(b != parent) {    //when adjacent vertex is visited but not parent
            return true;    //there is a cycle
         }
      }
   }
   return false;
}
bool isTree() {
   bool *vis = new bool[v];

   for(int i = 0; i<v; i++)
      vis[i] = false;    //initialize as no node is visited

   if(isCycle(0, vis, -1))    //check if there is a cycle or not
      return false;

   for(int i = 0; i<v; i++) {
      if(!vis[i])    //if there is a node, not visited by traversal, graph is not connected
         return false;
   }
   return true;
}

int main() {
   if(isTree())
      cout << "The Graph is a Tree.";
   else
      cout << "The Graph is not a Tree.";
}
Posted
Updated 26-May-20 10:10am
v2

Rate this:
Please Sign up or sign in to vote.

Solution 3

One thing I noticed - check out your usage of the variable v. First, isTree() is called and the first thing it does is bool *vis = new bool[v]; What is the value of v at that time? You could assume zero but I don't like to rely on the value of uninitialized data. I prefer to always set it to something.

If I were you, I would change this logic to read the matrix in from a file. The first line can contain the size of the matrix and then the data can follow. This will make your testing cycles much faster since you don't have to enter data every time. The name of the file can be specified as a command line argument.
   
Comments
KarstenK 27-May-20 4:28am
   
I guess that this is copied code and pasted from someone who didnt understand it :-O
Rate this:
Please Sign up or sign in to vote.

Solution 1

It is a clear task for you to debug your code. For learning to code and to use the debugger you can visit Learn C++ and search for the debugger chapters.

Your function isCycle looks like you missed some real code. Return true and false and not 1 or 0.

To be honest: your code doesnt look like a solution, but some copied and pasted pieces without sense.

Tip: write some tests with known data, so you can check easily for the working of the code.
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100