Michael Sambol · YouTube · 2:16
This 120-second whiteboard lesson introduces Prim's algorithm as a greedy method for building a minimum spanning tree. After defining an MST as a minimum-weight connected acyclic spanning subgraph, the presenter runs the algorithm on a 7-vertex weighted graph with vertices A through G. The Visited set starts empty, vertex A is chosen arbitrarily, and the algorithm repeatedly adds the cheapest edge crossing from visited to unvisited vertices. The worked example selects A-B, A-C, C-E, A-D, C-F, and F-G, explicitly rejecting B-E because both endpoints are already in the tree. The final MST has total edge weight 24. The clip closes by noting that Prim's time complexity depends on implementation: with adjacency matrix searching and with a binary heap plus adjacency list. This 16-second clip is the ending portion of a short lesson on Prim's algorithm. It first shows a handwritten summary of two running-time bounds: for adjacency-matrix searching and for a binary heap with adjacency lists. The video then switches to a typed pseudocode page for procedure prim(G,w), displaying the input/output specification, initialization of cost and prev, construction of a priority queue H, and the main loop that extracts a minimum-cost vertex and relaxes incident edges with decreasekey. The narration says the shown algorithm is fairly easy to implement and ends by hoping the viewer understood Prim's algorithm.
Use the learning inspector for key ideas and moments, or open the reading tabs for the complete notes.
Generated from the video's visuals and explanation; not verbatim speech.
The clip opens by naming the topic: Prim's algorithm. The board pairs the title with "Minimum Spanning Tree (MST)", and the narration states that the algorithm produces a minimum-weight connected graph with no cycles. This establishes both the method and the target object before any computation begins.
A weighted example graph with vertices A through G is shown, along with the initial state Visited = { }. The narrator explains that this visited collection records which nodes have already been touched, so the viewer sees the algorithm's bookkeeping structure before the first choice is made.
The next board simplifies the initialization to "Prim's = Pick a node". The narration then applies that rule by choosing A as the arbitrary starting vertex and adding it to Visited, turning the abstract first step into a concrete example state.
From A, the algorithm examines all incident edges and selects the cheapest one leading to an unvisited vertex. The chosen edge is A-B with weight 2, which is marked as part of the growing tree, and Visited becomes {A,B}. This demonstrates the central greedy rule of Prim's algorithm.
With {A,B} visited, several frontier edges have the same minimum weight 3. The narrator explicitly treats this as a tie and chooses A-C, updating Visited to {A,B,C}. The example then continues in the same manner, adding C-E with weight 1 and A-D with weight 3 as the tree expands.
At a later stage, edge B-E has weight 3 and looks attractive, but both endpoints are already in the MST. The video uses this moment to clarify the eligibility condition: only edges crossing from visited to unvisited vertices may be taken. Therefore B-E is skipped and C-F with weight 6 is selected instead.
Once only G remains unvisited, the algorithm attaches it through F-G with weight 9. The final red subgraph spans all seven vertices and contains six edges, matching the tree requirement. The narration then adds a theoretical note: if all edge weights are distinct, the MST is unique.
The completed edge set is used to compute the objective value. The board writes the sum of the selected weights, , and evaluates it to 24, showing how the total cost of the MST is read directly from the chosen edges.
The lesson closes by shifting from the worked example to asymptotic cost. A new page lists two implementation-dependent bounds for Prim's algorithm: for adjacency matrix searching and for a binary heap with adjacency list, while the narrator begins to explain that the running time depends on the data structures used.
The opening visual is a handwritten board titled Time Complexity. It compares two implementation choices for Prim's algorithm. The first line pairs Adjacency Matrix, Searching with , meaning that if the graph is searched through an adjacency matrix, the stated running time is quadratic in the number of vertices .
The second line pairs Binary Heap and Adjacency List with . Here denotes the number of edges, so the bound reflects heap operations together with adjacency-list edge scans.
The video then cuts to a typed pseudocode page headed procedure prim(G,w). The input is explicitly a connected undirected graph with edge weights , and the output is a minimum spanning tree encoded by the array prev.
The algorithm begins by initializing every vertex with and . This records that no vertex is yet attached to the growing tree. One arbitrary starting vertex is then chosen and assigned so that it becomes the first extracted vertex.
Next, the line creates a priority queue containing all vertices, keyed by their current cost values. The narration over this page says the algorithm shown is fairly easy to implement.
The main loop runs while is not empty. Each iteration removes , the currently cheapest frontier vertex. For every incident edge , the code checks whether .
If that inequality holds, the algorithm improves by setting and , then calls . In other words, the tree is grown by repeatedly selecting the minimum-cost available vertex and relaxing edges out of it.
The clip closes with the speaker saying, "And that's it," followed by a brief concluding remark that the video hopefully gave a good understanding of Prim's algorithm. No proof of correctness is shown in this excerpt; the emphasis is on the final complexity summary and the readable pseudocode structure.
Prim's algorithm is introduced as a greedy procedure for constructing a minimum spanning tree. The board directly links the algorithm name to "Minimum Spanning Tree (MST)", and the narration defines the MST as a minimum-weight connected graph with no cycles.
An MST is a spanning subgraph that connects all vertices, contains no cycles, and has minimum possible total edge weight. This definition is stated verbally near the beginning and serves as the target object of the whole example.
Before running the algorithm, the example creates an empty collection labeled Visited = { }. Its purpose is to record which vertices have already been incorporated into the partial tree, so future edge choices can be restricted to those crossing from visited to unvisited vertices.
The first operational step is to choose any starting node. In the example, vertex A is selected and immediately added to Visited, producing Visited = {A}. This initializes the tree fragment from which the greedy expansion proceeds.
At each step, inspect edges from the current visited set to unvisited vertices and select the one of minimum weight. The example first chooses A-B with weight 2, then continues by adding the cheapest admissible edge at each subsequent stage.
When multiple candidate edges share the same minimum weight, any one of them may be chosen. The narrator demonstrates this when three frontier edges all have weight 3 and selects A-C as the next addition.
Even if an edge has very small weight, it must be rejected when both endpoints are already in the MST. The example explicitly skips B-E for this reason and instead adds C-F, preserving the acyclic tree structure.
The algorithm stops once every vertex belongs to the tree. In the example, the last unvisited vertex G is attached through F-G, leaving a connected acyclic spanning tree on all seven vertices.
The clip states that if all edge weights are distinct, then the minimum spanning tree is unique. This is presented as a theoretical note after the worked construction, not as a proved theorem within the excerpt.
After the MST edges are identified, their weights are added to obtain the objective value. The example computes from the six chosen edges.
The closing board compares two standard implementations of Prim's algorithm. Using an adjacency matrix with searching gives , while using a binary heap together with an adjacency list gives .
The handwritten slide states that using adjacency matrix searching gives running time , where is the number of vertices.
The same slide states that using a binary heap together with adjacency lists gives running time , where is the number of vertices and is the number of edges.
The typed pseudocode defines procedure prim(G,w) for a connected undirected graph with edge weights . Its output is a minimum spanning tree represented by the array prev.
Every vertex starts with and . An arbitrary initial vertex is chosen and set to , then all vertices are inserted into a priority queue keyed by cost.
While is not empty, extract . For each edge , if , update , set , and call .
Explore conditions, steps and evidence. Supplementary explanations are labeled separately from content shown in the video.
Handwritten title "Prim's Algorithm" is shown on the whiteboard.
The narrator says, "This video will show you the correct way to run Prim's algorithm on a graph."
Prim's Algorithm
Name of the greedy minimum spanning tree algorithm demonstrated in the clip.
Graph theory / discrete mathematics
Below the title, the board shows "Minimum Spanning Tree (MST)" with a downward arrow from "Prim's Algorithm".
The narrator says, "Prim's algorithm results in a minimum spanning tree, a minimum weight connected graph with no cycles."
MST
Abbreviation for Minimum Spanning Tree, the output object produced by Prim's algorithm.
Graph theory
At the bottom of the graph page, the board first shows "Visited = { }" and later updates it as nodes are added.
The narrator says, "To start, create an empty list called visited. We will use this list to keep track of nodes that we have touched."
Visited
A tracking set/list of vertices already included in the growing minimum spanning tree.
Algorithm state in graph traversal
The hand-drawn graph contains seven circular nodes labeled A, B, C, D, E, F, and G.
The narrator refers to specific vertices such as A, B, C, F, and G while running the algorithm.
A, B, C, D, E, F, G
Vertex labels of the example weighted graph used to demonstrate Prim's algorithm.
Vertices of the example graph
Edges in the example graph are labeled with numeric weights including 1, 2, 3, 4, 5, 6, 7, 8, and 9.
The narrator repeatedly chooses edges by comparing their weights, e.g. "choose the smallest edge" and "edge BE with a weight of 3".
Edge weights
Numeric costs assigned to edges; Prim's algorithm selects the minimum-weight edge crossing from visited to unvisited vertices.
Weighted undirected graph
The board writes "Total Edge Weight = ".
The narrator says, "You can add the edge weights to get the minimum spanning tree's total edge weight."
Total Edge Weight
Sum of the weights of all edges selected into the MST.
Objective value of the minimum spanning tree
On the time-complexity page, the board writes and .
The narrator begins, "The time complexity depends on the data structures," indicating the formulas concern implementation-dependent running time.
The clip ends before the narrator explains what V and E stand for verbally.
V
Number of vertices in the graph, used in the displayed time-complexity expressions.
Graph size parameter
The second complexity formula on the board is written as .
The narrator introduces the topic of time complexity just before the clip ends.
The clip ends before the narrator explicitly defines E in speech.
E
Number of edges in the graph, used in the displayed time-complexity expression.
Graph size parameter
In the handwritten slide, V appears inside and .
V
Number of vertices in the graph.
Positive integer.
In the handwritten slide, E appears inside .
E
Number of edges in the graph.
Nonnegative integer.
The typed pseudocode header reads procedure prim(G,w).
G
Input graph to Prim's algorithm.
Connected undirected graph .
The typed pseudocode header reads procedure prim(G,w), and the input line mentions edge weights .
w
Edge-weight function.
Assigns a weight to each edge e.
Title card reads "Prim's Algorithm" with an arrow to "Minimum Spanning Tree (MST)".
Narrator states that the video shows how to run Prim's algorithm and that it results in a minimum spanning tree.
Prim's algorithm is presented as a method for constructing a minimum spanning tree from a weighted graph. The board links the algorithm directly to the MST concept, and the narration defines the MST as a minimum-weight connected graph with no cycles.
Applies to a weighted graph.
The desired output is a spanning tree of minimum total weight.
The board writes "Minimum Spanning Tree (MST)" under the title.
Narrator says, "a minimum spanning tree, a minimum weight connected graph with no cycles."
The clip defines an MST as a connected acyclic subgraph that spans the vertices and has minimum total edge weight. This is the target structure produced by Prim's algorithm.
The graph must be connected for a spanning tree to exist.
The MST minimizes the sum of selected edge weights.
The MST contains no cycles.
The graph page shows "Visited = { }" at the bottom.
Narrator says to create an empty list called visited to keep track of nodes that have been touched.
Prim's algorithm maintains a collection of already included vertices. In the example, this is written as a set-like object "Visited" and updated after each chosen vertex is incorporated into the growing tree.
Used during execution of Prim's algorithm.
Initially empty before the first vertex is chosen.
A separate board page reads "Prim's = Pick a node".
Narrator says, "The next step is to pick an arbitrary node. We will start the algorithm from this node. Let's start with A in our graph. First, add A to the visited list."
The algorithm begins by choosing any starting vertex. In the worked example, vertex A is selected and immediately inserted into the Visited set, establishing the initial tree fragment.
The starting vertex may be chosen arbitrarily.
After selection, the starting vertex is marked visited.
Narrator says, "Next, examine all vertices reachable from A... 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."
Edges from A are highlighted, and the edge A-B with weight 2 is circled and then colored red as part of the MST.
At each iteration, the algorithm inspects edges incident to the current visited set and chooses the minimum-weight edge that leads to a vertex not yet visited. The chosen edge and its new endpoint are then added to the MST.
Consider only edges crossing from visited vertices to unvisited vertices.
Choose the edge of minimum weight among those candidates.
Add both the edge and the newly reached vertex to the tree.
Narrator says, "Three edges all have a weight of three. Pick one of these. I've chosen to add AC."
From the visited set {A,B}, multiple candidate edges of weight 3 are visible, and A-C is selected next.
When more than one candidate edge attains the same minimum weight, the algorithm may choose any one of them. In the example, after {A,B} are visited, several weight-3 edges are available and the presenter selects A-C.
Occurs when multiple crossing edges share the minimum weight.
Any tied edge may be chosen without violating the greedy rule.
Narrator says, "Notice at this point, the edge BE with a weight of 3 is the smallest edge. But both vertices are already in the MST, so we do not pick it. Instead, we will choose to add F to the MST."
Edge B-E remains blue/unselected while the algorithm instead selects C-F with weight 6.
Prim's algorithm only accepts edges that connect the visited portion of the tree to an unvisited vertex. Even if an edge has small weight, it is ignored when both endpoints are already in the MST, because adding it would create a cycle.
Candidate edge must cross between visited and unvisited vertices.
Edges internal to the visited set are discarded.
Narrator says, "The only unvisited node remaining is G, so we add this to the minimum spanning tree. All the nodes are now connected in a tree."
The final red MST includes all seven vertices A through G and six selected edges.
The process stops once every vertex has been visited and included in the tree. In the example, the last unvisited vertex G is attached through edge F-G, yielding a connected acyclic spanning tree over all vertices.
Continue until all vertices are in the Visited set.
For a connected graph with n vertices, the MST contains n-1 edges.
Board writes "Total Edge Weight = ".
Narrator says, "You can add the edge weights to get the minimum spanning tree's total edge weight."
After the MST edges are selected, the total cost is obtained by summing their weights. The example computes the total from the six chosen edges and obtains 24.
Apply after the MST edge set has been determined.
Sum only the weights of edges included in the MST.
Board heading "Time Complexity" lists "Adjacency Matrix, Searching -> " and "Binary Heap and Adjacency List -> ".
Narrator says, "The time complexity depends on the data structures," before the clip ends.
The verbal explanation is cut off before the narrator elaborates on why each implementation gives the stated bound.
The clip states that Prim's running time depends on the chosen data structures. Two standard implementations are shown: using an adjacency matrix with searching gives , while using a binary heap together with an adjacency list gives .
First bound corresponds to adjacency-matrix search implementation.
Second bound corresponds to binary-heap plus adjacency-list implementation.
V denotes number of vertices and E denotes number of edges.
Handwritten slide title Time Complexity with line Adjacency Matrix, Searching -> .
The slide states that when Prim's algorithm is implemented with adjacency-matrix searching, the running time is . Here V denotes the number of vertices.
Implementation uses adjacency matrix searching.
V is the number of vertices.
Handwritten slide line Binary Heap and Adjacency List -> .
The slide states that with a binary heap and adjacency list representation, the running time is . Here V is the number of vertices and E is the number of edges.
Implementation uses a binary heap.
Graph is stored with adjacency lists.
V is the number of vertices and E is the number of edges.
Narrator defines MST as "a minimum weight connected graph with no cycles."
Board labels the output as "Minimum Spanning Tree (MST)".
A minimum spanning tree is a connected acyclic spanning subgraph of minimum total edge weight.
The underlying graph is weighted.
A spanning tree exists, which requires connectivity of the graph.
For the given weighted connected graph, an MST is a spanning subgraph with minimum total weight among all spanning trees.
Narrator says, "Note that if edge weights are distinct, this minimum spanning tree will be unique."
The clip states the result but does not prove it.
If all edge weights in the graph are distinct, then the minimum spanning tree is unique.
The graph is weighted.
All edge weights are pairwise distinct.
For any weighted graph whose edge weights are all different, there is exactly one minimum spanning tree.
Narrator says, "Prim's is a greedy algorithm, so we're going to choose the smallest edge that connects to an unvisited node."
Prim's algorithm proceeds by greedily selecting the minimum-weight edge that connects the current visited set to an unvisited vertex.
A starting vertex has been chosen.
A visited set is maintained.
Edge weights are comparable.
At each iteration before completion, the algorithm chooses a locally minimum crossing edge.
Narrator says, "The time complexity depends on the data structures," while introducing the complexity page.
Two different bounds are written for two different implementations.
The spoken explanation is truncated before further detail is given.
The time complexity of Prim's algorithm depends on the data structures used to represent and search the graph.
The graph is represented in some concrete data structure.
The algorithm is implemented using a corresponding search/update mechanism.
Across implementations of Prim's algorithm, asymptotic running time varies with the chosen representation and priority-structure support.
Speaker says: "The algorithm shown here is fairly easy to implement."
This is an evaluative statement rather than a formal theorem.
The algorithm shown on screen is fairly easy to implement.
The speaker is referring to the displayed Prim pseudocode.
No formal quantifier is stated.
The narrator walks through the algorithm step by step on the example graph.
The board updates Visited and colors selected MST edges in red as the algorithm proceeds.
Begin with an empty Visited set, written as Visited = { }.
Initialization step stated by the narrator.
Pick an arbitrary starting vertex; the example chooses A and updates Visited = {A}.
The narrator says to pick an arbitrary node and then starts with A.
Examine edges incident to A and choose the minimum-weight edge to an unvisited vertex, namely A-B with weight 2; update Visited = {A,B}.
This is the greedy rule described in the narration and shown by circling A-B.
From the visited set {A,B}, compare crossing edges; several have weight 3, and the presenter chooses A-C, updating Visited = {A,B,C}.
The narrator explicitly notes the tie among weight-3 edges and says, "I've chosen to add AC."
Continue the same rule and select C-E with weight 1, updating Visited = {A,B,C,E}.
The board shows C-E circled and then colored red as the next minimum crossing edge.
Select A-D with weight 3, updating Visited = {A,B,C,E,D}.
The diagram highlights A-D next and the narration instructs to continue picking the smallest edge to an unvisited node.
Although B-E has weight 3, it is not chosen because both B and E are already visited; instead choose C-F with weight 6, updating Visited = {A,B,C,D,E,F}.
The narrator explicitly rejects B-E for having both endpoints in the MST and then adds F.
The only remaining unvisited vertex is G, so add F-G with weight 9 and obtain the full MST over all seven vertices.
The narrator states that G is the only unvisited node remaining and then declares all nodes connected in a tree.
Sum the weights of the six selected MST edges to compute the total edge weight.
The board writes the arithmetic and the narrator explains that the MST total is found by adding edge weights.
The example yields the MST edge set {A-B, A-C, C-E, A-D, C-F, F-G} with total weight 24.
Narrator says edge BE is smallest but both vertices are already in the MST, so it is not picked.
B-E remains unselected while another crossing edge is chosen instead.
Identify the smallest visible edge among candidates, here B-E with weight 3.
The narrator points out that B-E is the smallest edge at that moment.
Check whether the edge connects a visited vertex to an unvisited vertex.
Prim's rule only accepts crossing edges from the current tree to outside vertices.
Since both B and E are already in the MST, reject B-E.
The narrator explicitly says both vertices are already in the MST, so the edge is not picked.
Choose the next valid minimum crossing edge, C-F with weight 6.
The algorithm continues by selecting the smallest admissible edge to an unvisited node.
Edges internal to the visited set are ignored because accepting them would violate the tree/no-cycle requirement of an MST.
Full typed pseudocode for procedure prim(G,w) is visible from initialization through the while-loop and decreasekey update.
The clip does not prove correctness; it only displays the algorithmic steps.
Initialize every vertex with infinite cost and no predecessor.
Displayed pseudocode initialization.
Choose one starting vertex and give it zero cost so it will be selected first.
Displayed pseudocode initialization.
Place all vertices into a priority queue keyed by cost-values.
Displayed pseudocode line with parenthetical note priority queue, using cost-values as keys.
Repeatedly remove the currently cheapest unreached vertex from the queue.
Displayed main loop header.
For each neighbor z of v, improve z's connection to the tree if edge {v,z} is cheaper than its current cost, then update the queue key.
Displayed relaxation block.
The procedure grows a spanning tree by always extracting the minimum-cost frontier vertex and relaxing incident edges, with the final tree encoded in prev.
A weighted graph with vertices A through G and numeric edge weights is drawn and processed step by step.
The narrator runs Prim's algorithm on this exact graph and computes the final total weight.
Run Prim's algorithm on the displayed weighted graph with vertices A, B, C, D, E, F, G and find its minimum spanning tree and total edge weight.
Vertices: A, B, C, D, E, F, G.
Visible edge weights include , , , , , , , , , , .
Start by choosing an arbitrary node; the example chooses A.
Construct the MST using Prim's greedy rule and compute the total edge weight.
Initialize Visited = { }.
Stated initialization step of the algorithm.
Choose A as the start vertex and set Visited = {A}.
The narrator says to pick an arbitrary node and starts with A.
Select A-B (weight 2) as the minimum edge from A to an unvisited vertex; set Visited = {A,B}.
Direct application of the greedy crossing-edge rule.
Among tied minimum crossing edges of weight 3, choose A-C; set Visited = {A,B,C}.
The narrator notes the tie and explicitly chooses AC.
Select C-E (weight 1); set Visited = {A,B,C,E}.
It is the smallest edge from the visited set to an unvisited vertex at that stage.
Select A-D (weight 3); set Visited = {A,B,C,E,D}.
Continuation of the same greedy rule as shown on the board.
Skip B-E because both endpoints are already visited; select C-F (weight 6); set Visited = {A,B,C,D,E,F}.
The narrator explicitly rejects B-E and then adds F via C-F.
Select F-G (weight 9) as the last remaining unvisited vertex is G.
The narrator states that G is the only unvisited node left.
Add the weights of the six MST edges to obtain the total cost.
The board displays the arithmetic and the narrator explains the summation.
The MST consists of edges A-B, A-C, C-E, A-D, C-F, and F-G, with total edge weight 24.
The resulting subgraph connects all seven vertices, contains exactly six edges, and has no cycles; the displayed sum of selected edge weights is 24.
The opening board shows "Prim's Algorithm" and then adds a downward arrow to "Minimum Spanning Tree (MST)".
Text "Prim's Algorithm"
Downward arrow
Text "Minimum Spanning Tree (MST)"
The board first presents the algorithm name.
An arrow is added to indicate the algorithm produces an MST.
The relationship shown is conceptual rather than computational.
No graph is yet being processed in this interval.
The visual establishes that Prim's algorithm is being introduced as a method for obtaining a minimum spanning tree.
A hand-drawn weighted graph with vertices A through G appears, with "Visited = { }" written below.
Seven labeled vertices A-G
Weighted edges
Text "Visited = { }"
The example graph is introduced.
The algorithm state is initialized with an empty visited collection.
The underlying graph structure and edge weights remain fixed throughout the worked example.
No MST edges are selected yet.
This frame sets up the input instance before any greedy choices are made.
A separate board page reads "Prim's = Pick a node".
Text "Prim's = Pick a node"
The video temporarily leaves the graph to emphasize the initialization rule.
No vertex has yet been permanently added on this slide itself.
The message summarizes the next operational step.
The visual compresses the start of Prim's algorithm to the idea of choosing an initial vertex.
Edges incident to A are emphasized, and A-B is circled and then colored red.
Narrator says to examine all vertices reachable from A and choose the smallest edge to an unvisited node.
Vertex A
Edges from A
Edge A-B
Visited set text
Visited changes from { } to {A}, then to {A,B}.
Edge A-B is marked as part of the MST.
The rest of the graph topology is unchanged.
Only edges crossing from visited to unvisited vertices are relevant.
The animation/diagram demonstrates the core Prim step: inspect frontier edges and take the cheapest one leading outward.
Multiple candidate edges of weight 3 are visible from the visited set, and A-C is circled and selected.
Narrator says three edges all have weight 3 and chooses AC.
Visited set {A,B}
Candidate edges of weight 3
Edge A-C
Visited expands from {A,B} to {A,B,C}.
One tied minimum edge is selected arbitrarily.
All tied edges have equal weight.
The algorithm remains valid regardless of which tied edge is chosen.
The visual illustrates that Prim's greedy rule may encounter ties and still proceed by selecting any minimum crossing edge.
Edge B-E is visible with weight 3 but remains unselected, while C-F is chosen next.
Narrator explicitly says B-E is not picked because both vertices are already in the MST.
Edge B-E
Edge C-F
Visited set before and after addition of F
The algorithm ignores B-E despite its low weight.
Visited expands by adding F through C-F.
Accepted edges must always cross from visited to unvisited vertices.
The visited set only grows; it never shrinks.
This event visually clarifies a common misconception: the globally smallest adjacent edge is not always eligible if it stays inside the current tree.
All seven vertices are circled in red and the selected MST edges are shown in red.
The board writes "Total Edge Weight = ".
Red-highlighted MST edges
All vertices A-G
Arithmetic line for total weight
The algorithm reaches termination with all vertices visited.
The total weight is computed from the selected edges.
The final structure is a tree spanning all vertices.
The non-selected edges are omitted from the MST.
The closing graph view confirms the output of Prim's algorithm and translates the edge set into its numerical cost.
A new page titled "Time Complexity" lists two implementation-dependent bounds.
The narrator's explanation is cut off before elaboration.
Heading "Time Complexity"
Text "Adjacency Matrix, Searching -> "
Text "Binary Heap and Adjacency List -> "
The video shifts from concrete graph execution to general algorithm analysis.
The bounds are presented as properties of implementations, not of a single graph instance.
The board summarizes that Prim's efficiency depends on how the graph and priority operations are implemented.
Static handwritten page titled Time Complexity with two implementation lines and arrows to asymptotic bounds.
Title Time Complexity
Line Adjacency Matrix, Searching
Arrow
Expression
Line Binary Heap and Adjacency List
Arrow
Expression
At about 3.5 seconds the handwritten page gives way to a typed pseudocode page.
During the first 3.5 seconds the slide content remains static.
The two complexity statements stay paired with their implementation labels.
The visual introduces implementation-dependent running times before showing the algorithm itself.
Static typed page headed procedure prim(G,w) with input/output lines, initialization, priority queue creation, and nested loops.
Header procedure prim(G,w)
Input line
Output line
Initialization block
H = makequeue(V)
while-loop
for each {v,z}
if cost(z) >
decreasekey(H,z)
Source URL at bottom right
Around 3.5 seconds the previous handwritten slide is replaced by this typed page.
After the transition the page remains static until the end of the clip.
The pseudocode text does not animate or highlight individual lines.
The source citation remains visible at the bottom right.
The second visual presents the full algorithm in pseudocode form while the narration comments on ease of implementation and concludes the lesson.
Narrator says the edge BE with weight 3 is the smallest edge, but both vertices are already in the MST, so it is not picked.
B-E is left unselected while another crossing edge is chosen.
One might think Prim's algorithm should always take the smallest nearby edge, even if both endpoints are already in the tree.
Prim's rule only accepts the smallest edge connecting the visited set to an unvisited vertex. Edges internal to the visited set are rejected because they would create a cycle.
Narrator says, "Note that if edge weights are distinct, this minimum spanning tree will be unique."
The clip does not discuss what happens when weights are not distinct, beyond implying non-uniqueness may occur.
A learner may infer from the example that every graph has exactly one MST.
The video states uniqueness only under the additional condition that all edge weights are distinct. Without that condition, multiple MSTs can exist.
Arrow from "Prim's Algorithm" to "Minimum Spanning Tree (MST)".
Narrator says Prim's algorithm results in a minimum spanning tree.
Prim's algorithm is presented as a procedure whose output is a minimum spanning tree.
The visited list is introduced and then used to decide which edges connect to unvisited nodes.
Visited is updated after each accepted vertex.
Maintaining the visited set is necessary in order to identify which edges cross from the current tree to unvisited vertices.
The narrator repeats the greedy rule until all nodes are connected in a tree.
Each accepted crossing edge enlarges the partial MST until all vertices are included.
The termination argument depends on repeatedly applying the greedy crossing-edge rule until every vertex has been absorbed into the tree.
Narrator rejects B-E because both endpoints are already in the MST.
The selected edges continue to form an acyclic connected subgraph.
Discarding internal edges is what keeps the construction consistent with the no-cycle requirement of a spanning tree.
The total-weight arithmetic is written after the final red MST is shown.
Narrator says to add the edge weights to get the MST's total edge weight.
The total edge weight can be computed only after the MST edge set has been fully determined.
Two different bounds are listed for two different implementations.
Narrator says the time complexity depends on the data structures.
The clip ends before giving a detailed derivation of either bound.
The abstract algorithm Prim's method can be implemented in multiple ways, and the chosen data structures determine its asymptotic running time.
Adjacency Matrix, Searching is directly paired by an arrow with .
The bound applies to the displayed Prim procedure when implemented with adjacency-matrix searching.
Binary Heap and Adjacency List is directly paired by an arrow with .
The bound applies to the displayed Prim procedure when implemented with a binary heap and adjacency lists.
Initialization lines precede H = makequeue(V) and the while-loop in the same pseudocode block.
The main loop depends on the prior initialization of cost, prev, the seed vertex , and the priority queue H.
The procedure header and input/output lines frame the subsequent algorithm as solving the minimum spanning tree problem.
The displayed method is an implementation of Prim's algorithm for producing a minimum spanning tree from a connected undirected weighted graph.
Narrator defines MST as a minimum weight connected graph with no cycles.
Board says "Prim's = Pick a node".
Narrator says to pick an arbitrary node and start with A.
Narrator chooses the smallest edge from A to an unvisited node, A to B.
A-B is circled and colored red.
Narrator says three edges all have weight 3 and picks one of them.
Narrator says B-E is not picked because both vertices are already in the MST.
Narrator says the MST will be unique if edge weights are distinct.
Board shows the sum .
Board lists and for different implementations.
The spoken explanation is truncated.
Handwritten line Adjacency Matrix, Searching -> .
Handwritten line Binary Heap and Adjacency List -> .
Pseudocode initializes cost and prev for all vertices, then sets cost()=0 and builds H.
Inside the if-block the pseudocode updates cost(z), prev(z), and calls decreasekey(H,z).
Covered · Title card and verbal definition introduce Prim's algorithm and the MST output.
Covered · Example graph is shown and the empty Visited set is initialized.
Covered · Board states to pick a node; narration selects A as the starting vertex.
Covered · Edges from A are examined and A-B is chosen as the first MST edge.
Covered · Tied weight-3 edges are discussed; A-C is chosen, then the process continues toward C-E and A-D.
Covered · B-E is rejected because both endpoints are already visited; C-F is added instead.
Covered · G is added as the last vertex, the MST is complete, and uniqueness under distinct weights is stated.
Covered · The selected edge weights are summed to obtain total weight 24.
Covered · A new board lists implementation-dependent time complexities before the clip ends.
Covered · Handwritten slide presents two implementation-dependent time complexities for Prim's algorithm.
Covered · Typed pseudocode shows the full Prim procedure while the audio comments on ease of implementation and closes the lesson.
Covered · Final brief tail after the spoken conclusion; no additional mathematical content is introduced.
Reviewed English material v1: card/concept_card "Prim's algorithm produces an MST" starting at 0:00 — Prim's algorithm is introduced as a greedy procedure for constructing a minimum spanning tree. The board directly links the algorithm name to "Minimum Spanning Tree (MST)", and the narration defines the MST as a minimum-weight connected graph with no cycles.
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).
To compute the total weight of the MST, sum the weights of all edges that were selected and added to the tree during the execution of Prim's algorithm.
Conditions: The MST edge set has been fully determined.; You have access to the weights of the selected edges.
Edge A-B is chosen first because Prim's algorithm is a greedy algorithm that selects the smallest edge connecting the current visited set to an unvisited node. From the starting node A, edge A-B has the minimum weight among all edges incident to A leading to unvisited nodes.
Conditions: Node A is the starting visited node.; The algorithm follows the greedy rule of picking the minimum-weight crossing edge.
A minimum spanning tree (MST) is a connected, acyclic subgraph that spans all vertices of a weighted graph and has the minimum possible total edge weight.
Conditions: The underlying graph must be weighted.; The graph must be connected for a spanning tree to exist.; The MST minimizes the sum of selected edge weights.; The MST contains no cycles.
YouTube2:45Another explanation of Minimum spanning tree.
Minimum spanning tree
YouTube1:47Another explanation of Minimum spanning tree.
Minimum spanning tree
YouTube3:34Another explanation of Minimum spanning tree.
Minimum spanning treeYouTube3:34Visual explanation for Minimum spanning tree, compared with the current whiteboard.
Minimum spanning tree