CS210 Tutorial 14

Complete the following exercises pasted below:

Q1. Draw the directed graph that corresponds to this adjacency matrix:

Q2. Draw the edge list that correspond to the graph from the previous question.

Q3. Given the following graph, in what order are the vertices visited for a depth-first search that starts at 0? In what order are the vertices visited for a breadth-first search that starts at 0?

Q4. Show the adjacency list of the graph given in the previous question.

Q5. Consider the highest weighted edge for choosing the next vertex; do a DFS on this graph starting at 7

Q6. Show the result of Breadth First Search on the above directed weighted graph.Consider the lowest weighted edge for choosing the next vertex. Start at 1.

Q7. Bob loves foreign languages and wants to plan his course schedule for the following years. He is interested in the following nine language courses: LA15, LA16, LA22, LA31, LA32, LA126, LA127, LA141, and LA169. The course
prerequisites are:

• LA15: (none)
• LA16: LA15
• LA22: (none)
• LA31: LA15
• LA32: LA16, LA31
• LA126: LA22, LA32
• LA127: LA16
• LA141: LA22, LA16
• LA169: LA32
In what order can Bob take these courses, respecting the prerequisites?