Graphs Exercises

Graph Traversals

  1. For each graph, list the vertices in the order that the respective search will visit them (starting with vertex A):
    • Breadth-first search
    • Depth-first search
    Graph 1:
    graph A -- B; A -- C; A -- I; B -- D; D -- G; G -- H; C -- E; C -- F; H -- I; I -- J;
    Digraph 1:
    graph A -> B; A -> C; A -> I; B -> D; D -> G; G -> H; C -> E; C -> F; H -> I; I -> J;
    Graph 2:
    graph A -- B; A -- D; A -- E; B -- C; B -- E; B -- F; C -- F; D -- E; E -- F;
  2. For Graph 1 and Digraph 1 (above), list the vertices in the order that the respective search will visit them (starting with vertex C):
    • Breadth-first search
    • Depth-first search
  3. Write pseudo code for each of the searches below:
    • Breadth-first search
    • Depth-first search
  4. Algorithm Efficiency
    1. What are the following Big Os?
      Search Adjacency List Adjacency Matrix
      Breadth-first    
      Depth-first    

    5. Topological Sorting

    1. Assume that you are getting ready for a date. Given the list of activities below, determine an ordering to accomplish all of the tasks: Possible graph
      • Activity
      • Buy flowers
      • Dinner
      • Dress & groom
      • Make dinner reservations
      • Pick-up date
      • Select activity
    2. Given the following digraph, produce a topological order:
      Digraph with the following edges: MATH_1113 -> MATH_2125; CPSC_1301K -> CPSC_1302K; MATH_1113 -> CPSC_1302K; CPSC_1301K -> CPSC_2105; MATH_2125 -> CPSC_2105; CPSC_1301K -> CYBR_2159; CYBR_2159 -> CYBR_2160;
    3. Describe three algorithms to determine a topological order:
    4. For each of the above algorithms, what is the Θ:
      1. Θ( )
      2. Θ( )
      3. Θ( )

    Last Modified: