Click here to Skip to main content
14,644,614 members

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

AhmedYousry20 asked:

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

Preview



When answering a question please:
  1. Read the question carefully.
  2. Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
  3. If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
  4. Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.
Let's work to help developers, not make them feel stupid.
Please note that all posts will be submitted under the http://www.codeproject.com/info/cpol10.aspx.




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