EECS 215
Homework 4
Due Thursday Week 6 or 7
- Always write the time-complexity (in Big Oh notation)
in a comment next to every major algorithm you implement in this homework.
- (33 points)
Implement either Prim's or Kruskal's algorithm to find the Minimum
spanning tree of a given input graph. The input should be of a format:
10
1 2 23
1 3 44
...
10 3 18
Where the first number N (10 in this example) is the number of vertices.
The vertices are numbered from 1 to N. The following lines in the form
u v w declare the undirected edges between vertices u and v to be of
weight w.
- (33 points)
Implement your choice of algorithm (from the single source shortest
path algorithms) to find the shortest paths to all
nodes for the input graph starting from vertex 1. Assume the graph
is given in the same format described above.
- (34 points)
Implement your choice of algorithm (from the all-pairs shortest path
algorithms) to find the all pairs shortest path
on the input graph. Assume the graph is given in the same format
described above.
- Test your program on some sample graphs and convince
yourself they are correct.
What to submit:
- Email me your source code and either an execution
script, a screen shot, or output file that
shows your program works as described above. Also include your input for
testing. Please use "zip" and not
"rar" to combine it all together if you decide to wrap it all into one file.