Lab # 7 Graphs Solution



1. Using the draw tree method for binary search trees as guide, write a method to display an unweighted undirected graph given its adjacency list representation. An easy way to do this is to view the vertices as points in a circle, separated by equal angles, and then draw edges as straight lines joining these points. The following images show examples of complete graphs (graphs where all different vertices are connected) drawn using this strategy:

3 vertices 5 vertices 3 vertices)

2. For Lab 6 you implemented a program to group words based on their similarities. Your task for this lab is to implement Kruskal’s algorithm to find the Minimum Spanning Tree of the graph that represents the words in Lab6Words.txt and their embeddings. For input to your method, build an edge list representation of the graph, where vertex i represents word wi , and the cost of edge (i, j) is given by sim(wi , wj ).

As usual, write a report describing your work.