CPS 100, Spring 2004, Recitation

1. Consider the graph given by the following adjacency matrix (blank entries indicate missing edges):

   6	1		0	17	3
   1			2	3	8
   		3			2
   0	2		17	5	3
   17	3		17	5	3
   3	8	2	3	3

   What is the resulting Minimum Spanning Tree produced by Prim's Algorithm?

2. Given the functions in tgraph.h, write a function, getEdges, that creates an adjacency matrix for a graph.

   void getEdges(const Graph & g, tmatrix &adj)
   // pre: g is Graph with g.vertexSize() > 0
   // post: adj is adjacency matrix for graph g 
   //      if there is an edge from vertex i to vertex j
   //      in g with weight w, then adj[i][j] == w
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

3. In word ladder and in class, we have used Breadth-First Search to find the shortest path between vertices in an unweighted graph. In an unweighted graph, the shortest path from vertex i to vertex j is measured by the number of edges in the path.

   We can use BFS to find the shortest path between nodes in an unweighted graph. How? How is Dijkstra's algorithm an improvement over your algorithm?