This question asks about Prim\'s algorithm which is used to find the minimun spa

Question

This question asks about Prim's algorithm which is used to find the minimun spanning tree of a graph.

a) What is the problem that Prim's algorithm is trying to solve? What is the end output of the algorithm? Is this output a precise/best solution or is it only an approximation?

b) In broad terms, how does the algorithm work? (No code needed in the explanation). Be as thorough as possible in your explanation.

c) Using the description you gave from b), what is the runtime complexity of Prim's algorithm and why.

Explanation / Answer

a)

Prim's algorithm to find minimum cost spanning tree (as Kruskal's algorithm) uses the greedy approach.

Prim's algorithm shares a similarity with the shortest path first algorithms.

Prim's algorithm, in contrast with Kruskal's algorithm, treats the nodes as a single tree and keeps on adding new nodes to the spanning tree from the given graph

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weightedundirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this 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.

Prim's algorithm is not the best approximation algorithm kruskal is best approximation algorithm

Kruskal's algorithm will grow a solution from the cheapest edge(minimum weight) by adding the next cheapest edge, provided that it doesn't create a cycle

In Prim's, you always keep a connected component, starting with a single vertex. You look at all edges from the current component to other vertices and find the smallest among them. You then add the neighbouring vertex to the component, increasing its size by 1. In N-1 steps, every vertex would be merged to the current one if we have a connected graph.

psuedo code

Associate with each vertex v of the graph a number C[v] (the cheapest cost of a connection to v) and an edge E[v] (the edge providing that cheapest connection).

To initialize these values, set all values of C[v] to any value which is larger than the maximum edge weight) and

set each E[v] to a special value indicating that there is no edge connecting v to vertices
Initialize an empty F and a set Q of vertices that have not yet been included in F (initially, all vertices).
Repeat the following steps until Q is empty:
Find and remove a vertex v from Q having the minimum possible value of C[v]
Add v to F and, if E[v] is not the special flag value, also add E[v] to F
Loop over the edges vw connecting v to other vertices w

. For each such edge, if w still belongs to Q and vw has smaller weight than C[w], perform the following steps:
Set C[w] to the cost of edge vw
Set E[w] to point to edge vw.

complexity

if using adgency matrix o(|v^2|)

if the input graph is represented using adjacency list, then the time complexity of Prim’s algorithm can be reduced to O(E log V) with the help of binary heap

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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