Scribd
Upload
11 views18 pages

Reverse-Delete Algorithm Explained

The document outlines the Reverse-Delete algorithm for finding minimum spanning trees, which involves sorting edges in decreasing order of their weights and deleting edges that do not cause disconnection in the graph. The algorithm proceeds by checking each edge, removing it if its deletion does not disconnect the graph, and continues until no more edges can be deleted. Examples illustrate the process and the final edges that remain in the minimum spanning tree.

Uploaded by

M Adnan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
11 views18 pages

Reverse-Delete Algorithm Explained

The document outlines the Reverse-Delete algorithm for finding minimum spanning trees, which involves sorting edges in decreasing order of their weights and deleting edges that do not cause disconnection in the graph. The algorithm proceeds by checking each edge, removing it if its deletion does not disconnect the graph, and continues until no more edges can be deleted. Examples illustrate the process and the final edges that remain in the minimum spanning tree.

Uploaded by

M Adnan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Graph Theory

Outline for today’s Lecture

Reverse-Delete algorithm for minimum spanning trees


Reverse Delete algorithm is closely related to Kruskal’s algorithm.

In Kruskal’s algorithm what we do is : Sort edges by increasing order of


their weights.

After sorting, we one by one pick edges in increasing order.

Include current picked edge if by including this in spanning tree not


form any cycle until there are V-1 edges in spanning tree, where V =
number of vertices.
In Reverse Delete algorithm, we sort all edges in decreasing order of
their weights.

After sorting, we one by one pick edges in decreasing order.

We include current picked edge if excluding current edge causes


disconnection in current graph.

The main idea is delete edge if its deletion does not lead to
disconnection of graph.
The Algorithm

1) Sort all edges of graph in non-increasing order of edge weights.


2) Initialize MST as original graph and remove extra edges using step 3.

3) Pick highest weight edge from remaining edges and check if deleting the edge
disconnects the graph or not. If disconnects, then we don't delete the edge.
Else we delete the edge and continue.
Let us understand with the following
example:

If we delete highest weight edge of weight 14, graph doesn’t become


disconnected, so we remove it.
Next we delete 11 as deleting it doesn’t disconnect the graph.
Next we delete 10 as deleting it doesn’t disconnect the graph.
Next is 9. We cannot delete 9 as deleting it causes disconnection.
We continue this way and following edges remain in final MST.
Edges in MST

(3, 4)
(0, 7)
(2, 3)
(2, 5)
(0, 1)
(5, 6)
(2, 8)
(6, 7)

Note : In case of same weight edges, we can pick any edge of the
same weight edges.
Example 2
In the following example green edges are being evaluated by the
algorithm and red edges have been deleted.

This is our original graph. The


numbers near the edges indicate their
edge weight.
The algorithm will start with the
maximum weighted edge, which in
this case is DE with an edge weight of
15. Since deleting edge DE does not
further disconnect the graph, it is
deleted.
The next largest edge is FG so the
algorithm will check if deleting this
edge will further disconnect the
graph. Since deleting the edge will not
further disconnect the graph, the
edge is then deleted.
The next largest edge is edge BD so
the algorithm will check this edge and
delete the edge.
The next edge to check is edge EG,
which will not be deleted since it
would disconnect node G from the
graph. Therefore, the next edge to
delete is edge BC.
The next largest edge is edge EF so
the algorithm will check this edge and
delete the edge.
The algorithm will then search the
remaining edges and will not find
another edge to delete; therefore this
is the final graph returned by the
algorithm.

You might also like