Why is edge A-B chosen first in the example?
Conditions
- Node A is the starting visited node.
- The algorithm follows the greedy rule of picking the minimum-weight crossing edge.
Reasoning, step by step
- Identify the current visited set: {A}.
- Examine all edges incident to A that lead to unvisited nodes.
- Compare the weights of these edges.
- Select the edge with the smallest weight, which is A-B.
- Add node B to the visited set.
Example
The narrator states, "Prim's is a greedy algorithm, so we're going to choose the smallest edge that connects to an unvisited node, in this case, A to B."
Common misconceptions
- Choosing the globally smallest edge in the entire graph, regardless of connectivity to the visited set.
- Selecting an edge that leads to an already visited node.
- Ignoring edge weights and choosing randomly.
Watch the explanation
Connected concepts
Explore next
Related questions
When multiple candidate edges share the same minimum weight, you can pick any one of them. The choice does not affect the validity of the greedy step, though it may lead to a different MST if edge weights are not distinct.
Conditions: Multiple edges connect the visited set to unvisited nodes.; These edges have identical minimum weights.
The time complexity of Prim's algorithm depends on the data structures used. Using an adjacency matrix with searching gives , while using a binary heap with an adjacency list gives , where is the number of vertices and is the number of edges.
Conditions: The graph is represented using specific data structures.; denotes the number of vertices.; denotes the number of edges.
Edge B-E is skipped because both of its endpoints (B and E) are already in the visited set (MST). Prim's algorithm only considers edges that connect a visited vertex to an unvisited vertex to avoid creating cycles.
Conditions: Both endpoints of the edge are already marked as visited.; The algorithm strictly follows the rule of adding only crossing edges.
No, the minimum spanning tree is not always unique. It is unique only if all edge weights in the graph are distinct.
Conditions: The graph is weighted.; Uniqueness is guaranteed only when all edge weights are pairwise distinct.
To start Prim's algorithm, create an empty list called 'visited' to track touched nodes, then pick an arbitrary starting node and add it to the visited list.
Conditions: The graph is weighted and connected.; You have a mechanism to track visited vertices (e.g., a list or set).
Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.