- WELCOME TO A LESSON ON KRUSKAL'S ALGORITHM
THAT'S USED TO FIND THE MINIMUM COSTS
OF SPANNING TREE.
FOR REVIEW, A SPANNING TREE IS A CONNECTED GRAPH
USING ALL VERTICES IN WHICH THERE ARE NO CIRCUITS.
IN OTHER WORDS, THERE'S A PATH
FROM ANY VERTEX TO ANY OTHER VERTEX,
BUT NO CIRCUITS.
THE DARK BLUE PATH HERE IS AN EXAMPLE
OF A SPANNING TREE.
THE MINIMUM COST SPANNING TREE IS THE SPANNING TREE
WITH THE SMALLEST TOTAL EDGE WEIGHT.
THE NEAREST NEIGHBOR STYLE APPROACH DOESN'T MAKE MUCH SENSE
HERE SINCE WE DON'T NEED A CIRCUIT.
SO INSTEAD WE'LL TAKE AN APPROACH SIMILAR
TO THE SORTED EDGES ALGORITHM.
SO THE ALGORITHM DEFINE THE MINIMUM COSTS
OF SPANNING TREE IS CALLED KRUSKAL'S ALGORITHM, STEP 1.
WE SELECT THE CHEAPEST, UNUSED EDGE IN THE GRAPH,
STEP 2, WE REPEAT STEP 1 ADDING THE CHEAPEST UNUSED EDGE
UNLESS "A" ADDING THE EDGE WOULD CREATE A CIRCUIT.
SO AGAIN WE DON'T WANT CIRCUITS IN A SPANNING TREE.
AND THEN 3, WE REPEAT UNTIL THE SPANNING TREE IS FORMED.
KRUSKAL'S ALGORITHM IS AN EFFICIENT
AND OPTIMAL ALGORITHM WHICH MEANS IT'S EASY TO USE
AND IT DOES ALWAYS GIVE THE MINIMUM COST
OF SPANNING TREE.
LET'S TAKE A LOOK AT SOME EXAMPLES.
WE WANT TO FIND THE MINIMUM COST SPANNING TREE ON THE GRAPH BELOW
USING KRUSKAL'S ALGORITHM.
WHICH OF THE EDGES BELOW WERE INCLUDED
IN THE MINIMUM COST AND WHAT IS THE MINIMUM COST?
SO AGAIN WE BEGIN BY SELECTING THE EDGE WITH THE LEAST WEIGHT
OR THE CHEAPEST EDGE WHICH WE CAN SEE HERE
WOULD BE EDGE B, C.
AND NOW WE'LL SELECT THE NEXT CHEAPEST EDGE
AS LONG AS IT DOESN'T FORM A CIRCUIT.
SO THE NEXT EDGE WOULD BE EDGE "A," C
WITH A WEIGHT OF 7.
NEXT WOULD BE EDGE C, D WITH A WEIGHT OF 8.
AND WE'RE DONE BECAUSE NOW THERE'S A PATH FROM ANY VERTEX
TO ANY OTHER VERTEX WITHOUT ANY CIRCUITS.
SO THIS IS A SPANNING TREE.
AND NOW TO FIND THE MINIMUM COSTS,
WE SUM THE WEIGHTS OF THESE THREE EDGES.
SO THAT WOULD BE 5 + 7 + 8 WHICH IS EQUAL TO 20.
NOW LET'S TAKE A LOOK AT A MORE INVOLVED EXAMPLE.
THE GRAPH BELOW SHOWS THE COST IN THOUSANDS OF DOLLARS
TO PAVE ROADS BETWEEN HOUSES.
DETERMINE THE MINIMUM COST SPANNING TREE ON THE GRAPH
USING KRUSKAL'S ALGORITHM.
LOOKING AT ALL THE WEIGHTS, THE LEAST WEIGHT IS 2,
SO BEGIN BY USING EDGE "A," B AS WELL AS EDGE E, "I."
THE NEXT SMALLEST WEIGHT LOOKS LIKE IT'S 4
SO WE'LL USE EDGE G, H.
THE NEXT SMALLEST WEIGHT IS 5 WHICH IS HERE, EDGE E, F.
THE NEXT SMALLEST WEIGHT WOULD BE 6.
NOTICE HOW TWO EDGES HAVE A WEIGHT OF 6
USING EDGE C, G DOES NOT FORM A CIRCUIT AND NEITHER DOES USING
EDGE J, K.
SO WE'RE STILL OKAY.
THE NEXT SMALLEST WEIGHT WOULD BE 7.
NOTICE USING EDGE G, K DOES NOT FORM A CIRCUIT
SO WE'LL USE THAT EDGE.
THE NEXT SMALLEST WEIGHT WOULD BE 8 AND THERE ARE THREE
EDGES OF WEIGHT 8, EDGE B, C, EDGE D, H AND EDGE "I," J.
NOTICE USING EDGE B, C DOES NOT FORM A CIRCUIT.
NOTICE USING EDGE D, H DOES NOT FORM A CIRCUIT
AND NEITHER DOES USING EDGE "I," J.
THE NEXT SMALLEST WEIGHT WOULD BE 9.
BUT LOOKING AT EDGE B, F IF WE USE EDGE B, F,
WE WOULD FORM A CIRCUIT HERE AND THEREFORE WE CANNOT USE
EDGE B, F.
THE NEXT SMALLEST WEIGHT HERE WOULD BE 12.
AND SO IF WE USE EDGE H, L, IT DOES NOT FORM A CIRCUIT
AND IT ALSO COMPLETES THE SPANNING TREE.
SO NOW WE HAVE ALL THE EDGES WE NEED SO WE'LL HAVE TO FIND
THE MINIMUM COSTS.
SO WE'LL FIND THE SUM OF ALL THE WEIGHTS.
SO WE'D HAVE 2 + 8 + 6 + 8 + 5 + 4 + 2 + 7 + 12 + 8 + 6.
JUST MAKE SURE WE HAVE ALL OF THESE.
WE USED A TOTAL OF 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 EDGES
AND WE HAVE 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 VALUES.
AND THE SUM COMES TO 68.
REMEMBER THIS REPRESENTS THE $68,000 SO WE CAN SAY
THE MINIMUM COST SPANNING TREE IS $68,000.
NOW LET'S TAKE A LOOK AT ONE MORE EXAMPLE
WHERE THE INFORMATION IS GIVEN AS A TABLE.
ONE THING WE SHOULD RECOGNIZE ABOUT THE TABLE
IS THAT EACH WEIGHT IS GIVEN TWICE.
THE DATA IN THE UPPER RIGHT HAND CORNER
IS A DUPLICATION OF DATA IN THE LOWER LEFT HAND CORNER.
FOR EXAMPLE, THIS VALUE HERE OF 3 REPRESENTS THE WEIGHT
OF EDGE B, C.
AND SO DOES THIS 3 HERE.
SO WHEN FINDING THE MINIMUM COSTS,
OR THE SMALLEST WEIGHTS, WE'LL JUST REFER
TO THIS UPPER TRIANGLE HERE.
ALSO NOTICE HOW WE HAVE SIX VERTICES SO IT CAN BE HELPFUL
TO PUT THE VERTICES IN A CIRCLE LIKE THIS TO KEEP TRACK
OF THE EDGES THAT ARE USED.
NOW WE WANT TO FIND THE EDGE WITH THE LEAST WEIGHT
OR THE MINIMUM COST WHICH WOULD BE HERE AT 3,
WHICH IS EDGE B, C.
SO WE EDGE, EDGE B, C IS HERE.
THE NEXT SMALLEST WEIGHT OR MINIMUM COST WOULD BE HERE
AT 4 WHICH IS THE WEIGHT OF EDGE C, E WHICH IS HERE.
THE NEXT SMALLEST WEIGHT LOOKS LIKE IT WOULD BE 11 HERE
WHICH IS THE WEIGHT OF EDGE B, E.
BUT NOTICE HOW WE CAN'T USE EDGE B, E BECAUSE IT FORMS A CIRCUIT.
SO WE'LL GO AHEAD AND JUST CROSS THAT OFF
SO WE DON'T HAVE TO USE IT AGAIN.
THE NEXT SMALLEST WEIGHT OR LOWEST COST WOULD BE HERE
AT 16 WHICH IS THE WEIGHT OF EDGE E, F WHICH IS HERE.
NEXT SMALLEST WEIGHT WOULD BE 17, THE WEIGHT
OF EDGE "A," E WHICH IS HERE.
THE NEXT SMALLEST WEIGHT OR LOWEST COST IS 19
WHICH IS THE WEIGHT OF EDGE B, D WHICH IS HERE
WHICH DOES COMPLETE OUR SPANNING TREE AND CREATE
THE MINIMUM COST SPANNING TREE.
NOTICE HOW THERE'S A PATH FROM ANY VERTEX
TO ANY OTHER VERTEX AND NO CIRCUITS ARE FORMED.
WE'RE ALSO ASKED TO FIND THE TOTAL COST.
SO NOW WE'LL FIND THE SUM OF THESE WEIGHTS
WHICH WOULD BE 3 + 19 + 17 + 4 + 16
WHICH EQUALS 59.
OKAY. I HOPE YOU FOUND THIS HELPFUL.