Introduction
In graph theory, the reverse-delete Algorithm is a method for creating a minimum spanning tree from a connected, edge-weighted graph. When compared to Kruskal's Algorithm, which also appears in the same work, it initially appeared in Kruskal. This approach will locate a minimum spanning tree for each disconnected portion of the graph if it is disconnected. Every vertex in the graph is contained within the collection of these minimal-spanning trees, known as a minimum-spanning forest.
Reverse Delete Algorithm
- By weight, order the edges
- Set up MST with all edges.
- The highest weight edge should be removed.
- Restore the edge if removing it causes the graph to become disconnected.
- Otherwise, keep going
Example
- The values close to the edge show their edge weight.
- This graph's minimum spanning tree is:
- Let's use the graph to perform the Reverse Delete Algorithm:
- We begin with Edges 3 to 4, which have the highest weight.
- Since removing edges 3 and 4 does not cause the graph to become disconnected, the edge may be deleted.
- Pick the edge 5-6 with weight 11 next. Since removing edges 5 and 6 does not cause the graph to become disconnected, the edge may be deleted.
- Pick the 1-3 edge with weight 9. Since removing edges 1-3 does not cause the graph to become disconnected, the edge may be deleted.
- Choose the edge 4-6 with weight nine next. The graph will become disconnected if this edge is removed because Node 6 will be split apart. We, therefore, do not remove the edge.
- Choose edge 2 with weight 8 next. Since removing edges 1-2 does not cause the graph to become disconnected, the edge may be deleted.
Code
Now let’s see the code in different languages like Java, C++, and Python.
Java Code
import java.util.arrlist;
class Edge
{
public int w;
public int u;
public int v;
public Edge n;
public Edge(int w, int u, int v)
{
this.w = w;
this.u = u;
this.v = v;
this.n = null;
}
}
public class grp
{
public int ver;
public arrlist < arrlist < Integer >> adgeList;
public Edge edge;
public int edgecounter;
public grp(int ver)
{
this.ver = ver;
this.adgeList = new arrlist < arrlist < Integer >> (ver);
this.edge = null;
this.edgecounter = 0;
int i;
for (i = 0; i < this.ver; ++i)
{
this.adgeList.add(new arrlist < Integer > ());
}
}
public boolean connected()
{
boolean[] reached = new boolean[this.ver];
// Set the initial reached ver
int i;
for (i = 0; i < this.ver; ++i)
{
reached[i] = false;
}
this.DFS(0, reached);
for (i = 1; i < this.ver; i++)
{
if (reached[i] == false)
{
return false;
}
}
return true;
}
public void add_edge_1(int u, int v, int w)
{
if (u < 0 || u >= this.ver || v < 0 || v >= this.ver)
{
return;
}
adgeList.get(u).add(v);
adgeList.get(v).add(u);
Edge e = new Edge(w, u, v);
if (this.edge == null)
{
this.edge = e;
}
else if (this.edge.w <= e.w)
{
e.n = this.edge;
this.edge = e;
}
else
{
Edge temp = this.edge;
while (temp.n != null && temp.n.w > e.w)
{
temp = temp.n;
}
e.n = temp.n;
temp.n = e;
}
this.edgecounter = this.edgecounter + 1;
}
public void printgrp()
{
int i;
System.out.print("\n grp Adjacency List ");
for (i = 0; i < this.ver; ++i)
{
System.out.print(" \n [" + i + "] :");
for (int j = 0; j < this.adgeList1.get(i).size(); j++)
{
System.out.print(" " + this.adgeList1.get(i).get(j));
}
}
}
public void DFS_1(int v, boolean[] reached)
{
reached[v] = true;
for (int i = 0; i < this.adgeList1.get(v).size(); i++)
{
if (reached[this.adgeList1.get(v).get(i)] == false)
{
DFS_1(this.adgeList1.get(v).get(i), reached);
}
}
}
public void rev_dlt_MST()
{
int result = 0;
Edge pt = this.edge;
System.out.println("\n\n nodes are nonnected by edge in mst");
while (pt != null)
{
adgeList.get(pt.u).remove(new Integer(pt.v));
adgeList.get(pt.v).remove(new Integer(pt.u));
if (connected() == false)
{
adgeList.get(pt.u).add(pt.v);
adgeList.get(pt.v).add(pt.u);
result += pt.weight;
System.out.print(" (" + pt.u + ", " + pt.v + ") \n");
}
pt = pt.n;
}
System.out.println("Calculated total weight of MST " + result);
}
public static void main(String[] args)
{
grp g = new grp(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);
g.printgrp();
g.rev_dlt_MST();
}
}C++ Code
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Edge
{
public:
int w;
int u;
int v;
Edge *n;
Edge(int w, int u, int v)
{
this->w = w;
this->u = u;
this->v = v;
this->n = NULL;
}
};
class Graph
{
public: int ver;
vector <vector<int> > adgeList;
Edge *edges;
int edgecounter;
Graph(int ver)
{
this->ver = ver;
this->edges = NULL;
this->edgecounter = 0;
for(int i = 0 ; i < ver; ++i)
{
this->adgeList.push_back(vector<int>());
}
}
void adding_edge(int u, int v, int w)
{
if (u < 0 || u >= this->ver || v < 0 || v >= this->ver)
{
return;
}
this->adgeList.at(u).push_back(v);
this->adgeList.at(v).push_back(u);
Edge *e = new Edge(w, u, v);
if (this->edges == NULL)
{
this->edges = e;
}
else if (this->edges->w <= e->w)
{
e->n = this->edges;
this->edges = e;
}
else
{
Edge *temp = this->edges;
while (temp->n != NULL && temp->n->w > e->w)
{
temp = temp->n;
}
e->n = temp->n;
temp->n = e;
}
this->edgecounter = this->edgecounter + 1;
}
void DFS(int v, bool reached[])
{
reached[v] = true;
for (int i = 0; i < this->adgeList.at(v).size(); i++)
{
if (reached[this->adgeList.at(v).at(i)] == false)
{
this->DFS(this->adgeList.at(v).at(i), reached);
}
}
}
bool connected()
{
bool reached[this->ver];
for (int i = 0; i < this->ver; ++i)
{
reached[i] = false;
}
this->DFS(0, reached);
for (int i = 1; i < this->ver; i++)
{
if (reached[i] == false)
{
return false;
}
}
return true;
}
void prnt_Graph()
{
cout << "\n Graph Adjacency List ";
for (int i = 0; i < this->ver; ++i)
{
cout << " \n [" << i << "] :";
for (int j = 0; j < this->adgeList.at(i).size(); j++)
{
cout << " " << this->adgeList.at(i).at(j);
}
}
}
void rev_dlt_MST()
{
int result = 0;
Edge *pt = this->edges;
cout << "\n\nConnected node by Edges in MST" << endl;
while (pt != NULL)
{
this->adgeList.at(pt->u).erase(remove(this->adgeList.at(pt->u).begin(), this->adgeList.at(pt->u).end(), pt->v), this->adgeList.at(pt->u).end());
this->adgeList.at(pt->v).erase(remove(this->adgeList.at(pt->v).begin(), this->adgeList.at(pt->v).end(), pt->u), this->adgeList.at(pt->v).end());
if (this->connected() == false)
{
this->adgeList.at(pt->u).push_back(pt->v);
this->adgeList.at(pt->v).push_back(pt->u);
result += pt->w;
cout << " (" << pt->u << ", " << pt->v << ") \n";
}
pt = pt->n;
}
cout << "Calculated total w of MST is " << result << endl;
}
};
int main()
{
Graph *g = new Graph(8);
g->adding_edge(0, 1, 5);
g->adding_edge(0, 3, 3);
g->adding_edge(1, 2, 3);
g->adding_edge(1, 6, 7);
g->adding_edge(1, 7, 9);
g->adding_edge(2, 5, 9);
g->adding_edge(2, 7, 4);
g->adding_edge(3, 4, 11);
g->adding_edge(3, 7, 8);
g->adding_edge(4, 5, 8);
g->adding_edge(4, 6, 14);
g->adding_edge(4, 7, 10);
g->adding_edge(5, 6, 11);
g->prnt_Graph();
g->rev_dlt_MST();
return 0;
}
Python Code
class Edge :
def __init__(self, w, u, v) :
self.w = w
self.u = u
self.v = v
self.next = None
class Group :
def __init__(self, ver) :
self.ver = ver
self.adgeList = []
self.edges = None
self.edgecounter = 0
i = 0
while (i < self.ver) :
self.adgeList.append([])
i += 1
def adding__edge(self, u, v, w) :
if (u < 0 or u >= self.ver or v < 0 or v >= self.ver) :
return
self.adgeList[u].append(v)
self.adgeList[v].append(u)
e = Edge(w, u, v)
if (self.edges == None) :
self.edges = e
elif (self.edges.w <= e.w) :
e.next = self.edges
self.edges = e
else :
temp = self.edges
while (temp.next != None and temp.next.w > e.w) :
temp = temp.next
e.next = temp.next
temp.next = e
self.edgecounter = self.edgecounter + 1
def DFS(self, v, reached) :
reached[v] = True
i = 0
while (i < len(self.adgeList[v])) :
if (reached[self.adgeList[v][i]] == False) :
self.DFS(self.adgeList[v][i], reached)
i += 1
def connected(self) :
reached = [False] * (self.ver)
i = 0
while (i < self.ver) :
reached[i] = False
i += 1
self.DFS(0, reached)
i = 1
while (i < self.ver) :
if (reached[i] == False) :
return False
i += 1
return True
def prnt_Group(self) :
print("\n Group Adjacency List ", end = "")
i = 0
while (i < self.ver) :
print(" \n [", i ,"] :", end = "")
j = 0
while (j < len(self.adgeList[i])) :
print(" ", self.adgeList[i][j], end = "")
j += 1
i += 1
def rev_dlt_MST(self) :
result = 0
point = self.edges
print("\n\nConnected node in MST by edges")
while (point != None) :
self.adgeList[point.u].remove(point.v)
self.adgeList[point.v].remove(point.u)
if (self.connected() == False) :
self.adgeList[point.u].append(point.v)
self.adgeList[point.v].append(point.u)
result += point.w
print(" (", point.u ,", ", point.v ,") ")
point = point.next
print("Calculated total w of MST is ", result)
def main() :
g = Group(8)
g.adding__edge(0, 1, 5)
g.adding__edge(0, 3, 3)
g.adding__edge(1, 2, 3)
g.adding__edge(1, 6, 7)
g.adding__edge(1, 7, 9)
g.adding__edge(2, 5, 9)
g.adding__edge(2, 7, 4)
g.adding__edge(3, 4, 11)
g.adding__edge(3, 7, 8)
g.adding__edge(4, 5, 8)
g.adding__edge(4, 6, 14)
g.adding__edge(4, 7, 10)
g.adding__edge(5, 6, 11)
g.prnt_Group()
g.rev_dlt_MST()
if __name__ == "__main__": main()
Output
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 39Complexities
- Time Complexity: O(E logV (log logV)3)
Using big-O notation, the time complexity is O(E logV (log logV)3), where E is the number of edges present and V is the number of vertices.
- Space Complexity: O(V+E)
Frequently asked questions
How does Kruskal's Algorithm work?
The Kruskal algorithm arranges all the edges according to rising edge weights and only keeps adding nodes to the tree if the selected edge does not constitute a cycle.
What is the complexity of the Kruskal algorithm?
The time complexity of the Kruskal algorithm is O(E log V), where V is the number of vertices.
Is the Kruskal algorithm greedy?
In the graph theory, it is known as a greedy method since it continuously adds the next lowest-weight edge that won't cycle to the minimal spanning forest.
Why do we use the Prim Algorithm?
The minimal spanning tree from a graph is found using Prim's Approach, a greedy algorithm.
Why Prims and Kruskal Cannot be applied on directed graphs?
All vertices are presumed to be connected in Prim's Algorithm. However, every node in a directed graph cannot be reached from every other node. Due to this, Prim's Algorithm is flawed.
Conclusion
To conclude this blog, here we discussed the Reverse Delete Algorithm, examples, and code. We also Algorithm. In the end, we saw the time complexities.
For more content, Refer to our guided paths on Coding Ninjas Studio to upskill yourself. If you want to explore more, feel free to see our courses, interview experiences, problems to solve, test series, libraries, and resources.
Do upvote our blogs if you find them helpful and engaging!
