Skip to main content

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:

Example Reverse delete algorithm minimum spanning tree

  1. Start with the full graph, including all edges and vertices.

  2. Sort the edges in decreasing order of weight (from the largest to the smallest).

  3. 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.

  4. Stop when all edges have been checked, or when the graph has become disconnected.

  5. 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
Last updated on by Kalkicode




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.

New Comment