Skip to content

Greedy Algorithm to find a minimum spanning tree in an undirected graph by deleting heaviest edges unless it would disconnect the graph

Notifications You must be signed in to change notification settings

SleekPanther/reverse-delete-algorithm

Folders and files

NameName
Last commit message
Last commit date

Latest commit

fc70d06 · Aug 9, 2017

History

7 Commits
Aug 9, 2017
Aug 8, 2017
Aug 8, 2017
Aug 8, 2017
Aug 9, 2017
Aug 9, 2017

Repository files navigation

Reverse Delete Algorithm (Minimum Spanning Tree)

Greedy Algorithm to find a minimum spanning tree in an undirected graph by deleting heaviest edges unless it would disconnect the graph

Problem Statement

Minim Spanning Tree: a subset of nodes that touches all vertices while keeping all nodes connected and uses the sum of the edge weights in a minimum
A Minimum spanning tree yields a graph with M-1 edges because adding 1 more edge would by definition create a cycle

Graph

Minimum Spanning Tree

Weight = 18+14+9+7+6+5+2 = 61

Reverse Delete Greedy Strategy

Start with all edges in the tree T. Consider edges in descending order of weight. Delete edge from T unless doing so would disconnect T

  • Sort edges by weight
  • Initialize MST with all edges
  • Delete the highest weight edge
    • If deleting the edge disconnects the graph, add it back
    • Otherwise continue

Usage

  • Node names are consecutive integers starting from 0
  • Create a graph: ArrayList<Edge> graph = new ArrayList<Edge>();
  • Graph undirected edge list, but only add each edge once
    • In the graph there is an edge from 0 to 9 with weight=9
    • This bidirectional edge can just be represented once: graph.add(new Edge(0, 1, 9));
  • Count the vertices in the graph: int vertexCount = 8;
  • Call the static method ReverseDeleteMST.findMST(graph, vertexCount);

Code Notes

  • Due to the implementation of Breadth First Search, the code creates an additional copy of the graph as an adjacency list
  • This adjacency list graph is the one where edges are deleted, the original input graph as an edge list is left in tact
  • The MST is technically built up from nothing and added to if deleting an edge in the adjacency list would disconnect the graph

References