Below is a high-level description of Kruksal\'s Minimum Spanning Tree Algorithm

Question

Below is a high-level description of Kruksal's Minimum Spanning Tree Algorithm for a Graph, G(V, E). Answer the questions assuming that |v| = n and that the average number of edges from any vertex is k, where k lessthanorequalto n. 1. Sort edges in E increasing cost order 2. Initialize each vertex in V as a single connected component 3. Loop Until Graph G is connected, add the cheapest edge which will connect two connected components. The joined components become a single connected component. a) Find and solve the mathematical model for the complexity of this algorithm b) Modify it so that it produces an arbitrary spanning tree. Write high level description c) Find and solve the mathematical model for the complexity of this modified algorithm.

Explanation / Answer

import java.util.Collections; import java.util.Comparator; import java.util.LinkedList; import java.util.List; import java.util.Scanner; import java.util.Stack; public class KruskalAlgorithm { private List edges; private int numberOfVertices; public static final int MAX_VALUE = 999; private int visited[]; private int spanning_tree[][]; public KruskalAlgorithm(int numberOfVertices) { this.numberOfVertices = numberOfVertices; edges = new LinkedList(); visited = new int[this.numberOfVertices + 1]; spanning_tree = new int[numberOfVertices + 1][numberOfVertices + 1]; } public void kruskalAlgorithm(int adjacencyMatrix[][]) { boolean finished = false; for (int source = 1; source

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

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