
A graph is an ordered pair, G = (V,E), where V is a set of vertices and E = {{u,v}  u ε V and v ε V} is the set of Edges.
More precisely, E is a collection of subsets of V, each of size 2, and the elements of E are called edges.
We will start be defining the class of Graph objects. This class will store V and E as sets. The vertices can be any kind of immutable object. The edges in E will be ordered pairs (tuples) of vertices. Tuples have the advantage of being immutable objects. This use of immutable objects will allow us to implement the several of the methods of the Graph class using Python's extremely efficient Dictionary class.
A Graph will own the sets V and E which define it. By using the set class for V and E we eliminate the concern about multiple copies of a vertex. It is also that case that a tuple (u,v) cannot be accidentally stored more than once, but we will need to avoid accidentally storing both (u,v) and (v,u). A Graph will also own a Dictionary called Adj, which is a particularly efficient data structure for algorithms that would naturally exploit the relationships stored in the Adjacency matrix. It also provides an efficient record of the degree for each vertex. V, E, and Adj are not treated as private objects so that we can directly explore possible algorithms which use them.
In HW13 we introduced the initial version of the Graph class which was very limited while we began to explore methods to be added to the class. Methods which are both relevant to the effective use of Graphs and capable of being efficiently implemented. In that homework we developed a code for plotting a graph and two codes for determining if a graph is connected. One approach was a recursive code that used a depthfirst search. The second approach used a queue and a breadth first search. The Graph class in this homework incorporates what we learned by including methods for plotting the graph, for determining whether the graph is connected, and for creating a list of the components of the graph. These last two methods are based on the breadthfirst search algorithm, which requires that we include the code for the Queue class.
Be sure to check out this new Graph class by doing tab completion on one or more of the Graph objects that you create.

A Queue Class
The following block defines a queue class with five methods  enqueue, dequeue, peek, clear, and display. However, instead of following the Stack class approach and having this own a private deque object, this queue is a subclass of the deque class. So this queue object is a deque. One consequence is that this queue object will inherit the methods of the deque class, which includes the clear method. This can be confirmed with the tab completion in the block following the definition of the Queue class.





Trees
A Tree is a connected acyclic graph. Connected means that there is a path between every pair of vertices. Acyclic means that there are no cycles.
It is straightforward to show by induction that if a tree has $nV$ vertices, then it has exactly $nV1$ edges.
Both the depthfirst and breadthfirst algorithms for determining whether a graph is connected are actually building a tree, which, when the graph is connected, is a spanning tree of the graph. In the while loop of the is_connected method we dequeue a vertex, u, from the queue which is part of the connected component. Note that all vertices are marked as visited immediately before being enqueued. We then check to see if vertex, u, has any adjacent vertices, v, which have not been visited. If we find one we mark it as visited and enqueue it. To build the spanning tree all we need to do at this stage is to add the edge (u,v) to the list of edges. It makes sense to give this list of edges the name, tree, since it will always be a tree. Every vertex that is selected is adjacent to a vertex that is already in the growing tree, so the tree is connected. Also since it has not been visited, adding this edge can not create a cycle.
Exercise 1: Complete the function, build_spanning_tree, then run the following three blocks.




Exercise 2: Define and display a graph with 6 vertices and 5 edges which is not a tree.



Since G3 has 26 vertices and 25 edges and is connected, it is a tree. However, we almost always draw a tree as a rooted tree, with the root at the top and the leaves at the bottom.
A Rooted Tree is a tree with a distinguished vertex called the root. This induces an ordering relationship on the vertices, which is often referred to as a parentchild relationship. The root represents the first generation, all the vertices directly connected to the root by an edge in the graph are the children of the root, the second generation. Similarly any vertex, other than the root, which is connected to a second generation vertex by an edge is a child of that vertex, a member of the third generation, and so forth. Any vertex which does not have a child is called a leaf. Thus every vertex except the root has a single parent, and any vertex which is not a leaf will have one or more children.
If a graph is a tree, then we can choose any vertex as the root. The following depthfirst prefix tree walk displays the rooted tree with the explicit parent child relationship indicated by the level of indentation.


An important question to ask about this routine is what does it do if applied to an arbitrary graph.
Exercise 3: The following two blocks display G1 and G2 with the trees constructed by the build_spanning_tree routine. Add code after each display, which will invoke the print_tree_df for the appropriate graph with 'A' as the root. Then briefly discuss whether the two trees rooted at 'A' are the same and if not why not. It may be quite helpful to review the graphic displays generated by Exercises 2 and 3 in HW13.



Exercise 4: A binary tree is a tree where the degree of each vertex is less than or equal to 3. Write a short code that determines whether G3 is a binary tree.

A rooted binary tree is a rooted tree in which every vertex has 0, 1, or 2 children.
Exercise 5: With Alice as the root, the binary tree, G3, is not a rooted binary tree. Briefly explain why. Then choose a node for the root which does produce a rooted binary tree and display the indented depthfirst print out of G3 with that root.


Minimum Weighted Spanning Tree
If we include a weight for each edge, then we can make a simple modification to the build_spanning_tree algorithm to obtain Prim's algorithm for finding a Minimum Weighted Spanning. This is a greedy algorithm that will find a spanning tree where the sum of the weights on the edges is minimized. That is, the sum of the weights on the edges of the tree found by Prim's algorithm will be less than or equal to the sum of the weights on the edges of any other spanning tree.
The essential step is to replace the queue, which stores the vertices that have been added to the component, with a priority queue, which contains the edges (prioritizedby their weights) that cross the boundary of the component. The code for Prim's algorithm contains three print statements to provide some insight into how the algorithm behaves.

A priority queue is a container where each item is inserted with a certain priority. When an item is removed, the item with the highest priority is the item that is removed. Priority queues can be implemented using a heap. A heap is a Complete Binary Tree with a partial ordering. A complete binary tree is a binary tree where the tree is filled out from top to bottom, left to right. To be a heap, the complete binary tree must satisfy the following partial ordering criteria.
The priority of the parent must always be equal to or higher than the priority of its children.
This is often referred to as the heap property. The heap property is an invariant which must be true before and after pushing or popping an item.
There is a natural embedding of a complete binary tree into an array using the functions
The following version of the Priority Queue makes the bubbleup and siftdown routines explicit, so that it is possible to extend the class to allow for changes in the priority and other features that are important for discrete event simulation.


Exercise 6: Briefly discuss why the edge (A,E) made it to the top of the Priority Queue, but did not end up in the MST.

The Prime Maze Graph
The following blocks define and display the Prime Maze Graph.



Exercise 7: Using the Prime Maze Graph, PMG, and its weights, WPM, find the minimum weighted spanning tree using the Prim function. You should feel free to comment out the statement in the Prim function that prints the Priority Queue. Using a copy of Gpm, the plot for the Prime Maze Graph, superimpose a plot of the resulting tree with the edges drawn in red.


