22.6.2. Critical Edges

Try these first

1. 1.

   Define what a graph is.

   Hint

   Think about what elements are needed to form a graph.

2. 2.

   What does BFS stand for?

   Hint

   Consider the order in which nodes are visited.

3. 3.

   What is the main purpose of BFS?

   • To traverse the graph level by level
   • To traverse deeper into the graph
   • Both of the above

   Hint

   Consider the structure of a tree as you think about traversal methods.

4. 4.

   True or False: A directed graph can have cycles.

   • True
   • False

   Hint

   Imagine following arrows along a path in a graph.

5. 5.

   Given the following undirected graph, write pseudocode to perform BFS to find all connected components.

   Hint

   Focus on marking nodes as you traverse.

6. 6.

   In a directed graph with back edges, devise an approach to identify all strongly connected components. Outline the steps in your solution.

   Hint

   Consider how the order of finished times can help in traversal.