Graphs Exercises

Graph Basics

  1. Identify as many of the graph terms as you can that apply to the following graph:
    CS-Software Systems Prerequisites Graph
  2. Discuss with your neighbors the advantages and disadvantages of storing the above graph with each of the following:
    • Adjacency list
    • Adjacency matrix
    For each implementation, how could you store the vertex labels? How could you store weights?
  3. Given the following graph, draw the resulting:
    • Adjacency list
    • Adjacency matrix
    EXSC Undergraduate Prerequisites graph
  4. Discuss with your neighbors the advantages and disadvantages of performing the following common operations on graphs for each implementation:
    1. Determine whether there is an edge from vertex i to vertex j
    2. Find all vertices adjacent to a given vertex i
    3. Find all vertices adjacent from a given vertex j

Graph Traversals

  1. List the vertices in the order that the respective search will visit them (starting with vertex A):
    • Depth-first search
    • Breadth-first search

Topological Sorting

  1. Given the list of directed edges below, draw the directed graph: 
    CPSC_1301K -> CPSC_1302K
CPSC_1301K -> CPSC_2105 
CPSC_1301K -> CYBR_2159 
CPSC_1302K -> CPSC_2108 
CYBR_2159 -> CYBR_2160
MATH_1113 -> CPSC_1302K
MATH_1113 -> MATH_2125
MATH_2125 -> CPSC_2105
MATH_2125 -> CPSC_2108
  2. For this graph, determine the topological order. The two main algorithms to do this are:
    1. Iteratively look for a vertex that has an outdegree of 0 (it has no successor) and add it to the front of a list
    2. Iteratively look for a vertex that has an indegree of 0 (it has no precessor) and add it to the end of a list
    After producing the topological order with one of the above algorithms, then repeat the exercise using the other algorithm.

Shortest Paths

  1. Interpret the vertices below as cities and the edges as the cost to lay down fiber optic cable. Calculate the cost from A to each city for the following graphs:

Spanning Trees

  1. For each of the following trees, calculate a DFS spanning tree and a BFS spanning tree (starting at A):
  2. Interpret the vertices below as cities and the edges as the cost to lay down fiber optic cable.
    What is the least cost to connect every city (starting with city A) for each graph?
    Draw all of the edges that are part of the solution.

Euler Circuits

Do the graphs below have Euler circuits (each starting at vertex A)?
If so, list the vertices in the order visited.
1 2 3

Last Modified: