Summary of "Prim's algorithm in 2 minutes"

Summary of "Prim's Algorithm in 2 Minutes"

Main Ideas and Concepts:

Prim's Algorithm Purpose: Prim's Algorithm is used to find a Minimum Spanning Tree (MST) in a graph, which is a connected graph with the minimum total edge weight and no cycles.
Greedy Approach: The algorithm follows a greedy strategy by always selecting the smallest edge that connects an unvisited node to the growing MST.

Step-by-Step Methodology:

Initialize:
- Create an empty list called visited to track nodes that have been added to the MST.
Start Node:
- Choose an arbitrary starting node (e.g., node A) and add it to the visited list.
Examine Reachable Nodes:
- Look at all vertices connected to the current node (A) using edges (shown with blue edges).
Select Smallest Edge:
- From the current node, choose the smallest edge that connects to an unvisited node. For example, from A to B.
Update Visited List:
- Add the newly connected node (B) to the visited list.
Repeat:
- Continue the process of examining reachable nodes and selecting the smallest edge connecting to an unvisited node:
- If multiple edges have the same weight, you can choose any of them.
- Avoid edges that connect nodes already in the MST.
Completion:
- Repeat until all nodes are included in the MST.
- If all edge weights are distinct, the resulting MST will be unique.
Calculate Total Weight:
- Sum the weights of the edges in the MST to find the total edge weight.