1
$\begingroup$

I am trying to apply BFS to the following problem, but I'm not sure how to do it

Input: directed graph $G$ defined by the array of adjacency lists with n vertices and m edges, and a vertex $v$ in $G$

Output: $true$, if $v$ is a part of a cycle, $false$ otherwise

Can someone explain in pseudocode or in words how to do this?

$\endgroup$
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Dec 4 '17 at 3:37
  • $\begingroup$ @Lola1984: what will happen if your remove that node? Think about it. $\endgroup$ – noman pouigt Dec 4 '17 at 17:40
1
$\begingroup$

Simply apply Strongly connected components algorithm , Kosaraju's algorithm has complexity $O(m+n)$. Now, read through the SCC components and check if $v$ is part of a component with size $\geq$ 2. The second step is $O(n)$. Actually, the second step can be interleaved with the first step to get your required complexity result.

A simpler algorithm may be just to to use DFS on the graph. Have a look at Cormen's Introduction to algorithms, chapter 22. Your exact problem is solved there using DFS.

$\endgroup$
  • $\begingroup$ I don't know this algorithm... and I can't use it, is there anything more simpler? $\endgroup$ – Lola1984 Dec 4 '17 at 2:45
  • $\begingroup$ actually, this is a very simple algorithm, it applies BFS exactly twice, check it out here-:geeksforgeeks.org/strongly-connected-components $\endgroup$ – csTheoryBeginner Dec 4 '17 at 2:47
  • $\begingroup$ also, check my comment edit on using DFS in the answer. $\endgroup$ – csTheoryBeginner Dec 4 '17 at 2:49
  • $\begingroup$ @csTheoryBeginner just remove the node and check if the connected nodes to the removed node are connected via a different path. Suppose 'b' and 'c' are connected to deleted node 'a' so after a is removed we just need to check if there is a path between 'b' and 'c'. In the case 'a' is part of cycle then 'b' and 'c' will be connected otherwise no. Connection between 'b' and 'c' can be checked via dfs or bfs. $\endgroup$ – noman pouigt Dec 5 '17 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.