What is a cycle in a graph?


#1

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.