pseudo code for finding closed paths in a graph

Question

Hi All, I have an adjaceny matrix for a graph which tracks the edges between the nodes by having a 1 in the corresponding adjMat[i,j] = 1; Through this adjaceny matrix i wish to find out all the closed paths of length 4 which exists in the graph. Can anyone please provide me with a pseudo code. thank u

Answer 1

Apply a depth-limited depth-first-search to every node and record nodes where the DFS finds the starting node. For the search, see pseudo-code here: http://en.wikipedia.org/wiki/Depth-limited_search. You just need to add something like "if(node' == node && node'.depth==4) memorize(node)" to the beginning of the loop.

HTH, Tetha.

Answer 2

This sounds like homework, so I won't give the whole thing away. But here's a hint: since you are interested in finding cycles of length 4, take the 4th power of the adjacency matrix and scan along the diagonal. If any entry M[i,i] is nonzero, there is a cycle containing vertex i.

Answer 3

hey man thanks a lot but what do u mean by find 4th power of adjancey matrix?