2. (10 points) List the names of two different algorithms time complexities. for

Question

2. (10 points) List the names of two different algorithms time complexities. for finding the minimum spanning tree and their Algi: Time Complexity. - Alg2: Time Complexity The graph below shows that, there are multiple computers that each computer can possibly be linked to at most 4 other computers; the number on each edge represents the cost estimate for this possible link In order to determine which links should actually be built so that every computer is connected in a network with minimum cost, which algorithm is more efficient? Justify your answer: Apply the algorithm chosen above to this graph to find a minimum spanning tree. If the algorithm specifies a starting vertex, assume it is vertex a. Show the edge chosen at each step in order. UseaM represent the edge between vertes. x and vertexY. For example, b) represents the edge between vertex a and vertex b. Assume the start vertex is a if needed. Order Edge Chosen Edge Weight 2 10 Total weight of this MST is

Explanation / Answer

Alg1 :- Kruskal's Algorithm, Time Complexity : - O(E*log(V)), Here E is number of Edges and V is number of vertices.

Alg2 :- Prim's Algorithm, Time Complexity :- O(V^2), Here V is the number of Vertices.

Kruskal's Algorithm is more efficient. Since the maximum number of Edges = 4*n. Hence O(4*n*log(n)) is more efficient than O(n^2).

Total weight of MST = 33

Order Edge Chosen (x,y) Edge Weight 1 (a,b) 1 2 (g,k) 1 3 (e,i) 2 4 (i,l) 2 5 (a,c) 3 6 (b,e) 3 7 (e,f) 3 8 (a,d) 4 9 (g,h) 4 10 (h,i) 5 11 (i,j) 5

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.