Check for Cycles in Adjacency Matrix?

Question

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?

Answer 1

There is two good solutions:

1. begin to traverse (bfs, dfs , ...) your graph if you visited a node twice there is cycle in your graph.

2. hence you have a adjacency matrix, then you could use algorithm that Imran mentioned in comment, you just need to compute Aⁿ, 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.