Goals • to implement graph and tree data structures, and to understand the performance of
their traversals
Requirements
and Notes • Develop several of your own implementations of an undirected graph.
The @ile graphs1.txt contains data describing multiple undirected
graphs. Read it and create three versions of each graph:
1. as a matrix
2. as an adjacency list
3. as linked objects
For each graph, print the matrix and adjacency list versions. For the
linked objects version of each graph, perform depth-@irst and breadth-
@irst traversals, printing each vertex’s IDs as you encounter it. (I.e., print
all of the vertex IDs in “depth-@irst” order and then in “breadth-@irst”
order.)
• Develop your own implementation of a binary search tree. Using the
text @ile magicitems.txt from our web site, populate your BST with
that data.
• Randomly select 42 magic items and look up each in the BST. Print the
number of comparisons for each lookup and compute the overall
average.
• In your LaTeX summary and analysis document, analyze the asymptotic
running time of both graph traversals and explain why it is that way.
Also analyze the asymptotic running time of BST lookups and explain
that as well.
Of course, your code must …
• separate structure from presentation.
• be professionally formatted yet uniquely yours (show some personality)
• use and demonstrate best practices.
• make me proud to be your teacher.
[−∞ if not]
Resources • Graphs are described in our text in section 22.1 on via notes linked from our web page.
• Breadth-@irst and depth-@irst traversals are described in our text in sections 22.2 and
22.3 respectively.
• Trees are described in our text in chapters 12, 13, and 18.
