1. This is taken from Spring 2013 mid-term 2 question 3. This is a different gre
ID: 3705238 • Letter: 1
Question
1. This is taken from Spring 2013 mid-term 2 question 3. This is a different greedy algorithm of finding a minimum-cost tree that spans an undirected graph G(V,E), i.e., a tree that contains all nodes in the graph, and the tree edges connecting all the nodes have the least total weight. The basic idea is to process the edges in a non-increasing order. For each edge, we ask whether the removal of the edge will result in a disconnected graph. If the graph remains connected after the removal, the edge can be safely discarded from the minimum-cost spanning tree. Otherwise, the edge should be kept in the minimum-cost spanning tree. The pseudo-code is given below. om ono Greedy-MST(G, V, E): 1. MST + G(V,E); /* MST is G to begin with */ Build a priority queue PQ of edges in E[G] using max-heap; while PQ is not empty { eExplanation / Answer
i) The orderirng of edges after down heapify the sequence of ordering of edges will be :
(a,e), (d,e), (c,d), (a,b), (e,f), (b,f), (a,f), (b,c), (d,f), (b,d)
heapify take place on following places:
ii) deque operartion can be implemented in following way
Dequeue(q[],size)
temp q[1]
swap(q[1],q[size)
size size-1
downword_heapify(q,1,size)
return temp;
Time complexity for single element i will take height of heap O(log n) where n is number of element in heap. To process all element of heap it will take O(nlog n).
iii.
DFS(G)
1 for each vertex u ? V[G]
2 do color[u] ? WHITE
3 count? 0
4 time ? 0
5 for each vertex u ? V[G]
6 do if color[u] = WHITE
7 then DFS-VISIT(u)
8. count? count+1
9 if count>0
Then return 1 // disconnected
10 return 0 //connected
iv)
Time complexity of line2 is O(E log E).
Time complexity of line4 is O(log E).
Time complexity of line2 is O(E+V).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.