CS210 Tutorial 13

Complete the following exercises pasted below:

Q1. Given the following Edge List, draw a undirected Graph: (1,2) (2,3) (3,4) (4,5) (5,1) (6,8) (7,9) (6,9) (8,10) (7,10) (1,6) (2,7) (3,8) (4,9) (5,10)

Q2. Make an adjacency Matrix for the graph represented in Q1.

Q3. Give psuedocode for inserting an edge in a pre-existing adjacency list. Make sure this method runs in O(1) time.

Q4. Draw a graph for the following adjacency list.

vertex adjacent vertices
1 (2, 3, 4)
2 (1, 3, 4)
3 (1, 2, 4)
4 (1, 2, 3, 6)
5 (6, 7, 8)
6 (4, 5, 7)
7 (5, 6, 8)
8 (5, 7)

Q5. Give Sequence of vertices visited using DFS starting at 1.

Q6. Give Sequence of vertices visited using BFS starting at 1.

Q7. Give the following weighted undirected graph, find the BFS and DFS on the graph starting at vertex_4. Assume the lowest edge weight when looking for next note/vertex.

Q8. Given a square chessboard of 6 x 6 size with a Knight piece at position (1,3); What algorithm would you use BFS/DFS to reach the target T in least number of steps.