Kruskal: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
Kruskal is a greed algorithm to find the Minimum Spanning Tree. | |||
To get the Minimum Spanning Tree of a given Graph using the Kruskal algorithm, we need for each node of the graph to make a disjoint set. Then, all the edges of the graph should be sorted by weight. Iterate on the sorted list of edges and check if the nodes of the given edge belongs to the same set: If not, that edge is part of the solution and merge the disjoint sets that contain these nodes. | To get the Minimum Spanning Tree of a given Graph using the Kruskal algorithm, we need for each node of the graph to make a disjoint set. Then, all the edges of the graph should be sorted by weight. Iterate on the sorted list of edges and check if the nodes of the given edge belongs to the same set: If not, that edge is part of the solution and merge the disjoint sets that contain these nodes. | ||
Visually, the algorithm looks from the smaller to the bigger edges and add them to the solution one by one except when the edge has nodes that have already been part of the solution (meaning, edge has both nodes that belong to the same set). | Visually, the algorithm looks from the smaller to the bigger edges and add them to the solution one by one except when the edge has nodes that have already been part of the solution (meaning, edge has both nodes that belong to the same set). | ||
The complexity of the Kruskal algorithm is O(m log n) where m is the number of edges and n the number of nodes. | |||
== Resources == | == Resources == | ||
| Line 8: | Line 12: | ||
|- | |- | ||
|https://www.youtube.com/watch?v=5xosHRdxqHA | |https://www.youtube.com/watch?v=5xosHRdxqHA | ||
|- | |||
|https://en.wikipedia.org/wiki/Kruskal%27s_algorithm | |||
|} | |} | ||
Revision as of 05:44, 11 June 2018
Kruskal is a greed algorithm to find the Minimum Spanning Tree.
To get the Minimum Spanning Tree of a given Graph using the Kruskal algorithm, we need for each node of the graph to make a disjoint set. Then, all the edges of the graph should be sorted by weight. Iterate on the sorted list of edges and check if the nodes of the given edge belongs to the same set: If not, that edge is part of the solution and merge the disjoint sets that contain these nodes.
Visually, the algorithm looks from the smaller to the bigger edges and add them to the solution one by one except when the edge has nodes that have already been part of the solution (meaning, edge has both nodes that belong to the same set).
The complexity of the Kruskal algorithm is O(m log n) where m is the number of edges and n the number of nodes.
Resources
| https://www.youtube.com/watch?v=5xosHRdxqHA |
| https://en.wikipedia.org/wiki/Kruskal%27s_algorithm |