CSS 220 SXU The Total Weight Along the Hamiltonian Circuit Questions

CSS 220 Module 8 Homework
Kruskal’s algorithm – is a Minimum Spanning Tree algorithm which finds an edge of
the least possible weight that connects any two trees in the forest.
Prim’s algorithm – The algorithm operates by building the Minimum Spanning Tree
one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest
possible connection from the tree to another vertex.
Binary Tree Traversals
In-order Traversal – Left, Root, Right
Pre-order Traversal – Root, Left, Right
Post-order Traversal – Left, Right, Root
1.
Consider the graph given above. Use the nearest neighbor algorithm to find the
Hamiltonian circuit starting at vertex A.
a) List the vertices in the Hamiltonian circuit in the order they are visited. Do not
forget to include the starting vertex at both ends.
b) Calculate the weight of the circuit.
2.
Consider the graph given above. Use the nearest neighbor algorithm to find the
Hamiltonian circuit starting at vertex O.
a) List the vertices in the Hamiltonian circuit in the order they are visited. Do not
forget to include the starting vertex at both ends.
b) What is the total weight along the Hamiltonian circuit?
3.
Consider the graph given above. Use Kruskal’s and Prim’s algorithms (for Prim start at
J) to find the minimum spanning tree.
a) For each algorithm provide the edges in the order they were selected.
b) What is the total weight of the spanning tree?
4. Create the binary search tree representation of the following list: 22,8,41,34,5,20.
Then perform in-order traversal of the tree. What do you get?
5. Perform in-order, pre-order, and post-order traversal on the tree below. List out the
sequence of values for each traversal.
6. Perform post-order traversal on this arithmetic expression tree. What is the resulting
value?
7. Consider the following graph:
Which one of the following can NOT be the sequence of edges added to the
minimum spanning tree using Kruskal’s algorithm?
a. (b,e)(e,f)(a,c)(b,c)(f,g)(c,d)
b. (b,e)(e,f)(a,c)(f,g)(b,c)(c,d)
c. (b,e)(e,f)(b,c)(a,c)(f,g)(c,d)
d. (b,e)(a,c)(e,f)(b,c)(f,g)(c,d)