Graphs Exercises

   < Previous  Next >
  1. Identify as many of the graph terms as you can that apply to the following graph:
    CSCI Undergraduate Prerequisites graph
  2. Discuss with your neighbor 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 neighbor 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
  5. List the vertices in the order that the respective search will visit them (starting with vertex A):
    • Depth-first search
    • Breadth-first search

      6. Last Modified: