14,668,141 members
Rate this:
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:

## 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.
Rate this:

## 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

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

Top Experts
Last 24hrsThis month
 OriginalGriff 225 Richard MacCutchan 130 CPallini 115 Rick York 85 Richard Deeming 60
 OriginalGriff 5,166 Richard MacCutchan 3,485 CPallini 2,197 Sandeep Mewara 1,535 Patrice T 1,256

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