Problem Set: Graphs

1. For each of the graphs shown above, give the adjacency matrix and adjacency list.
   
   
2. For each of the graphs shown above, show the order in which the vertices will be visited in a depth first search. Start the search at vertex A. If there is a choice, visit the vertices in alphabetical order.
   
   
3. For each of the graphs shown above, show the order in which the vertices will be visited in a breadth first search. Start the search at vertex A. If there is a choice, visit the vertices in alphabetical order.
   
   






 



 

4. For each of the graphs shown above, show the order in which the vertices will be visited in a depth first search. Start the search at vertex 1. If there is a choice, visit the vertices in increasing order.
   
   
5. For each of the graphs shown above, show the order in which the vertices will be visited in a breadth first search. Start the search at vertex 1. If there is a choice, visit the vertices in increasing order.
   
   

For each of the following graphs, find and draw the MST that will be generated by Kruskal's algorithm and by Prim's algorithm

6.  

   

7.  

   

8.  

   

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2017