Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Reverse Delete Algorithm
2.1.
Example
3.
Code
3.1.
Java Code
3.2.
C++ Code
3.3.
Python Code
3.4.
Output
4.
Complexities
5.
Frequently asked questions
5.1.
How does Kruskal's Algorithm work?
5.2.
What is the complexity of the Kruskal algorithm?
5.3.
Is the Kruskal algorithm greedy?
5.4.
Why do we use the Prim Algorithm?
5.5.
Why Prims and Kruskal Cannot be applied on directed graphs?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Reverse Delete Algorithm

Author Muskan Sharma
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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

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.
Example Image

 

  • This graph's minimum spanning tree is:
Example Image

 

  • Let's use the graph to perform the Reverse Delete Algorithm:

 

Example Image

 

  • 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.
Example Image
  • 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.
Example Image
  • 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.
Example Image
  • 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.
Example Image
  • 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.
Example Image
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 39

Complexities

  • 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 coursesinterview experiences, problems to solvetest serieslibraries, and resources

Thank You

Do upvote our blogs if you find them helpful and engaging!

Previous article
Number of loops of size k starting from a specific node
Next article
Understanding the Snake and Ladder problem
Live masterclass