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?

Answers


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 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.


Need Your Help

Emacs regexp-replace seems to work unexpectedly

regex emacs wildcard

I am trying to remove some <span style="something not constant"> from a text and I tried M-x replace-regexp> "<span*>" -> ""

Find PDF page count with Node (on Windows)

javascript node.js pdf phantomjs pdf.js

I did a lot of research (I guess not enough?) and am trying to find an easy to use library to find the page count of a PDF using Node.js. The library would need to be usable on a Windows OS.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.