Topic: Graph Algorithms.

We have discussed various graph algorithms, including Depth$-$First Search $($DFS$),$ Breadth$-$First Search $($BFS$),$ Prim's Algorithm, Kruskal's Algorithm, and Dijkstra's Algorithm.

For this assignment, you will tackle Kruskal's Algorithm, an algorithm for finding minimum spanning trees $($MSTs$).$ Although we outlined the idea behind this algorithm, we did not cover it thoroughly in class in the same way we covered Prim's or Dijkstra's algorithms. Please prepare and present a brief $(<mn>1</mn><mn>0</mn>$ minute$)$ explanation of how this algorithm functions. You are strongly encouraged to include an illustrative example. $($This may be on paper, electronic, or constructed live on the whiteboard. I$\text{'}$m open to other formats if desired.$)$

For this assignment, you will need to address how we avoid adding cycles to our MST$.$ There are multiple valid solutions, but your goal is to get as close to constant time as possible, and you must find and explain an approach that is faster than linear time.

I will ask you about:

$-$ The overall idea of the algorithm $($what are we finding, how are we finding it$)$

$-$ How we detect $\backslash$& avoid cycles in near$-$constant time

$-$ A visual example

$-$ How we calculate the overall runtime of the algorithm