Page 297 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Minimum Spanning Tree: A minimum spanning tree or minimum weight spanning tree is then a
spanning tree with weight less than or equal to the weight of every other spanning tree.
Kruskal’s algorithm: Kruskal’s algorithm is an algorithm in graph theory that finds a minimum

spanning tree for a connected weighted graph.
14.6 Self Assessment

State whether the following statements are true or false:

1. Network flow is an advanced branch of graph theory.
2. Kruskal’s algorithm is an algorithm in graph theory that fi nds a minimum spanning tree
for a connected weighted graph.

3. Kruskal’s algorithm is not an example of a greedy algorithm.

4. Prim’s algorithm is an algorithm in graph theory that finds a minimum spanning tree for a
connected weighted graph.
5. A graph may not have many spanning trees.
Fill in the blanks:
6. Prism algorithm was discovered in 1930 by mathematician .....................
7. ......................... developed some examples on which the running time is based.

8. A ......................... can solve it in linear expected time.
9. Kruskal’s algorithm is an algorithm in graph theory that fi nds a minimum spanning tree
for a connected ..................... graph.
10. Prism’s algorithms sometimes called the ............................

14.7 Review Questions

1. What do you mean by network fl ow?
2. Explain Ford Fulkerson’s method of network fl ow.
3. What do you mean by minimum spanning tree?
4. Describe proof of correctness of Kruskal’s algorithm
5. Explain prim’s algorithm

6. Dijkstra’s algorithm to compute a minimal spanning tree in a network works by considering
all edges in any convenient order. As in Kruskal’s algorithm, we select edges for a spanning
tree, by adding edges to an initially empty set. However, each edge is now selected as
it is considered, but if it creates a cycle together with the previously selected edges, the
most expensive edge in this cycle is deselected. Prove that the edges chosen by Dijkstra’s
algorithm also form a minimal spanning tree of a connected network.
7. Kruskal’s algorithm to compute a minimal spanning tree in a network works by considering
all edges in increasing order of weight. We select edges for a spanning tree, by adding
edges to an initially empty set. An edge is selected if together with the previously selected
edges it creates no cycle. Prove that the edges chosen by Kruskal’s algorithm do form a
minimal spanning tree of a connected network.
8. Explain how Prim’s algorithm for minimal spanning trees differs from Kruskal’s
algorithm.

292 LOVELY PROFESSIONAL UNIVERSITY