Kruskal: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
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 | 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). | |||
== Resources == | == Resources == | ||
Revision as of 05:41, 11 June 2018
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).
Resources
| https://www.youtube.com/watch?v=5xosHRdxqHA |