Posted on by Kalkicode
Code Graph

# Reverse delete algorithm for minimum spanning tree

The reverse delete algorithm is a method used to find the minimum spanning tree of a graph, where the minimum spanning tree is a subset of edges that connects all the vertices with the minimum possible total edge weight. This article presents a detailed explanation of the reverse delete algorithm and provides a Java code implementation to demonstrate its application. ## Problem Statement

Given an undirected graph with weighted edges, the goal is to find the minimum spanning tree by iteratively removing edges while maintaining the connectivity of the graph.

## Description with Example

Imagine a scenario where you have a set of cities connected by roads with varying lengths. The reverse delete algorithm can help you identify the roads that need to be retained to ensure that all cities remain connected while minimizing the total road length.

## Idea to Solve

The reverse delete algorithm works by first sorting the edges of the graph in decreasing order of their weights. It then iteratively removes edges from the highest weight to the lowest while checking if the graph remains connected after each removal.

## Pseudocode

``````function reverseDeleteMST(graph):
result = 0
point = graph.edges
while point is not null:
remove edge (point.u, point.v) from the graph
if graph is still connected:
add edge (point.u, point.v) back to the graph
update result by adding point's weight
print edge (point.u, point.v)
point = point.next
print total weight of MST: result``````

## Algorithm Explanation

1. Initialize the `result` variable to store the total weight of the minimum spanning tree.
2. Initialize the `point` variable to the first edge in the sorted list of edges.
3. Iterate through each edge: a. Remove the edge `(u, v)` from the graph. b. Check if the graph remains connected using the `isConnected` function. c. If the graph is still connected:
• Add the edge `(u, v)` back to the graph.
• Update the `result` by adding the weight of the edge.
• Print the edge `(u, v)` to indicate it's part of the MST. d. Move to the next edge.
4. Print the total weight of the minimum spanning tree: `result`.

## Program solution

``````import java.util.ArrayList;
/*
Java Program
Reverse delete algorithm for minimum spanning tree
*/
class Edge
{
// edge weight or cost
public int weight;
public int u;
public int v;
public Edge next;
public Edge(int weight, int u, int v)
{
this.weight = weight;
this.u = u;
this.v = v;
this.next = null;
}
}
public class Graph
{
public int vertices;
public ArrayList < ArrayList < Integer >> adgeList;
public Edge edges;
public int edgeCount;
public Graph(int vertices)
{
this.vertices = vertices;
this.adgeList = new ArrayList < ArrayList < Integer >> (vertices);
this.edges = null;
this.edgeCount = 0;
for (int i = 0; i < this.vertices; ++i)
{
}
}
public void addEdge(int u, int v, int w)
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
// Collect descending order sorted edges
// Create new edge
Edge e = new Edge(w, u, v);
// Add edge in decreasing order
if (this.edges == null)
{
// First edge
this.edges = e;
}
else if (this.edges.weight <= e.weight)
{
e.next = this.edges;
this.edges = e;
}
else
{
Edge temp = this.edges;
// Find position to add new edge
while (temp.next != null && temp.next.weight > e.weight)
{
temp = temp.next;
}
e.next = temp.next;
temp.next = e;
}
this.edgeCount = this.edgeCount + 1;
}
// Perform DFS
public void findDFS(int v, boolean[] visited)
{
// Indicates the current vertex is visited
visited[v] = true;
// iterate edges of v node
for (int i = 0; i < this.adgeList.get(v).size(); i++)
{
{
}
}
}
// Check that graph start vertices are reach to all other vertices or not
public boolean isConnected()
{
boolean[] visited = new boolean[this.vertices];
// Set the initial visited vertices
for (int i = 0; i < this.vertices; ++i)
{
visited[i] = false;
}
this.findDFS(0, visited);
for (int i = 1; i < this.vertices; i++)
{
if (visited[i] == false)
{
// When [i] vertices are not visit
return false;
}
}
return true;
}
public void printGraph()
{
for (int i = 0; i < this.vertices; ++i)
{
System.out.print(" \n [" + i + "] :");
// iterate edges of i node
for (int j = 0; j < this.adgeList.get(i).size(); j++)
{
}
}
}
public void reverseDeleteMST()
{
int result = 0;
// Get first higher edge
Edge point = this.edges;
System.out.println("\n\nConnected node by Edges in MST");
// iterates the edge from high to low order
while (point != null)
{
// Remove the current weight edge of node from u to v and v to u
if (isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
// Update weight
result += point.weight;
// Display edge
System.out.print(" (" + point.u + ", " + point.v + ") \n");
}
// Visit next smaller weight edge
point = point.next;
}
System.out.println("Calculated total weight of MST is " + result);
}
public static void main(String[] args)
{
Graph g = new Graph(8);
// Display graph element
g.printGraph();
// Find MST
g.reverseDeleteMST();
}
}``````

