- DATA STRUCTURES AND ALGORITHMS I on "Graphs"

1. Find an image of an object, for example:

2. On the image, identify a minimum of 7 points or vertices. For example:

3. Draw a connected graph based on these vertices using a minimum 7 edges. Label the vertices with letters If you have a very long name, use a maximum of 10 letters, labeled as letters and digits

[2 marks]

Remember each graph in the class must be UNIQUE. A duplicate will be rejected.

4. Write your set of vertices and edges as below: [1 marks]

V = { }

E = { }

5. Draw its Adjacency Matrix [3 marks]

6. Draw its Adjacency List (3 marks)

7. Show a traversal of the graph both traversal methods [7 marks]:

• Breadth-First Search (BFS)
• Depth First Search (DFS)

For both algorithms, you need to show the steps and draw the resultant BFS Tree and DFS Tree respectively.

8. Based on the graph you have made earlier in no 3, assign values as weights on all the edges where all the edges are of different weights.

Find the minimum spanning tree using any one of the two available algorithms for the Minimum Cost Spanning Tree. You need to show the calculation of the minimum cost [4 marks]

AS SOON AS POSSIBLE PLEASE

Transcribed image text