CODEWITHSUNDEEP
algorithmmatrixgraph
John Mòf
John Mòf

Reputation: 115

Directed graph: checking for cycle in adjacency matrix

There is an alternative method respect to the DFS algorithm to check if there are cycles in a directed graph represented with an adjacency matrix?

I found piecemeal information on the properties of matrices. Maybe I can multiply matrix A by itself n times, and check if there is non-zero diagonal in each resulting matrix.

While this approach may be right, how can I extract explicitly the list of vertices representing a cycle? And what about the complexity of this hypothetical algorithm?

Thanks in advance for your help.

Upvotes: 3

Views: 2147

Answers (2)

Codor
Codor

Reputation: 17595

Depth-first search can be modified to decide the existence of a cycle. The first time that the algorithm discovers a node which has previously been visited, the cycle can be extracted from the stack, as the previously found node must still be on the stack; it would make sense to use a user-defined stack instead of the call stack. The complexity would be O(|V|+|E|), as for unmodified depth-first search itself.

Upvotes: 0

Sorawee Porncharoenwase
Sorawee Porncharoenwase

Reputation: 6502

Let's say after n iterations, you have a matrix where the cell at row i and column j is M[n][i][j]

By definition M[n][i][j] = sum over k (M[n - 1][i][k] * A[k][j]). Let's say M[13][5][5] > 0, meaning it has a cycle of length 13 starting at 5 and ending at 5. To have M[13][5][5] > 0, there must be some k such that M[12][5][k] * A[k][5] > 0. Let's say k = 6, now you know one more node in the cycle (6). It also follows that M[12][5][6] > 0 and A[6][5] > 0

To have M[12][5][6] > 0, there must be some k such that M[11][5][k] * A[k][6] > 0. Let's say k = 9, now, you know one more node in the cycle (9). It also follows that M[11][5][9] > 0 and A[9][6] > 0

Then, you can do the same repetitively to find other nodes in the cycle.

Upvotes: 2

Related Questions