#### input

`````` Graph Adjacency List
 :  1  3
 :  0  2  6  7
 :  1  5  7
 :  0  4  7
 :  3  5  6  7
 :  2  4  6
 :  1  4  5
 :  1  2  3  4

Connected node by Edges in MST
(2, 5)
(4, 5)
(1, 6)
(0, 1)
(2, 7)
(1, 2)
(0, 3)
Calculated total weight of MST is 39``````
``````// Include header file
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
/*
C++ Program
Reverse delete algorithm for minimum spanning tree
*/
class Edge
{
public:
// edge weight or cost
int weight;
int u;
int v;
Edge *next;
Edge(int weight, int u, int v)
{
this->weight = weight;
this->u = u;
this->v = v;
this->next = NULL;
}
};
class Graph
{
public: int vertices;
Edge *edges;
int edgeCount;
Graph(int vertices)
{
this->vertices = vertices;
this->edges = NULL;
this->edgeCount = 0;
for(int i = 0 ; i < vertices; ++i)
{
}
}
void addEdge(int u, int v, int w)
{
if (u < 0 || u >= this->vertices || v < 0 || v >= this->vertices)
{
return;
}
// Collect descending order sorted edges
// Create new edge
Edge *e = new Edge(w, u, v);
// Add edge in decreasing order
if (this->edges == NULL)
{
// First edge
this->edges = e;
}
else if (this->edges->weight <= e->weight)
{
e->next = this->edges;
this->edges = e;
}
else
{
Edge *temp = this->edges;
// Find position to add new edge
while (temp->next != NULL && temp->next->weight > e->weight)
{
temp = temp->next;
}
e->next = temp->next;
temp->next = e;
}
this->edgeCount = this->edgeCount + 1;
}
// Perform DFS
void findDFS(int v, bool visited[])
{
// Indicates the current vertex is visited
visited[v] = true;
// iterate edges of v node
for (int i = 0; i < this->adgeList.at(v).size(); i++)
{
{
}
}
}
// Check that graph start vertices are reach to all other vertices or not
bool isConnected()
{
bool visited[this->vertices];
// Set the initial visited vertices
for (int i = 0; i < this->vertices; ++i)
{
visited[i] = false;
}
this->findDFS(0, visited);
for (int i = 1; i < this->vertices; i++)
{
if (visited[i] == false)
{
// When [i] vertices are not visit
return false;
}
}
return true;
}
void printGraph()
{
cout << "\n Graph Adjacency List ";
for (int i = 0; i < this->vertices; ++i)
{
cout << " \n [" << i << "] :";
// iterate edges of i node
for (int j = 0; j < this->adgeList.at(i).size(); j++)
{
cout << "  " << this->adgeList.at(i).at(j);
}
}
}
void reverseDeleteMST()
{
int result = 0;
// Get first higher edge
Edge *point = this->edges;
cout << "\n\nConnected node by Edges in MST" << endl;
// iterates the edge from high to low order
while (point != NULL)
{

// Remove the current weight edge of node from u to v and v to u

if (this->isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
// Update weight
result += point->weight;
// Display edge
cout << " (" << point->u << ", " << point->v << ") \n";
}
// Visit next smaller weight edge
point = point->next;
}
cout << "Calculated total weight of MST is " << result << endl;
}
};
int main()
{
Graph *g = new Graph(8);
// Display graph element
g->printGraph();
// Find MST
g->reverseDeleteMST();
return 0;
}``````

#### input

`````` Graph Adjacency List
 :  1  3
 :  0  2  6  7
 :  1  5  7
 :  0  4  7
 :  3  5  6  7
 :  2  4  6
 :  1  4  5
 :  1  2  3  4

