14,644,614 members

# How can I check if the adjacency matrix doesn't contain cycle or loop?

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;
}
}

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.";
}
Tags: C++