Reverse Delete Algorithm

Q: What is the complexity of the Kruskal algorithm?

The time complexity of Kruskal algorithm is O(E log V), where V is the number of vertices.

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.

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();
  }
}

You can also try this code with Online Java Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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()

You can also try this code with Online Python Compiler

Run Code

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)³)

Using big-O notation, the time complexity is O(E logV (log logV)³), 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.