Question
In the context of this exercise, what is a cycle in a graph?
Answer
A cycle is a path of vertices and edges where you can start from a vertex and follow the path all the way back to that starting vertex. These cycles only occur for directed graphs.
For example, the following graph will contain a cycle:
graph = {
'A': ['B'],
'B': ['C'],
'C': ['A']
}
In this graph, there is a cycle formed by the path A -> B -> C
, back to A
.
Cycles are sometimes harmless, but other times they can cause bugs in graph algorithms due to infinite looping.