C-program to return true if any circuit/cycle exit otherwise false, for a for a given adjacency matrix?

Question

data structures (graph theory)

Answer 1

Assumme that you are given a graph of N nodes, with adjacency matrix, adj[N][N].
Adjacency matrix is a boolean matrix, where an entry at a location[i][j] means node i and node j is connected. You have to make sure that all the entries [i][i] are false or zero.

Now you have to multiply this matrix by itself. The formula is simple
for(int i=0;i<=N-1;i++)
for(iny j= 0 ;j<=N-1;j++)
{
new_mat[i][j] = False;
for(k = 0;k<=N-1;k++)
new_mat[i][j] = new_mat[i][j] || (new_mat[i][k] && new_mat[k][j]);
}

You will have to do this multiplication untill you get TRUE at any [i][i] place, or the consecutive two matrices are same.
First case means there is cycle.
Second case means there is no cycle.