Reverse-delete algorithm - Revision history

JJMC89 bot III: Moving :Category:Algorithms in graph theory to :Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

2024-10-12T19:57:48Z

Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

← Previous revision		Revision as of 19:57, 12 October 2024
Line 89:		Line 89:
	{{Graph traversal algorithms}}		{{Graph traversal algorithms}}

	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]
	[[Category:Spanning tree]]		[[Category:Spanning tree]]

JJMC89 bot III: Moving :Category:Graph algorithms to :Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

2024-10-12T02:25:00Z

Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

← Previous revision		Revision as of 02:25, 12 October 2024
Line 89:		Line 89:
	{{Graph traversal algorithms}}		{{Graph traversal algorithms}}

	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]
	[[Category:Spanning tree]]		[[Category:Spanning tree]]

Matrix: /* Example */ add skin-invert-image for dark mode

2024-10-03T19:11:44Z

Example: add skin-invert-image for dark mode

← Previous revision		Revision as of 19:11, 3 October 2024
Line 26:		Line 26:
	== Example ==		== Example ==
	In the following example green edges are being evaluated by the algorithm and red edges have been deleted.		In the following example green edges are being evaluated by the algorithm and red edges have been deleted.
	{\| border=1 cellspacing=0 cellpadding=5		{\| border=1 cellspacing=0 cellpadding=5 class="skin-invert-image"
	\|[[Image:Reverse Delete 0.svg\|200px]]		\|[[Image:Reverse Delete 0.svg\|200px]]
	\|This is our original graph. The numbers near the edges indicate their edge weight.		\|This is our original graph. The numbers near the edges indicate their edge weight.

Ygolygydd: Reverted 3 edits by 182.53.54.19 (talk) to last revision by Pickersgill-Cunliffe

2024-09-04T11:38:36Z

Reverted 3 edits by 182.53.54.19 (talk) to last revision by Pickersgill-Cunliffe

← Previous revision		Revision as of 11:38, 4 September 2024
Line 1:		Line 1:
	{{short description\|Minimum spanning forest algorithm that greedily deletes edges}}		{{short description\|Minimum spanning forest algorithm that greedily deletes edges}}
	The '''reverse-delete algorithm''' is an used to obtain a from a given connected, It first appeared in but it should not be confused with which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.		The '''reverse-delete algorithm''' is an [[algorithm]] in [[graph theory]] used to obtain a [[minimum spanning tree]] from a given connected, [[weighted graph\|edge-weighted graph]]. It first appeared in {{harvtxt\|Kruskal\|1956}}, but it should not be confused with [[Kruskal's algorithm]] which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.

	choosing the best choice which is another greedy algorithm to find a starts with an empty graph and adds edges while the starts with the original graph and deletes edges from it. The algorithm works as follows:		This algorithm is a [[greedy algorithm]], choosing the best choice given any situation. It is the reverse of [[Kruskal's algorithm]], which is another greedy algorithm to find a minimum spanning tree. Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it. The algorithm works as follows:
			* Start with graph G, which contains a list of edges E.

			* Go through E in decreasing order of edge weights.
	.
			* For each edge, check if deleting the edge will further disconnect the graph.
			* Perform any deletion that does not lead to additional disconnection.

	== Pseudocode ==		== Pseudocode ==

182.53.54.19 at 11:35, 4 September 2024

2024-09-04T11:35:44Z

← Previous revision		Revision as of 11:35, 4 September 2024
Line 2:		Line 2:
	The '''reverse-delete algorithm''' is an used to obtain a from a given connected, It first appeared in but it should not be confused with which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.		The '''reverse-delete algorithm''' is an used to obtain a from a given connected, It first appeared in but it should not be confused with which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.

	choosing the best choice which is another greedy algorithm to find a ~~minimum spanning tree. Kruskal’s algorithm~~ starts with an empty graph and adds edges while the ~~Reverse-Delete algorithm~~ starts with the original graph and deletes edges from it. The algorithm works as follows:		choosing the best choice which is another greedy algorithm to find a starts with an empty graph and adds edges while the starts with the original graph and deletes edges from it. The algorithm works as follows:

	.		.
	* Perform any deletion that does not lead to additional disconnection.

	== Pseudocode ==		== Pseudocode ==

182.53.54.19 at 11:34, 4 September 2024

2024-09-04T11:34:52Z

← Previous revision		Revision as of 11:34, 4 September 2024
Line 2:		Line 2:
	The '''reverse-delete algorithm''' is an used to obtain a from a given connected, It first appeared in but it should not be confused with which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.		The '''reverse-delete algorithm''' is an used to obtain a from a given connected, It first appeared in but it should not be confused with which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.

	choosing the best choice ~~given any situation. It is the reverse of [[Kruskal's algorithm]],~~ which is another greedy algorithm to find a minimum spanning tree. Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it. The algorithm works as follows:		choosing the best choice which is another greedy algorithm to find a minimum spanning tree. Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it. The algorithm works as follows:

	.		.

182.53.54.19 at 11:34, 4 September 2024

2024-09-04T11:34:25Z

← Previous revision		Revision as of 11:34, 4 September 2024
Line 1:		Line 1:
	{{short description\|Minimum spanning forest algorithm that greedily deletes edges}}		{{short description\|Minimum spanning forest algorithm that greedily deletes edges}}
	The '''reverse-delete algorithm''' is an ~~[[algorithm]] in [[graph theory]]~~ used to obtain a ~~[[minimum spanning tree]]~~ from a given connected, ~~[[weighted graph\|edge-weighted graph]].~~ It first appeared in ~~{{harvtxt\|Kruskal\|1956}},~~ but it should not be confused with ~~[[Kruskal's algorithm]]~~ which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.		The '''reverse-delete algorithm''' is an used to obtain a from a given connected, It first appeared in but it should not be confused with which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.

	~~This algorithm is a [[greedy algorithm]],~~ choosing the best choice given any situation. It is the reverse of [[Kruskal's algorithm]], which is another greedy algorithm to find a minimum spanning tree. Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it. The algorithm works as follows:		choosing the best choice given any situation. It is the reverse of [[Kruskal's algorithm]], which is another greedy algorithm to find a minimum spanning tree. Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it. The algorithm works as follows:

	* Start with graph G, which contains a list of edges E.
			.
	* Go through E in decreasing order of edge weights.
	* For each edge, check if deleting the edge will further disconnect the graph.
	* Perform any deletion that does not lead to additional disconnection.		* Perform any deletion that does not lead to additional disconnection.

Pickersgill-Cunliffe: Reverted edits by 158.130.59.20 (talk) (HG) (3.4.12)

2024-03-20T18:00:58Z

Reverted edits by 158.130.59.20 (talk) (HG) (3.4.12)

← Previous revision		Revision as of 18:00, 20 March 2024
Line 1:		Line 1:
	{{short description\|Minimum spanning forest algorithm that greedily deletes edges}}		{{short description\|Minimum spanning forest algorithm that greedily deletes edges}}
	The '''~~wallbreaker~~ algorithm'' is an [[algorithm]] in [[graph theory]] used to obtain a [[minimum spanning tree]] from a given connected, [[weighted graph\|edge-weighted graph]]. It first appeared in {{harvtxt\|Kruskal\|1956}}, but it should not be confused with [[Kruskal's algorithm]] which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.		The '''reverse-delete algorithm''' is an [[algorithm]] in [[graph theory]] used to obtain a [[minimum spanning tree]] from a given connected, [[weighted graph\|edge-weighted graph]]. It first appeared in {{harvtxt\|Kruskal\|1956}}, but it should not be confused with [[Kruskal's algorithm]] which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.

	This algorithm is a [[greedy algorithm]], choosing the best choice given any situation. It is the reverse of [[Kruskal's algorithm]], which is another greedy algorithm to find a minimum spanning tree. Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it. The algorithm works as follows:		This algorithm is a [[greedy algorithm]], choosing the best choice given any situation. It is the reverse of [[Kruskal's algorithm]], which is another greedy algorithm to find a minimum spanning tree. Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it. The algorithm works as follows:

158.130.59.20 at 18:00, 20 March 2024

2024-03-20T18:00:28Z

← Previous revision		Revision as of 18:00, 20 March 2024
Line 1:		Line 1:
	{{short description\|Minimum spanning forest algorithm that greedily deletes edges}}		{{short description\|Minimum spanning forest algorithm that greedily deletes edges}}
	The '''~~reverse-delete~~ algorithm''' is an [[algorithm]] in [[graph theory]] used to obtain a [[minimum spanning tree]] from a given connected, [[weighted graph\|edge-weighted graph]]. It first appeared in {{harvtxt\|Kruskal\|1956}}, but it should not be confused with [[Kruskal's algorithm]] which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.		The '''wallbreaker algorithm'' is an [[algorithm]] in [[graph theory]] used to obtain a [[minimum spanning tree]] from a given connected, [[weighted graph\|edge-weighted graph]]. It first appeared in {{harvtxt\|Kruskal\|1956}}, but it should not be confused with [[Kruskal's algorithm]] which appears in the same paper. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which contains every vertex in the graph.

	This algorithm is a [[greedy algorithm]], choosing the best choice given any situation. It is the reverse of [[Kruskal's algorithm]], which is another greedy algorithm to find a minimum spanning tree. Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it. The algorithm works as follows:		This algorithm is a [[greedy algorithm]], choosing the best choice given any situation. It is the reverse of [[Kruskal's algorithm]], which is another greedy algorithm to find a minimum spanning tree. Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it. The algorithm works as follows:

Materialscientist: Reverted edits by 152.77.91.162 (talk) (HG) (3.4.12)

2023-11-09T08:25:34Z

Reverted edits by 152.77.91.162 (talk) (HG) (3.4.12)

← Previous revision		Revision as of 08:25, 9 November 2023
Line 8:		Line 8:
	* Perform any deletion that does not lead to additional disconnection.		* Perform any deletion that does not lead to additional disconnection.

	== ~~King Theo passed here~~ ==		== Pseudocode ==

	'''function''' ReverseDelete(edges[] ''E'') '''is'''		'''function''' ReverseDelete(edges[] ''E'') '''is'''