Connected node by Edges in MST
(2, 5)
(4, 5)
(1, 6)
(0, 1)
(2, 7)
(1, 2)
(0, 3)
Calculated total weight of MST is 39``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program
Reverse delete algorithm for minimum spanning tree
*/
public class Edge
{
// edge weight or cost
public int weight;
public int u;
public int v;
public Edge next;
public Edge(int weight, int u, int v)
{
this.weight = weight;
this.u = u;
this.v = v;
this.next = null;
}
}
public class Graph
{
public int vertices;
public List < List < int >> adgeList;
public Edge edges;
public int edgeCount;
public Graph(int vertices)
{
this.vertices = vertices;
this.adgeList = new List < List < int >> (vertices);
this.edges = null;
this.edgeCount = 0;
for (int i = 0; i < this.vertices; ++i)
{
}
}
public void addEdge(int u, int v, int w)
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
// Collect descending order sorted edges
// Create new edge
Edge e = new Edge(w, u, v);
// Add edge in decreasing order
if (this.edges == null)
{
// First edge
this.edges = e;
}
else if (this.edges.weight <= e.weight)
{
e.next = this.edges;
this.edges = e;
}
else
{
Edge temp = this.edges;
// Find position to add new edge
while (temp.next != null && temp.next.weight > e.weight)
{
temp = temp.next;
}
e.next = temp.next;
temp.next = e;
}
this.edgeCount = this.edgeCount + 1;
}
// Perform DFS
public void findDFS(int v, Boolean[] visited)
{
// Indicates the current vertex is visited
visited[v] = true;
// iterate edges of v node
for (int i = 0; i < this.adgeList[v].Count; i++)
{
{
}
}
}
// Check that graph start vertices are reach to all other vertices or not
public Boolean isConnected()
{
Boolean[] visited = new Boolean[this.vertices];
// Set the initial visited vertices
for (int i = 0; i < this.vertices; ++i)
{
visited[i] = false;
}
this.findDFS(0, visited);
for (int i = 1; i < this.vertices; i++)
{
if (visited[i] == false)
{
// When [i] vertices are not visit
return false;
}
}
return true;
}
public void printGraph()
{
for (int i = 0; i < this.vertices; ++i)
{
Console.Write(" \n [" + i + "] :");
// iterate edges of i node
for (int j = 0; j < this.adgeList[i].Count; j++)
{
}
}
}
public void reverseDeleteMST()
{
int result = 0;
// Get first higher edge
Edge point = this.edges;
Console.WriteLine("\n\nConnected node by Edges in MST");
// iterates the edge from high to low order
while (point != null)
{
// Remove the current weight edge of node from u to v and v to u
if (this.isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
// Update weight
result += point.weight;
// Display edge
Console.Write(" (" + point.u + ", " + point.v + ") \n");
}
// Visit next smaller weight edge
point = point.next;
}
Console.WriteLine("Calculated total weight of MST is " + result);
}
public static void Main(String[] args)
{
Graph g = new Graph(8);
// Display graph element
g.printGraph();
// Find MST
g.reverseDeleteMST();
}
}``````

#### input

`````` Graph Adjacency List
 :  1  3
 :  0  2  6  7
 :  1  5  7
 :  0  4  7
 :  3  5  6  7
 :  2  4  6
 :  1  4  5
 :  1  2  3  4

