Kruskal - Revision history

Savoundg at 07:56, 10 May 2019

2019-05-10T07:56:40Z

← Older revision		Revision as of 07:56, 10 May 2019
Line 1:		Line 1:
	Kruskal is a ~~greed~~ algorithm to find the Minimum Spanning Tree.		Kruskal is a greedy 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.

Savoundg at 05:44, 11 June 2018

2018-06-11T05:44:45Z

← Older revision		Revision as of 05:44, 11 June 2018
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
	\|}		\|}

Savoundg at 05:41, 11 June 2018

2018-06-11T05:41:08Z

← Older revision		Revision as of 05:41, 11 June 2018
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 ~~belong~~ to the same set: If not, that edge is part of the solution and merge the disjoint sets that contain these nodes. Visually ~~speaking~~, the algorithm looks from the smaller ~~edges~~ to the bigger edges and add them to the solution except the edge has nodes that have already been part of the solution (meaning, edge has both nodes that belong to the same set).		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 ==

Savoundg at 05:40, 11 June 2018

2018-06-11T05:40:13Z

← Older revision		Revision as of 05:40, 11 June 2018
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 belong to the same set: If not, that edge is part of the solution and merge the disjoint sets that contain these nodes. Visually speaking, the algorithm looks from the smaller edges to the bigger edges and add them to the solution except 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 ==
	{\| class="wikitable"		{\| class="wikitable"

Savoundg: Created page with "== Resources == {| class="wikitable" ! |- |https://www.youtube.com/watch?v=5xosHRdxqHA |}"

2018-06-11T05:24:24Z

Created page with "== Resources == {| class="wikitable" ! |- |https://www.youtube.com/watch?v=5xosHRdxqHA |}"

New page

== Resources ==
{| class="wikitable"
!
|-
|https://www.youtube.com/watch?v=5xosHRdxqHA
|}