Reverse delete algorithm for minimum spanning tree
The Reverse Delete Algorithm is a heuristic algorithm used to find the Minimum Spanning Tree (MST) of a graph. The algorithm works by removing edges from the graph in a specific order and checking whether the graph still remains connected.
Here are the steps for the Reverse Delete Algorithm:

Start with the full graph, including all edges and vertices.
Sort the edges in decreasing order of weight (from the largest to the smallest).
Iterate through the sorted edges, and for each edge, check if the graph remains connected after removing that edge. If the graph remains connected, keep the edge. Otherwise, discard the edge.
Stop when all edges have been checked, or when the graph has become disconnected.
The remaining edges form the Minimum Spanning Tree of the graph.
The Reverse Delete Algorithm is called so because it works in reverse order compared to the Kruskal's Algorithm. Kruskal's Algorithm starts with no edges and adds edges one by one to form the MST. On the other hand, the Reverse Delete Algorithm starts with all edges and removes edges one by one to form the MST.
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)
{
this.adgeList.add(new ArrayList < Integer > ());
}
}
public void addEdge(int u, int v, int w)
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
// add node edge
adgeList.get(u).add(v);
adgeList.get(v).add(u);
// 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)
{
// Add edges in front
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++)
{
if (visited[this.adgeList.get(v).get(i)] == false)
{
findDFS(this.adgeList.get(v).get(i), visited);
}
}
}
// 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()
{
System.out.print("\n Graph Adjacency List ");
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++)
{
System.out.print(" " + this.adgeList.get(i).get(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
adgeList.get(point.u).remove(new Integer(point.v));
adgeList.get(point.v).remove(new Integer(point.u));
if (isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
adgeList.get(point.u).add(point.v);
adgeList.get(point.v).add(point.u);
// 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);
g.addEdge(0, 1, 5);
g.addEdge(0, 3, 3);
g.addEdge(1, 2, 3);
g.addEdge(1, 6, 7);
g.addEdge(1, 7, 9);
g.addEdge(2, 5, 9);
g.addEdge(2, 7, 4);
g.addEdge(3, 4, 11);
g.addEdge(3, 7, 8);
g.addEdge(4, 5, 8);
g.addEdge(4, 6, 14);
g.addEdge(4, 7, 10);
g.addEdge(5, 6, 11);
// Display graph element
g.printGraph();
// Find MST
g.reverseDeleteMST();
}
}
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
// 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;
vector <vector<int> > adgeList;
Edge *edges;
int edgeCount;
Graph(int vertices)
{
this->vertices = vertices;
this->edges = NULL;
this->edgeCount = 0;
for(int i = 0 ; i < vertices; ++i)
{
this->adgeList.push_back(vector<int>());
}
}
void addEdge(int u, int v, int w)
{
if (u < 0 || u >= this->vertices || v < 0 || v >= this->vertices)
{
return;
}
// add node edge
this->adgeList.at(u).push_back(v);
this->adgeList.at(v).push_back(u);
// 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)
{
// Add edges in front
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++)
{
if (visited[this->adgeList.at(v).at(i)] == false)
{
this->findDFS(this->adgeList.at(v).at(i), visited);
}
}
}
// 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
this->adgeList.at(point->u).erase(remove(this->adgeList.at(point->u).begin(), this->adgeList.at(point->u).end(), point->v), this->adgeList.at(point->u).end());
this->adgeList.at(point->v).erase(remove(this->adgeList.at(point->v).begin(), this->adgeList.at(point->v).end(), point->u), this->adgeList.at(point->v).end());
if (this->isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
this->adgeList.at(point->u).push_back(point->v);
this->adgeList.at(point->v).push_back(point->u);
// 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);
g->addEdge(0, 1, 5);
g->addEdge(0, 3, 3);
g->addEdge(1, 2, 3);
g->addEdge(1, 6, 7);
g->addEdge(1, 7, 9);
g->addEdge(2, 5, 9);
g->addEdge(2, 7, 4);
g->addEdge(3, 4, 11);
g->addEdge(3, 7, 8);
g->addEdge(4, 5, 8);
g->addEdge(4, 6, 14);
g->addEdge(4, 7, 10);
g->addEdge(5, 6, 11);
// Display graph element
g->printGraph();
// Find MST
g->reverseDeleteMST();
return 0;
}
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
// 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)
{
this.adgeList.Add(new List < int > ());
}
}
public void addEdge(int u, int v, int w)
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
// add node edge
this.adgeList[u].Add(v);
this.adgeList[v].Add(u);
// 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)
{
// Add edges in front
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++)
{
if (visited[this.adgeList[v][i]] == false)
{
this.findDFS(this.adgeList[v][i], visited);
}
}
}
// 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()
{
Console.Write("\n Graph Adjacency List ");
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++)
{
Console.Write(" " + this.adgeList[i][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
this.adgeList[point.u].Remove(point.v);
this.adgeList[point.v].Remove(point.u);
if (this.isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
this.adgeList[point.u].Add(point.v);
this.adgeList[point.v].Add(point.u);
// 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);
g.addEdge(0, 1, 5);
g.addEdge(0, 3, 3);
g.addEdge(1, 2, 3);
g.addEdge(1, 6, 7);
g.addEdge(1, 7, 9);
g.addEdge(2, 5, 9);
g.addEdge(2, 7, 4);
g.addEdge(3, 4, 11);
g.addEdge(3, 7, 8);
g.addEdge(4, 5, 8);
g.addEdge(4, 6, 14);
g.addEdge(4, 7, 10);
g.addEdge(5, 6, 11);
// Display graph element
g.printGraph();
// Find MST
g.reverseDeleteMST();
}
}
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
<?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 $adgeList;
public $edges;
public $edgeCount;
public function __construct($vertices)
{
$this->vertices = $vertices;
$this->adgeList = array();
$this->edges = NULL;
$this->edgeCount = 0;
for ($i = 0; $i < $this->vertices; ++$i)
{
$this->adgeList[$i] = array();
}
}
public function addEdge($u, $v, $w)
{
if ($u < 0 || $u >= $this->vertices || $v < 0 || $v >= $this->vertices)
{
return;
}
// add node edge
$this->adgeList[$u][] = $v;
$this->adgeList[$v][] = $u;
// 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)
{
// Add edges in front
$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
foreach ($this->adgeList[$v] as $key=>$value)
{
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()
{
echo("\n Graph Adjacency List ");
for ($i = 0; $i < $this->vertices; ++$i)
{
echo(" \n [".$i."] :");
// iterate edges of i node
for ($j = 0; $j < count($this->adgeList[$i]); $j++)
{
echo(" ".$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,
$this->adgeList[$point->u])) !== false) {
unset($this->adgeList[$point->u][$key]);
}
if (($key = array_search($point->u,
$this->adgeList[$point->v])) !== false) {
unset($this->adgeList[$point->v][$key]);
}
if ($this->isConnected() == false )
{
// When delete edge are create problems ().
// Then they are add back into graph
$this->adgeList[$point->u][] = $point->v;
$this->adgeList[$point->v][] = $point->u;
// 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);
$g->addEdge(0, 1, 5);
$g->addEdge(0, 3, 3);
$g->addEdge(1, 2, 3);
$g->addEdge(1, 6, 7);
$g->addEdge(1, 7, 9);
$g->addEdge(2, 5, 9);
$g->addEdge(2, 7, 4);
$g->addEdge(3, 4, 11);
$g->addEdge(3, 7, 8);
$g->addEdge(4, 5, 8);
$g->addEdge(4, 6, 14);
$g->addEdge(4, 7, 10);
$g->addEdge(5, 6, 11);
// 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
/*
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.adgeList = [];
this.edges = null;
this.edgeCount = 0;
for (var i = 0; i < this.vertices; ++i)
{
this.adgeList.push([]);
}
}
addEdge(u, v, w)
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
// add node edge
this.adgeList[u].push(v);
this.adgeList[v].push(u);
// 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)
{
// Add edges in front
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++)
{
if (visited[this.adgeList[v][i]] == false)
{
this.findDFS(this.adgeList[v][i], visited);
}
}
}
// 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()
{
process.stdout.write("\n Graph Adjacency List ");
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++)
{
process.stdout.write(" " + this.adgeList[i][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
index = this.adgeList[point.u].indexOf(point.v);
if (index !== -1)
{
this.adgeList[point.u].splice(index, 1);
}
index = this.adgeList[point.v].indexOf(point.u);
if (index !== -1)
{
this.adgeList[point.v].splice(index, 1);
}
if (this.isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
this.adgeList[point.u].push(point.v);
this.adgeList[point.v].push(point.u);
// 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);
g.addEdge(0, 1, 5);
g.addEdge(0, 3, 3);
g.addEdge(1, 2, 3);
g.addEdge(1, 6, 7);
g.addEdge(1, 7, 9);
g.addEdge(2, 5, 9);
g.addEdge(2, 7, 4);
g.addEdge(3, 4, 11);
g.addEdge(3, 7, 8);
g.addEdge(4, 5, 8);
g.addEdge(4, 6, 14);
g.addEdge(4, 7, 10);
g.addEdge(5, 6, 11);
// 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
# 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.adgeList = []
self.edges = None
self.edgeCount = 0
i = 0
while (i < self.vertices) :
self.adgeList.append([])
i += 1
def addEdge(self, u, v, w) :
if (u < 0 or u >= self.vertices or v < 0 or v >= self.vertices) :
return
# add node edge
self.adgeList[u].append(v)
self.adgeList[v].append(u)
# 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) :
# Add edges in front
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
while (i < len(self.adgeList[v])) :
if (visited[self.adgeList[v][i]] == False) :
self.findDFS(self.adgeList[v][i], visited)
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
while (j < len(self.adgeList[i])) :
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
self.adgeList[point.u].remove(point.v)
self.adgeList[point.v].remove(point.u)
if (self.isConnected() == False) :
# When delete edge are create problems ().
# Then they are add back into graph
self.adgeList[point.u].append(point.v)
self.adgeList[point.v].append(point.u)
# 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)
g.addEdge(0, 1, 5)
g.addEdge(0, 3, 3)
g.addEdge(1, 2, 3)
g.addEdge(1, 6, 7)
g.addEdge(1, 7, 9)
g.addEdge(2, 5, 9)
g.addEdge(2, 7, 4)
g.addEdge(3, 4, 11)
g.addEdge(3, 7, 8)
g.addEdge(4, 5, 8)
g.addEdge(4, 6, 14)
g.addEdge(4, 7, 10)
g.addEdge(5, 6, 11)
# 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_reader :weight, :u, :v, :next
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
attr_reader :vertices, :adgeList, :edges, :edgeCount
attr_accessor :vertices, :adgeList, :edges, :edgeCount
def initialize(vertices)
self.vertices = vertices
self.adgeList = []
self.edges = nil
self.edgeCount = 0
i = 0
while (i < self.vertices)
self.adgeList.push([])
i += 1
end
end
def addEdge(u, v, w)
if (u < 0 || u >= self.vertices || v < 0 || v >= self.vertices)
return
end
# add node edge
self.adgeList[u].push(v)
self.adgeList[v].push(u)
# 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)
# Add edges in front
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
for i in self.adgeList[v]
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()
print("\n Graph Adjacency List ")
i = 0
while (i < self.vertices)
print(" \n [", i ,"] :")
j = 0
# iterate edges of i node
while (j < self.adgeList[i].length)
print(" ", self.adgeList[i][j])
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
self.adgeList[point.u] -= [point.v]
self.adgeList[point.v] -= [point.u]
if (self.isConnected() == false)
# When delete edge are create problems ().
# Then they are add back into graph
self.adgeList[point.u].push(point.v)
self.adgeList[point.v].push(point.u)
# 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)
g.addEdge(0, 1, 5)
g.addEdge(0, 3, 3)
g.addEdge(1, 2, 3)
g.addEdge(1, 6, 7)
g.addEdge(1, 7, 9)
g.addEdge(2, 5, 9)
g.addEdge(2, 7, 4)
g.addEdge(3, 4, 11)
g.addEdge(3, 7, 8)
g.addEdge(4, 5, 8)
g.addEdge(4, 6, 14)
g.addEdge(4, 7, 10)
g.addEdge(5, 6, 11)
# Display graph element
g.printGraph()
# Find MST
g.reverseDeleteMST()
end
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
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 adgeList: ArrayBuffer[ArrayBuffer[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)
{
this.adgeList += new ArrayBuffer[Int]();
i += 1;
}
}
def addEdge(u: Int, v: Int, w: Int): Unit = {
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
// add node edge
adgeList(u) += v;
adgeList(v) += u;
// 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)
{
// Add edges in front
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
while (i < this.adgeList(v).size)
{
if (visited(this.adgeList(v)(i)) == false)
{
findDFS(this.adgeList(v)(i), visited);
}
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 = {
print("\n Graph Adjacency List ");
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
while (j < this.adgeList(i).size)
{
print(" " + this.adgeList(i)(j));
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
adgeList(point.u) -= point.v;
adgeList(point.v) -= point.u;
if (isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
adgeList(point.u) += point.v;
adgeList(point.v) += point.u;
// 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);
g.addEdge(0, 1, 5);
g.addEdge(0, 3, 3);
g.addEdge(1, 2, 3);
g.addEdge(1, 6, 7);
g.addEdge(1, 7, 9);
g.addEdge(2, 5, 9);
g.addEdge(2, 7, 4);
g.addEdge(3, 4, 11);
g.addEdge(3, 7, 8);
g.addEdge(4, 5, 8);
g.addEdge(4, 6, 14);
g.addEdge(4, 7, 10);
g.addEdge(5, 6, 11);
// Display graph element
g.printGraph();
// Find MST
g.reverseDeleteMST();
}
}
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
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;
var adgeList: [
[Int]
];
var edges: Edge? ;
var edgeCount: Int;
init(_ vertices: Int)
{
self.vertices = vertices;
self.adgeList = [[Int]]();
self.edges = nil;
self.edgeCount = 0;
var i = 0;
while (i < self.vertices)
{
self.adgeList.append([Int]());
i += 1;
}
}
func addEdge(_ u: Int, _ v: Int, _ w: Int)
{
if (u < 0 || u >= self.vertices || v < 0 || v >= self.vertices)
{
return;
}
// add node edge
self.adgeList[u].append(v);
self.adgeList[v].append(u);
// 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)
{
// Add edges in front
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
while (i < self.adgeList[v].count)
{
if (visited[self.adgeList[v][i]] == false)
{
self.findDFS(self.adgeList[v][i], &visited);
}
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
while (j < self.adgeList[i].count)
{
print(" ", self.adgeList[i][j], terminator: "");
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) {
self.adgeList[point!.u].remove(at: k1)
}
if let k2 = self.adgeList[point!.v].index(of:point!.u) {
self.adgeList[point!.v].remove(at: k2)
}
if (self.isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
self.adgeList[point!.u].append(point!.v);
self.adgeList[point!.v].append(point!.u);
// 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);
g.addEdge(0, 1, 5);
g.addEdge(0, 3, 3);
g.addEdge(1, 2, 3);
g.addEdge(1, 6, 7);
g.addEdge(1, 7, 9);
g.addEdge(2, 5, 9);
g.addEdge(2, 7, 4);
g.addEdge(3, 4, 11);
g.addEdge(3, 7, 8);
g.addEdge(4, 5, 8);
g.addEdge(4, 6, 14);
g.addEdge(4, 7, 10);
g.addEdge(5, 6, 11);
// 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 adgeList: MutableList <MutableList<Int>> ;
var edges: Edge ? ;
var edgeCount: Int;
constructor(vertices: Int)
{
this.vertices = vertices;
this.adgeList = mutableListOf<MutableList<Int>>();
this.edges = null;
this.edgeCount = 0;
var i: Int = 0;
while (i < this.vertices)
{
this.adgeList.add(mutableListOf<Int>());
i += 1;
}
}
fun addEdge(u: Int, v: Int, w: Int): Unit
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
// add node edge
this.adgeList[u].add(v);
this.adgeList[v].add(u);
// 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)
{
// Add edges in front
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
while (i < this.adgeList[v].size)
{
if (visited[this.adgeList[v][i]] == false)
{
this.findDFS(this.adgeList[v][i], visited);
}
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
{
print("\n Graph Adjacency List ");
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
while (j < this.adgeList[i].size)
{
print(" " + this.adgeList[i][j]);
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
this.adgeList[point.u].remove(point.v);
this.adgeList[point.v].remove(point.u);
if (this.isConnected() == false)
{
// When delete edge are create problems ().
// Then they are add back into graph
this.adgeList[point.u].add(point.v);
this.adgeList[point.v].add(point.u);
// 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);
g.addEdge(0, 1, 5);
g.addEdge(0, 3, 3);
g.addEdge(1, 2, 3);
g.addEdge(1, 6, 7);
g.addEdge(1, 7, 9);
g.addEdge(2, 5, 9);
g.addEdge(2, 7, 4);
g.addEdge(3, 4, 11);
g.addEdge(3, 7, 8);
g.addEdge(4, 5, 8);
g.addEdge(4, 6, 14);
g.addEdge(4, 7, 10);
g.addEdge(5, 6, 11);
// Display graph element
g.printGraph();
// Find MST
g.reverseDeleteMST();
}
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
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.
New Comment