Prim's algorithm for minimal spanning tree

MHB
Thread starter LearnerJr
Start date Nov 20, 2016
Tags

Algorithm Tree

In summary, Prim's algorithm is a greedy algorithm that finds the minimum spanning tree of a weighted undirected graph. It starts with a random vertex and adds the edge with the smallest weight that connects the tree to a new vertex, until all vertices are connected. The time complexity is O(V^2), but can be improved to O(ElogV) using a priority queue. Prim's algorithm differs from Kruskal's algorithm in that it starts from a starting vertex and is useful for dense graphs with a known starting point.

Nov 20, 2016

LearnerJr

Quite stuck on this how do i do this and how do i document each step?

Physics news on Phys.org

Nov 20, 2016

Prove It

Gold Member

MHB

LearnerJr said:

Quite stuck on this how do i do this and how do i document each step?

https://en.wikipedia.org/wiki/Prim's_algorithm

Nov 20, 2016

LearnerJr

Prove It said:

https://en.wikipedia.org/wiki/Prim's_algorithm

It says connected spanning subgraph. I am so confused . can I still use normal prim algorithm ??

Related to Prim's algorithm for minimal spanning tree

1. What is Prim's algorithm for minimal spanning tree?

Prim's algorithm is a greedy algorithm used to find the minimum spanning tree of a weighted undirected graph. This means it finds the subset of edges that connects all vertices in a graph with the minimum total weight.

2. How does Prim's algorithm work?

Prim's algorithm starts with a random vertex and then grows the minimum spanning tree by adding the edge with the smallest weight that connects the tree to a new vertex. This process is repeated until all vertices are connected and a minimum spanning tree is formed.

3. What is the time complexity of Prim's algorithm?

The time complexity of Prim's algorithm is O(V^2), where V is the number of vertices in the graph. This can be improved to O(ElogV) using a priority queue data structure.

4. What is the difference between Prim's and Kruskal's algorithm?

Both Prim's and Kruskal's algorithm are used to find the minimum spanning tree of a graph. The main difference is that Prim's algorithm grows the tree from a starting vertex, while Kruskal's algorithm sorts all the edges and adds them to the tree in order of increasing weight.

5. When should Prim's algorithm be used?

Prim's algorithm should be used when the graph is dense (has a large number of edges) and when a starting vertex is known. It is also useful when there are multiple disconnected components in the graph, as it can find the minimum spanning tree for each component separately.