22.3. Cycles in Graphs

Try these first

1. 1.

   Define what a graph is.

   Hint

   Think about a diagram of points and connections.

2. 2.

   What does BFS stand for?

   Hint

   Consider the order in which it's used to explore a graph.

3. 3.

   What is the primary use of BFS?

   • To explore depth first
   • To find paths level by level
   • To mark all vertices

   Hint

   Consider what happens with layers of a graph.

4. 4.

   True or False: A cyclic graph cannot have any loops.

   • True
   • False

   Hint

   Think about connections that allow returning.

5. 5.

   Create a directed graph with at least five vertices, ensuring there’s one cycle. Run DFS and document the order of visits and any cycles detected.

   Hint

   Remember to keep track of each vertex’s pre and post numbers.

6. 6.

   In a given graph structure, identify critical edges that, when removed, would disconnect the graph. Provide evidence for your findings.

   Hint

   Consider what happens to connectivity if certain paths are eliminated.