Skip to Content

COMP225 : Algorithms and Data Structures

Week 10

Objectives : to learn more about graphs. Reference Carrano Chapter 13.
  1. Consider the above graph :
    • How many vertices? How many edges?
    • Is the graph connected?
    • Does graph contain any cycles?
    • What is the degree of vertex B?
    • What is the maximum degree of any vertex in graph?
  2. (*)Draw the adjacency matrix for the above graph.
  3. Draw the adjacency list for the above graph.
  4. (*) Perform (trace) a Depth First Search starting at vertex A, displaying each vertex as it is visited. At each point where there is a choice, choose the vertex which is smallest alphabetically.
  5. (*) Perform (trace) a Breadth First Search starting at vertex A. At each point where there is a choice, choose the vertex which is smallest alphabetically.
  6. Considering the adjacency matrix representation, describe (in words) an algorithm for finding the degree of a given vertex.
  7. Considering the adjacency list representation, describe (in words) an algorithm for finding the degree of a given vertex.
All enquiries to Ros Ballantyne