CODEWITHSUNDEEP
algorithmgraph
L Lawliet
L Lawliet

Reputation: 2625

Algorithm to a minimum cycle including a particular vertex

I was searching for an algorithm that could find a very basic (i.e. the shortest) cycle that includes a given vertex.

In other words, if a vertex v1 participates in two cycles say one with v1, v2, v3 and the other v1, v2, v4, v5, v6. I want the algorithm to give me v1, v2, v3 cycle as the output.

Does anyone know which algorithm would do that?

Also, what could be the complexity of this algorithm.

Thanks in advance.

Upvotes: 1

Views: 83

Answers (1)

Grigor Gevorgyan
Grigor Gevorgyan

Reputation: 6853

Start a bfs from the given vertex v0. Stop as soon as bfs considers a vertex v1 adjacent to v0, and v0 is not parent of v1 in bfs tree. The found path from v0 to v1 plus (v1,v0) edge is your shortest cycle. Complexity is O(n+m) due to bfs.

Upvotes: 3

Related Questions