0
$\begingroup$

I am trying to find all the cycles in an undirected graph given the adjacency list of the vertices, with the an output of all the cycles in form of the vertices they are made up of.

For example -https://i.stack.imgur.com/Ku4fd.jpg

The example depicts the graph drawn by the adjacency list with desired cycles result

1 235
2 134
3 1245
4 235
5 134

The output from the algorithm would be

Cycles:
1 2 3
1 3 5
2 3 4 
3 4 5

Note that I am not trying to find ALL possible cycles in the graph but rather all the loops. We assume for this problem that there any vertex is connected to at least 2 others

I am new to discrete maths, algorithms and graph theory, any help would be greatly appreciated.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Does "loops" mean "sequences of vertices ​ v$_0$ v$_1$ v$_2$ ... v$_{L\hspace{.02 in}-1\hspace{-0.02 in}}$ v$_L$ ​ such that ​ [ v$_0$ = v$_L$ ​ and that sequence ​ ​ ​ ​ has no other repetitions and for all elements i of {0,1,2,3,...,L-2,L-1}, there is an edge from v$_i$ to v$_{i+1}$"$\hspace{.02 in}$? ​ ​ ​ ​ ​ ​ ​ ​​ $\endgroup$
    – user12859
    Apr 17, 2016 at 19:22
  • $\begingroup$ Yes, a loop is essentially a sequence of vertices that starts from vertex i and comes back to vertex i that does not enclose any other sequences starting and finishing at vi $\endgroup$
    – Seb Hill
    Apr 17, 2016 at 19:45
  • 1
    $\begingroup$ (That's different from what I was guessing.) ​ Is "enclose" in the sense of a planar embedding, or just vi not also being an internal vertex? ​ ​ ​ ​ $\endgroup$
    – user12859
    Apr 17, 2016 at 19:50
  • 1
    $\begingroup$ It's not clear what you are asking for. In the first sentence, you say you want to find all cycles. Later you say you don't want to find all cycles; you want to find all loops. You never define what you mean by a loop. Please edit the question to provide a precise specification/definition of what you want and what you mean by a loop; as it stands, the question is not answerable, as it's not clear what you are looking for. $\endgroup$
    – D.W. ♦
    Apr 18, 2016 at 5:10
  • 1
    $\begingroup$ Also posted on SO. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W. ♦
    Apr 18, 2016 at 5:14

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.