Department of Computing

Local Navigation

• Comp Home
• COMP225 Home
Blackboard

Week 10

Objectives : to learn more about graphs. Reference Carrano Chapter 13.

1. * Draw the adjacency matrix for the above graph.
2. * Draw the adjacency list for the above graph.
3. * Perform a Depth First Search starting at vertex A. At each point where there is a choice, choose the vertex which is smallest alphabetically.
4. * Perform a Breadth First Search starting at vertex A. At each point where there is a choice, choose the vertex which is smallest alphabetically.
5. Construct the DFS spanning tree.
6. Construct the BFS spanning tree.
7. Construct a minimum spanning tree using Prim's algorithm.
8. Construct a minimum spanning tree using Kruskal's algorithm.
9. Discuss the relative efficiency of Prim's versus Kruskal's algorithm.

All enquiries to Ros Ballantyne