Check for Cycles in Adjacency Matrix?
One of my methods in Java passes in an adjacency matrix with
- 1 values in matrix indicating a connection, and
- 0 values indicating no connection.
My adjacency matrix represents an un-directed graph.
How can I check whether my adjacency matrix has any cycles or not?
There is two good solutions:
begin to traverse (bfs, dfs , ...) your graph if you visited a node twice there is cycle in your graph.
hence you have a adjacency matrix, then you could use algorithm that Imran mentioned in comment, you just need to compute An, for n = 1 , .... and check if there is non zero diagonal entry or not, and I think your teacher wants this algorithm.
Just google adjacency matrix properties and you will find articles like this.