Connected node by Edges in MST
(2, 5)
(4, 5)
(1, 6)
(0, 1)
(2, 7)
(1, 2)
(0, 3)
Calculated total weight of MST is 39``````
``````<?php
/*
Php Program
Reverse delete algorithm for minimum spanning tree
*/
class Edge
{
// edge weight or cost
public \$weight;
public \$u;
public \$v;
public \$next;
public  function __construct(\$weight, \$u, \$v)
{
\$this->weight = \$weight;
\$this->u = \$u;
\$this->v = \$v;
\$this->next = NULL;
}
}
class Graph
{
public \$vertices;
public \$edges;
public \$edgeCount;
public  function __construct(\$vertices)
{
\$this->vertices = \$vertices;
\$this->edges = NULL;
\$this->edgeCount = 0;
for (\$i = 0; \$i < \$this->vertices; ++\$i)
{
}
}
{
if (\$u < 0 || \$u >= \$this->vertices || \$v < 0 || \$v >= \$this->vertices)
{
return;
}
// Collect descending order sorted edges
// Create new edge
\$e = new Edge(\$w, \$u, \$v);
// Add edge in decreasing order
if (\$this->edges == NULL)
{
// First edge
\$this->edges = \$e;
}
else if (\$this->edges->weight <= \$e->weight)
{
\$e->next = \$this->edges;
\$this->edges = \$e;
}
else
{
\$temp = \$this->edges;
// Find position to add new edge
while (\$temp->next != NULL && \$temp->next->weight > \$e->weight)
{
\$temp = \$temp->next;
}
\$e->next = \$temp->next;
\$temp->next = \$e;
}
\$this->edgeCount = \$this->edgeCount + 1;
}
// Perform DFS
public  function findDFS(\$v, &\$visited)
{
// Indicates the current vertex is visited
\$visited[\$v] = true;

// iterate edges of v node
{
if (\$visited[\$value] == false)
{
\$this->findDFS(\$value, \$visited);
}
}
}
// Check that graph start vertices are reach to all other vertices or not
public  function isConnected()
{
\$visited = array_fill(0, \$this->vertices, false);
\$this->findDFS(0, \$visited);
for (\$i = 1; \$i < \$this->vertices; \$i++)
{
if (\$visited[\$i] == false)
{
// When [i] vertices are not visit
return false;
}
}
return true;
}
public  function printGraph()
{
for (\$i = 0; \$i < \$this->vertices; ++\$i)
{
echo(" \n [".\$i."] :");
// iterate edges of i node
for (\$j = 0; \$j < count(\$this->adgeList[\$i]); \$j++)
{
}
}
}
public  function reverseDeleteMST()
{
\$result = 0;
// Get first higher edge
\$point = \$this->edges;
echo("\n\nConnected node by Edges in MST"."\n");
// iterates the edge from high to low order
while (\$point != NULL)
{

// Remove the current weight edge of node from u to v and v to u
if ((\$key = array_search(\$point->v,

}

if ((\$key = array_search(\$point->u,

}

if (\$this->isConnected() == false )
{
// When delete edge are create problems ().
// Then they are add back into graph
// Update weight
\$result += \$point->weight;
// Display edge
echo(" (".\$point->u.
", ".\$point->v.
") \n");
}
// Visit next smaller weight edge
\$point = \$point->next;
}
echo("Calculated total weight of MST is ".\$result.
"\n");
}
}

function main()
{
\$g = new Graph(8);
// Display graph element
\$g->printGraph();
// Find MST
\$g->reverseDeleteMST();
}
main();``````

#### input

`````` Graph Adjacency List
 :  1  3
 :  0  2  6  7
 :  1  5  7
 :  0  4  7
 :  3  5  6  7
 :  2  4  6
 :  1  4  5
 :  1  2  3  4

Connected node by Edges in MST
(2, 5)
(4, 5)
(1, 6)
(0, 1)
(2, 7)
(1, 2)
(0, 3)
Calculated total weight of MST is 39``````
``````/*
Node JS Program
Reverse delete algorithm for minimum spanning tree
*/
class Edge
{
constructor(weight, u, v)
{
this.weight = weight;
this.u = u;
this.v = v;
this.next = null;
}
}
class Graph
{
constructor(vertices)
{
this.vertices = vertices;
this.edges = null;
this.edgeCount = 0;
for (var i = 0; i < this.vertices; ++i)
{
}
}
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
// Collect descending order sorted edges
// Create new edge
var e = new Edge(w, u, v);
// Add edge in decreasing order
if (this.edges == null)
{
// First edge
this.edges = e;
}
else if (this.edges.weight <= e.weight)
{
e.next = this.edges;
this.edges = e;
}
else
{
var temp = this.edges;
// Find position to add new edge
while (temp.next != null && temp.next.weight > e.weight)
{
temp = temp.next;
}
e.next = temp.next;
temp.next = e;
}
this.edgeCount = this.edgeCount + 1;
}
// Perform DFS
findDFS(v, visited)
{
// Indicates the current vertex is visited
visited[v] = true;
// iterate edges of v node
for (var i = 0; i < this.adgeList[v].length; i++)
{
{
}
}
}
// Check that graph start vertices are reach to all other vertices or not
isConnected()
{
var visited = Array(this.vertices).fill(false);
this.findDFS(0, visited);
for (var i = 1; i < this.vertices; i++)
{
if (visited[i] == false)
{
// When [i] vertices are not visit
return false;
}
}
return true;
}
printGraph()
{
for (var i = 0; i < this.vertices; ++i)
{
process.stdout.write(" \n [" + i + "] :");
// iterate edges of i node
for (var j = 0; j < this.adgeList[i].length; j++)
{
}
}
}
reverseDeleteMST()
{
var result = 0;
// Get first higher edge
var point = this.edges;
var index = 0;
console.log("\n\nConnected node by Edges in MST");
// iterates the edge from high to low order
while (point != null)
{
// Remove the current weight edge of node from u to v and v to u
if (index !== -1)
{
}
if (index !== -1)
{
}
if (this.isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
// Update weight
result += point.weight;
// Display edge
process.stdout.write(" (" + point.u + ", " + point.v + ") \n");
}
// Visit next smaller weight edge
point = point.next;
}
console.log("Calculated total weight of MST is " + result);
}
}

function main()
{
var g = new Graph(8);
// Display graph element
g.printGraph();
// Find MST
g.reverseDeleteMST();
}
main();``````

#### input

`````` Graph Adjacency List
 :  1  3
 :  0  2  6  7
 :  1  5  7
 :  0  4  7
 :  3  5  6  7
 :  2  4  6
 :  1  4  5
 :  1  2  3  4

Connected node by Edges in MST
(2, 5)
(4, 5)
(1, 6)
(0, 1)
(2, 7)
(1, 2)
(0, 3)
Calculated total weight of MST is 39``````
``````#    Python 3 Program
#    Reverse delete algorithm for minimum spanning tree
class Edge :
#  edge weight or cost
def __init__(self, weight, u, v) :
self.weight = weight
self.u = u
self.v = v
self.next = None

class Graph :
def __init__(self, vertices) :
self.vertices = vertices
self.edges = None
self.edgeCount = 0
i = 0
while (i < self.vertices) :
i += 1

def addEdge(self, u, v, w) :
if (u < 0 or u >= self.vertices or v < 0 or v >= self.vertices) :
return

#  Collect descending order sorted edges
#  Create new edge
e = Edge(w, u, v)
#  Add edge in decreasing order
if (self.edges == None) :
#  First edge
self.edges = e
elif (self.edges.weight <= e.weight) :
e.next = self.edges
self.edges = e
else :
temp = self.edges
#  Find position to add new edge
while (temp.next != None and temp.next.weight > e.weight) :
temp = temp.next

e.next = temp.next
temp.next = e

self.edgeCount = self.edgeCount + 1

#  Perform DFS
def findDFS(self, v, visited) :
#  Indicates the current vertex is visited
visited[v] = True
i = 0
#  iterate edges of v node

i += 1

#  Check that graph start vertices are reach to all other vertices or not
def isConnected(self) :
visited = [False] * (self.vertices)
i = 0
#  Set the initial visited vertices
while (i < self.vertices) :
visited[i] = False
i += 1

self.findDFS(0, visited)
i = 1
while (i < self.vertices) :
if (visited[i] == False) :
#  When [i] vertices are not visit
return False

i += 1

return True

def printGraph(self) :
print("\n Graph Adjacency List ", end = "")
i = 0
while (i < self.vertices) :
print(" \n [", i ,"] :", end = "")
j = 0
#  iterate edges of i node
print("  ", self.adgeList[i][j], end = "")
j += 1

i += 1

def reverseDeleteMST(self) :
result = 0
#  Get first higher edge
point = self.edges
print("\n\nConnected node by Edges in MST")
#  iterates the edge from high to low order
while (point != None) :
#  Remove the current weight edge of node from u to v and v to u
if (self.isConnected() == False) :
#  When delete edge are create problems ().
#  Then they are add back into graph
#  Update weight
result += point.weight
#  Display edge
print(" (", point.u ,", ", point.v ,") ")

#  Visit next smaller weight edge
point = point.next

print("Calculated total weight of MST is ", result)

def main() :
g = Graph(8)
#  Display graph element
g.printGraph()
#  Find MST
g.reverseDeleteMST()

if __name__ == "__main__": main()``````

#### input

`````` Graph Adjacency List
[ 0 ] :   1   3
[ 1 ] :   0   2   6   7
[ 2 ] :   1   5   7
[ 3 ] :   0   4   7
[ 4 ] :   3   5   6   7
[ 5 ] :   2   4   6
[ 6 ] :   1   4   5
[ 7 ] :   1   2   3   4

Connected node by Edges in MST
( 2 ,  5 )
( 4 ,  5 )
( 1 ,  6 )
( 0 ,  1 )
( 2 ,  7 )
( 1 ,  2 )
( 0 ,  3 )
Calculated total weight of MST is  39``````
``````#    Ruby Program
#    Reverse delete algorithm for minimum spanning tree
class Edge
# Define the accessor and reader of class Edge
attr_accessor :weight, :u, :v, :next
#  edge weight or cost
def initialize(weight, u, v)
self.weight = weight
self.u = u
self.v = v
self.next = nil
end

end

class Graph
# Define the accessor and reader of class Graph
def initialize(vertices)
self.vertices = vertices
self.edges = nil
self.edgeCount = 0
i = 0
while (i < self.vertices)
i += 1
end

end

if (u < 0 || u >= self.vertices || v < 0 || v >= self.vertices)
return
end

#  Collect descending order sorted edges
#  Create new edge
e = Edge.new(w, u, v)
#  Add edge in decreasing order
if (self.edges == nil)
#  First edge
self.edges = e
elsif (self.edges.weight <= e.weight)
e.next = self.edges
self.edges = e
else

temp = self.edges
#  Find position to add new edge
while (temp.next != nil && temp.next.weight > e.weight)
temp = temp.next
end

e.next = temp.next
temp.next = e
end

self.edgeCount = self.edgeCount + 1
end

#  Perform DFS
def findDFS(v, visited)
#  Indicates the current vertex is visited
visited[v] = true
#  iterate edges of v node
if (visited[i] == false)
self.findDFS(i, visited)
end
i += 1
end

end

#  Check that graph start vertices are reach to all other vertices or not
def isConnected()
visited = Array.new(self.vertices) {false}
i = 0
#  Set the initial visited vertices
while (i < self.vertices)
visited[i] = false
i += 1
end

self.findDFS(0, visited)
i = 1
while (i < self.vertices)
if (visited[i] == false)
#  When [i] vertices are not visit
return false
end

i += 1
end

return true
end

def printGraph()
i = 0
while (i < self.vertices)
print(" \n [", i ,"] :")
j = 0
#  iterate edges of i node
j += 1
end

i += 1
end

end

def reverseDeleteMST()
result = 0
#  Get first higher edge
point = self.edges
print("\n\nConnected node by Edges in MST", "\n")
#  iterates the edge from high to low order
while (point != nil)

#  Remove the current weight edge of node from u to v and v to u

if (self.isConnected() == false)
#  When delete edge are create problems ().
#  Then they are add back into graph
#  Update weight
result += point.weight
#  Display edge
print(" (", point.u ,", ", point.v ,") \n")
end

#  Visit next smaller weight edge
point = point.next
end

print("Calculated total weight of MST is ", result, "\n")
end

end

def main()
g = Graph.new(8)
#  Display graph element
g.printGraph()
#  Find MST
g.reverseDeleteMST()
end

main()``````

#### input

`````` Graph Adjacency List
 :  1  3
 :  0  2  6  7
 :  1  5  7
 :  0  4  7
 :  3  5  6  7
 :  2  4  6
 :  1  4  5
 :  1  2  3  4

Connected node by Edges in MST
(2, 5)
(4, 5)
(1, 6)
(0, 1)
(2, 7)
(1, 2)
(0, 3)
Calculated total weight of MST is 39
``````
``````import scala.collection.mutable._;
/*
Scala Program
Reverse delete algorithm for minimum spanning tree
*/
class Edge(
// edge weight or cost
var weight: Int,
var u: Int,
var v: Int,
var next: Edge)
{
def this(weight: Int, u: Int, v: Int)
{
this(weight, u,v,null);
}
}
class Graph(var vertices: Int,
var edges: Edge,
var edgeCount: Int)
{
def this(vertices: Int)
{
this(vertices,new ArrayBuffer[ArrayBuffer[Int]](vertices), null,0);
var i: Int = 0;
while (i < this.vertices)
{
i += 1;
}
}
def addEdge(u: Int, v: Int, w: Int): Unit = {
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
// Collect descending order sorted edges
// Create new edge
var e: Edge = new Edge(w, u, v);
// Add edge in decreasing order
if (this.edges == null)
{
// First edge
this.edges = e;
}
else if (this.edges.weight <= e.weight)
{
e.next = this.edges;
this.edges = e;
}
else
{
var temp: Edge = this.edges;
// Find position to add new edge
while (temp.next != null && temp.next.weight > e.weight)
{
temp = temp.next;
}
e.next = temp.next;
temp.next = e;
}
this.edgeCount = this.edgeCount + 1;
}
// Perform DFS
def findDFS(v: Int, visited: Array[Boolean]): Unit = {
// Indicates the current vertex is visited
visited(v) = true;
var i: Int = 0;
// iterate edges of v node
{
{
}
i += 1;
}
}
// Check that graph start vertices are reach to all other vertices or not
def isConnected(): Boolean = {
var visited: Array[Boolean] = Array.fill[Boolean](this.vertices)(false);
this.findDFS(0, visited);
var i: Int = 1;
while (i < this.vertices)
{
if (visited(i) == false)
{
// When [i] vertices are not visit
return false;
}
i += 1;
}
return true;
}
def printGraph(): Unit = {
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
{
j += 1;
}
i += 1;
}
}
def reverseDeleteMST(): Unit = {
var result: Int = 0;
// Get first higher edge
var point: Edge = this.edges;
println("\n\nConnected node by Edges in MST");
// iterates the edge from high to low order
while (point != null)
{
// Remove the current weight edge of node from u to v and v to u
if (isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
// Update weight
result += point.weight;
// Display edge
print(" (" + point.u + ", " + point.v + ") \n");
}
// Visit next smaller weight edge
point = point.next;
}
println("Calculated total weight of MST is " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var g: Graph = new Graph(8);
// Display graph element
g.printGraph();
// Find MST
g.reverseDeleteMST();
}
}``````

#### input

`````` Graph Adjacency List
 :  1  3
 :  0  2  6  7
 :  1  5  7
 :  0  4  7
 :  3  5  6  7
 :  2  4  6
 :  1  4  5
 :  1  2  3  4

Connected node by Edges in MST
(2, 5)
(4, 5)
(1, 6)
(0, 1)
(2, 7)
(1, 2)
(0, 3)
Calculated total weight of MST is 39``````
``````import Foundation;
/*
Swift 4 Program
Reverse delete algorithm for minimum spanning tree
*/
class Edge
{
// edge weight or cost
var weight: Int;
var u: Int;
var v: Int;
var next: Edge? ;
init(_ weight: Int, _ u: Int, _ v: Int)
{
self.weight = weight;
self.u = u;
self.v = v;
self.next = nil;
}
}
class Graph
{
var vertices: Int;
[Int]
];
var edges: Edge? ;
var edgeCount: Int;
init(_ vertices: Int)
{
self.vertices = vertices;
self.edges = nil;
self.edgeCount = 0;
var i = 0;
while (i < self.vertices)
{
i += 1;
}
}
func addEdge(_ u: Int, _ v: Int, _ w: Int)
{
if (u < 0 || u >= self.vertices || v < 0 || v >= self.vertices)
{
return;
}
// Collect descending order sorted edges
// Create new edge
let e = Edge(w, u, v);
// Add edge in decreasing order
if (self.edges == nil)
{
// First edge
self.edges = e;
}
else if (self.edges!.weight <= e.weight)
{
e.next = self.edges;
self.edges = e;
}
else
{
var temp = self.edges;
// Find position to add new edge
while (temp!.next  != nil && temp!.next!.weight > e.weight)
{
temp = temp!.next;
}
e.next = temp!.next;
temp!.next = e;
}
self.edgeCount = self.edgeCount + 1;
}
// Perform DFS
func findDFS(_ v: Int, _ visited: inout[Bool])
{
// Indicates the current vertex is visited
visited[v] = true;
var i = 0;
// iterate edges of v node
{
{
}
i += 1;
}
}
// Check that graph start vertices are reach to all other vertices or not
func isConnected() -> Bool
{
var visited = Array(repeating: false, count: self.vertices);

self.findDFS(0, &visited);
var i = 1;
while (i < self.vertices)
{
if (visited[i] == false)
{
// When [i] vertices are not visit
return false;
}
i += 1;
}
return true;
}
func printGraph()
{
print("\n Graph Adjacency List ", terminator: "");
var i = 0;
while (i < self.vertices)
{
print(" \n [", i ,"] :", terminator: "");
var j = 0;
// iterate edges of i node
{
j += 1;
}
i += 1;
}
}
func reverseDeleteMST()
{
var result = 0;
// Get first higher edge
var point = self.edges;
print("\n\nConnected node by Edges in MST");
// iterates the edge from high to low order
while (point  != nil)
{
// Remove the current weight edge of node from u to v and v to u
if let k1 = self.adgeList[point!.u].index(of:point!.v) {
}
if let k2 = self.adgeList[point!.v].index(of:point!.u) {
}

if (self.isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
// Update weight
result += point!.weight;
// Display edge
print(" (", point!.u ,", ", point!.v ,") ");
}
// Visit next smaller weight edge
point = point!.next;
}
print("Calculated total weight of MST is ", result);
}
}
func main()
{
let g = Graph(8);
// Display graph element
g.printGraph();
// Find MST
g.reverseDeleteMST();
}
main();``````

#### input

`````` Graph Adjacency List
[ 0 ] :   1   3
[ 1 ] :   0   2   6   7
[ 2 ] :   1   5   7
[ 3 ] :   0   4   7
[ 4 ] :   3   5   6   7
[ 5 ] :   2   4   6
[ 6 ] :   1   4   5
[ 7 ] :   1   2   3   4

Connected node by Edges in MST
( 2 ,  5 )
( 4 ,  5 )
( 1 ,  6 )
( 0 ,  1 )
( 2 ,  7 )
( 1 ,  2 )
( 0 ,  3 )
Calculated total weight of MST is  39``````
``````/*
Kotlin Program
Reverse delete algorithm for minimum spanning tree
*/
class Edge
{
// edge weight or cost
var weight: Int;
var u: Int;
var v: Int;
var next: Edge ? ;
constructor(weight: Int, u: Int, v: Int)
{
this.weight = weight;
this.u = u;
this.v = v;
this.next = null;
}
}
class Graph
{
var vertices: Int;
var edges: Edge ? ;
var edgeCount: Int;
constructor(vertices: Int)
{
this.vertices = vertices;
this.edges = null;
this.edgeCount = 0;
var i: Int = 0;
while (i < this.vertices)
{
i += 1;
}
}
fun addEdge(u: Int, v: Int, w: Int): Unit
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
// Collect descending order sorted edges
// Create new edge
val e: Edge = Edge(w, u, v);
// Add edge in decreasing order
if (this.edges == null)
{
// First edge
this.edges = e;
}
else if (this.edges!!.weight <= e.weight)
{
e.next = this.edges;
this.edges = e;
}
else
{
var temp: Edge? = this.edges;
// Find position to add new edge
while ( temp?.next != null
&& temp.next!!.weight > e.weight)
{
temp = temp.next;
}
e.next = temp?.next;
temp?.next = e;
}
this.edgeCount = this.edgeCount + 1;
}
// Perform DFS
fun findDFS(v: Int, visited: Array < Boolean > ): Unit
{
// Indicates the current vertex is visited
visited[v] = true;
var i: Int = 0;
// iterate edges of v node
{
{
}
i += 1;
}
}
// Check that graph start vertices are reach to all other vertices or not
fun isConnected(): Boolean
{
val visited: Array < Boolean > = Array(this.vertices)
{
false
};
this.findDFS(0, visited);
var i: Int = 1;
while (i < this.vertices)
{
if (visited[i] == false)
{
// When [i] vertices are not visit
return false;
}
i += 1;
}
return true;
}
fun printGraph(): Unit
{
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
{
j += 1;
}
i += 1;
}
}
fun reverseDeleteMST(): Unit
{
var result: Int = 0;
// Get first higher edge
var point: Edge ? = this.edges;
println("\n\nConnected node by Edges in MST");
// iterates the edge from high to low order
while (point != null)
{
// Remove the current weight edge of node from u to v and v to u
if (this.isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
// Update weight
result += point.weight;
// Display edge
print(" (" + point.u + ", " + point.v + ") \n");
}
// Visit next smaller weight edge
point = point.next;
}
println("Calculated total weight of MST is " + result);
}
}
fun main(args: Array < String > ): Unit
{
val g: Graph = Graph(8);
// Display graph element
g.printGraph();
// Find MST
g.reverseDeleteMST();
}``````

#### input

`````` Graph Adjacency List
 :  1  3
 :  0  2  6  7
 :  1  5  7
 :  0  4  7
 :  3  5  6  7
 :  2  4  6
 :  1  4  5
 :  1  2  3  4

Connected node by Edges in MST
(2, 5)
(4, 5)
(1, 6)
(0, 1)
(2, 7)
(1, 2)
(0, 3)
Calculated total weight of MST is 39``````

## Output Explanation

The output displays the adjacency list of the graph along with the edges that are part of the minimum spanning tree. Each edge `(u, v)` indicates that there is a connection between vertex `u` and vertex `v` in the minimum spanning tree. The total weight of the minimum spanning tree is also calculated and printed.

## Time Complexity

The time complexity of the reverse delete algorithm mainly depends on the sorting of the edges, which takes O(E log E) time. Additionally, for each edge, the algorithm checks connectivity using the Depth-First Search (DFS) method, which has a time complexity of O(V + E). Therefore, the overall time complexity is dominated by O(E log E), where E is the number of edges.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post