Prim's Algorithm (AS)

Prim’s Algorithm (AS)

Basics

• Prim’s Algorithm: A technique used in graph theory to find a minimum spanning tree for a connected weighted graph.
• It starts with a single node and expands the tree one edge at a time, always choosing the next edge that provides the smallest increase in total weight.

Detailed Steps

• initial Setting: begin at any arbitrary node and add this to your ‘tree in construction’.
• Addition of new nodes and edges: Identify all the edges that connect your current tree to nodes not yet in the tree. Choose the edge with the smallest weight and add this to your tree.
• Repeat Until Complete: Repeat this process until all nodes are included in your tree.

Frequenty Made Mistakes

• It’s important not use a cut (a partition of the vertices of a graph into two disjoint subsets) that disconnects the graph.
• Edge weight: If two edges have the same weight, you can choose either

Solving Problems

• Prim’s Algorithm works best: when you need to solve problems related to network design.
• Examples include: telephone, electrical wiring, computer data spanning trees where we are interested in a way to connect all points together while keeping the cost as low as possible.