OMGEKEERD VERWIJDERALGORITME VOOR MINIMAAL OVERSPANNENDE BOOM

Probeer het eens op GfG Practice Omgekeerd verwijderalgoritme voor minimaal overspannende boom

#practiceLinkDiv {weergave: geen! belangrijk; }

Het Reverse Delete-algoritme is nauw verwant aan Het algoritme van Kruskal . In het algoritme van Kruskal is wat we doen: randen sorteren op toenemende volgorde van hun gewicht. Na het sorteren pakken we de randen één voor één in oplopende volgorde. We nemen de huidige gekozen rand op als we deze in de opspannende boom opnemen en er geen enkele cyclus ontstaat totdat er V-1-randen in de opspannende boom zijn waarbij V = aantal hoekpunten.

In het Reverse Delete-algoritme sorteren we alle randen afnemend volgorde van hun gewichten. Na het sorteren pakken we de randen één voor één in afnemende volgorde. Wij neem de huidige gekozen rand op als het uitsluiten van de huidige rand de verbinding in de huidige grafiek verbreekt . Het hoofdidee is het verwijderen van de rand als het verwijderen ervan niet leidt tot het ontkoppelen van de grafiek.

Het algoritme:

Sorteer alle randen van de grafiek in niet-oplopende volgorde van randgewichten.

Initialiseer MST als originele grafiek en verwijder extra randen met stap 3.

Kies de hoogste gewichtsrand van de resterende randen en controleer of het verwijderen van de rand de verbinding met de grafiek verbreekt of niet .
Als de verbinding wordt verbroken, verwijderen we de rand niet.
Anders verwijderen we de rand en gaan verder.

Illustratie:

Laten we het begrijpen met het volgende voorbeeld:

omgekeerd verwijderen2

Als we de hoogste gewichtsrand van gewicht 14 verwijderen, wordt de grafiek niet losgekoppeld, dus verwijderen we deze.

omgekeerd verwijderen3

Vervolgens verwijderen we 11, omdat het verwijderen ervan de grafiek niet ontkoppelt.

omgekeerd verwijderen4

Vervolgens verwijderen we 10, omdat het verwijderen ervan de grafiek niet ontkoppelt.

omgekeerd verwijderen5

Het volgende is 9. We kunnen 9 niet verwijderen, omdat het verwijderen ervan de verbinding verbreekt.

We gaan op deze manier verder en de volgende randen blijven in de uiteindelijke MST.

 Edges in MST   
 (3 4)    
 (0 7)    
 (2 3)    
 (2 5)    
 (0 1)    
 (5 6)    
 (2 8)    
 (6 7)    
     Opmerking :    In het geval van randen met hetzelfde gewicht kunnen we elke rand met randen met hetzelfde gewicht kiezen.  
Aanbevolen praktijk Omgekeerd verwijderalgoritme voor minimaal overspannende boom    Probeer het!       Uitvoering:    
 C++      // C++ program to find Minimum Spanning Tree   // of a graph using Reverse Delete Algorithm   #include       using     namespace     std  ;   // Creating shortcut for an integer pair   typedef     pair   <  int       int  >     iPair  ;   // Graph class represents a directed graph   // using adjacency list representation   class     Graph   {      int     V  ;     // No. of vertices      list   <  int  >     *  adj  ;      vector   <     pair   <  int       iPair  >     >     edges  ;      void     DFS  (  int     v       bool     visited  []);   public  :      Graph  (  int     V  );     // Constructor      // function to add an edge to graph      void     addEdge  (  int     u       int     v       int     w  );      // Returns true if graph is connected      bool     isConnected  ();      void     reverseDeleteMST  ();   };   Graph  ::  Graph  (  int     V  )   {      this  ->  V     =     V  ;      adj     =     new     list   <  int  >  [  V  ];   }   void     Graph  ::  addEdge  (  int     u       int     v       int     w  )   {      adj  [  u  ].  push_back  (  v  );     // Add w to v’s list.      adj  [  v  ].  push_back  (  u  );     // Add w to v’s list.      edges  .  push_back  ({  w       {  u       v  }});   }   void     Graph  ::  DFS  (  int     v       bool     visited  [])   {      // Mark the current node as visited and print it      visited  [  v  ]     =     true  ;      // Recur for all the vertices adjacent to      // this vertex      list   <  int  >::  iterator     i  ;      for     (  i     =     adj  [  v  ].  begin  ();     i     !=     adj  [  v  ].  end  ();     ++  i  )      if     (  !  visited  [  *  i  ])      DFS  (  *  i       visited  );   }   // Returns true if given graph is connected else false   bool     Graph  ::  isConnected  ()   {      bool     visited  [  V  ];      memset  (  visited       false       sizeof  (  visited  ));      // Find all reachable vertices from first vertex      DFS  (  0       visited  );      // If set of reachable vertices includes all      // return true.      for     (  int     i  =  1  ;     i   <  V  ;     i  ++  )      if     (  visited  [  i  ]     ==     false  )      return     false  ;      return     true  ;   }   // This function assumes that edge (u v)   // exists in graph or not   void     Graph  ::  reverseDeleteMST  ()   {      // Sort edges in increasing order on basis of cost      sort  (  edges  .  begin  ()     edges  .  end  ());      int     mst_wt     =     0  ;     // Initialize weight of MST      cout      < <     'Edges in MST  n  '  ;      // Iterate through all sorted edges in      // decreasing order of weights      for     (  int     i  =  edges  .  size  ()  -1  ;     i  >=  0  ;     i  --  )      {      int     u     =     edges  [  i  ].  second  .  first  ;      int     v     =     edges  [  i  ].  second  .  second  ;      // Remove edge from undirected graph      adj  [  u  ].  remove  (  v  );      adj  [  v  ].  remove  (  u  );      // Adding the edge back if removing it      // causes disconnection. In this case this       // edge becomes part of MST.      if     (  isConnected  ()     ==     false  )      {      adj  [  u  ].  push_back  (  v  );      adj  [  v  ].  push_back  (  u  );      // This edge is part of MST      cout      < <     '('      < <     u      < <     ' '      < <     v      < <     ')   n  '  ;      mst_wt     +=     edges  [  i  ].  first  ;      }      }      cout      < <     'Total weight of MST is '      < <     mst_wt  ;   }   // Driver code   int     main  ()   {      // create the graph given in above figure      int     V     =     9  ;      Graph     g  (  V  );      // making above shown graph      g  .  addEdge  (  0       1       4  );      g  .  addEdge  (  0       7       8  );      g  .  addEdge  (  1       2       8  );      g  .  addEdge  (  1       7       11  );      g  .  addEdge  (  2       3       7  );      g  .  addEdge  (  2       8       2  );      g  .  addEdge  (  2       5       4  );      g  .  addEdge  (  3       4       9  );      g  .  addEdge  (  3       5       14  );      g  .  addEdge  (  4       5       10  );      g  .  addEdge  (  5       6       2  );      g  .  addEdge  (  6       7       1  );      g  .  addEdge  (  6       8       6  );      g  .  addEdge  (  7       8       7  );      g  .  reverseDeleteMST  ();      return     0  ;   }   
  Java      // Java program to find Minimum Spanning Tree   // of a graph using Reverse Delete Algorithm   import     java.util.*  ;   // class to represent an edge   class   Edge     implements     Comparable   <  Edge  >     {      int     u       v       w  ;      Edge  (  int     u       int     v       int     w  )      {      this  .  u     =     u  ;      this  .  w     =     w  ;      this  .  v     =     v  ;      }      public     int     compareTo  (  Edge     other  )      {      return     (  this  .  w     -     other  .  w  );      }   }   // Class to represent a graph using adjacency list   // representation   public     class   GFG     {      private     int     V  ;     // No. of vertices      private     List   <  Integer  >[]     adj  ;      private     List   <  Edge  >     edges  ;      @SuppressWarnings  ({     'unchecked'       'deprecated'     })      public     GFG  (  int     v  )     // Constructor      {      V     =     v  ;      adj     =     new     ArrayList  [  v  ]  ;      for     (  int     i     =     0  ;     i      <     v  ;     i  ++  )      adj  [  i  ]     =     new     ArrayList   <  Integer  >  ();      edges     =     new     ArrayList   <  Edge  >  ();      }      // function to Add an edge      public     void     AddEdge  (  int     u       int     v       int     w  )      {      adj  [  u  ]  .  add  (  v  );     // Add w to v’s list.      adj  [  v  ]  .  add  (  u  );     // Add w to v’s list.      edges  .  add  (  new     Edge  (  u       v       w  ));      }      // function to perform dfs      private     void     DFS  (  int     v       boolean  []     visited  )      {      // Mark the current node as visited and print it      visited  [  v  ]     =     true  ;      // Recur for all the vertices adjacent to      // this vertex      for     (  int     i     :     adj  [  v  ]  )     {      if     (  !  visited  [  i  ]  )      DFS  (  i       visited  );      }      }      // Returns true if given graph is connected else false      private     boolean     IsConnected  ()      {      boolean  []     visited     =     new     boolean  [  V  ]  ;      // Find all reachable vertices from first vertex      DFS  (  0       visited  );      // If set of reachable vertices includes all      // return true.      for     (  int     i     =     1  ;     i      <     V  ;     i  ++  )     {      if     (  visited  [  i  ]     ==     false  )      return     false  ;      }      return     true  ;      }      // This function assumes that edge (u v)      // exists in graph or not      public     void     ReverseDeleteMST  ()      {      // Sort edges in increasing order on basis of cost      Collections  .  sort  (  edges  );      int     mst_wt     =     0  ;     // Initialize weight of MST      System  .  out  .  println  (  'Edges in MST'  );      // Iterate through all sorted edges in      // decreasing order of weights      for     (  int     i     =     edges  .  size  ()     -     1  ;     i     >=     0  ;     i  --  )     {      int     u     =     edges  .  get  (  i  ).  u  ;      int     v     =     edges  .  get  (  i  ).  v  ;      // Remove edge from undirected graph      adj  [  u  ]  .  remove  (  adj  [  u  ]  .  indexOf  (  v  ));      adj  [  v  ]  .  remove  (  adj  [  v  ]  .  indexOf  (  u  ));      // Adding the edge back if removing it      // causes disconnection. In this case this      // edge becomes part of MST.      if     (  IsConnected  ()     ==     false  )     {      adj  [  u  ]  .  add  (  v  );      adj  [  v  ]  .  add  (  u  );      // This edge is part of MST      System  .  out  .  println  (  '('     +     u     +     ' '     +     v      +     ')'  );      mst_wt     +=     edges  .  get  (  i  ).  w  ;      }      }      System  .  out  .  println  (  'Total weight of MST is '      +     mst_wt  );      }      // Driver code      public     static     void     main  (  String  []     args  )      {      // create the graph given in above figure      int     V     =     9  ;      GFG     g     =     new     GFG  (  V  );      // making above shown graph      g  .  AddEdge  (  0       1       4  );      g  .  AddEdge  (  0       7       8  );      g  .  AddEdge  (  1       2       8  );      g  .  AddEdge  (  1       7       11  );      g  .  AddEdge  (  2       3       7  );      g  .  AddEdge  (  2       8       2  );      g  .  AddEdge  (  2       5       4  );      g  .  AddEdge  (  3       4       9  );      g  .  AddEdge  (  3       5       14  );      g  .  AddEdge  (  4       5       10  );      g  .  AddEdge  (  5       6       2  );      g  .  AddEdge  (  6       7       1  );      g  .  AddEdge  (  6       8       6  );      g  .  AddEdge  (  7       8       7  );      g  .  ReverseDeleteMST  ();      }   }   // This code is contributed by Prithi_Dey   
  Python3      # Python3 program to find Minimum Spanning Tree   # of a graph using Reverse Delete Algorithm   # Graph class represents a directed graph   # using adjacency list representation   class   Graph  :   def   __init__  (  self     v  ):   # No. of vertices   self  .  v   =   v   self  .  adj   =   [  0  ]   *   v   self  .  edges   =   []   for   i   in   range  (  v  ):   self  .  adj  [  i  ]   =   []   # function to add an edge to graph   def   addEdge  (  self     u  :   int     v  :   int     w  :   int  ):   self  .  adj  [  u  ]  .  append  (  v  )   # Add w to v’s list.   self  .  adj  [  v  ]  .  append  (  u  )   # Add w to v’s list.   self  .  edges  .  append  ((  w     (  u     v  )))   def   dfs  (  self     v  :   int     visited  :   list  ):   # Mark the current node as visited and print it   visited  [  v  ]   =   True   # Recur for all the vertices adjacent to   # this vertex   for   i   in   self  .  adj  [  v  ]:   if   not   visited  [  i  ]:   self  .  dfs  (  i     visited  )   # Returns true if graph is connected   # Returns true if given graph is connected else false   def   connected  (  self  ):   visited   =   [  False  ]   *   self  .  v   # Find all reachable vertices from first vertex   self  .  dfs  (  0     visited  )   # If set of reachable vertices includes all   # return true.   for   i   in   range  (  1     self  .  v  ):   if   not   visited  [  i  ]:   return   False   return   True   # This function assumes that edge (u v)   # exists in graph or not   def   reverseDeleteMST  (  self  ):   # Sort edges in increasing order on basis of cost   self  .  edges  .  sort  (  key   =   lambda   a  :   a  [  0  ])   mst_wt   =   0   # Initialize weight of MST   print  (  'Edges in MST'  )   # Iterate through all sorted edges in   # decreasing order of weights   for   i   in   range  (  len  (  self  .  edges  )   -   1     -  1     -  1  ):   u   =   self  .  edges  [  i  ][  1  ][  0  ]   v   =   self  .  edges  [  i  ][  1  ][  1  ]   # Remove edge from undirected graph   self  .  adj  [  u  ]  .  remove  (  v  )   self  .  adj  [  v  ]  .  remove  (  u  )   # Adding the edge back if removing it   # causes disconnection. In this case this   # edge becomes part of MST.   if   self  .  connected  ()   ==   False  :   self  .  adj  [  u  ]  .  append  (  v  )   self  .  adj  [  v  ]  .  append  (  u  )   # This edge is part of MST   print  (  '(   %d     %d   )'   %   (  u     v  ))   mst_wt   +=   self  .  edges  [  i  ][  0  ]   print  (  'Total weight of MST is'     mst_wt  )   # Driver Code   if   __name__   ==   '__main__'  :   # create the graph given in above figure   V   =   9   g   =   Graph  (  V  )   # making above shown graph   g  .  addEdge  (  0     1     4  )   g  .  addEdge  (  0     7     8  )   g  .  addEdge  (  1     2     8  )   g  .  addEdge  (  1     7     11  )   g  .  addEdge  (  2     3     7  )   g  .  addEdge  (  2     8     2  )   g  .  addEdge  (  2     5     4  )   g  .  addEdge  (  3     4     9  )   g  .  addEdge  (  3     5     14  )   g  .  addEdge  (  4     5     10  )   g  .  addEdge  (  5     6     2  )   g  .  addEdge  (  6     7     1  )   g  .  addEdge  (  6     8     6  )   g  .  addEdge  (  7     8     7  )   g  .  reverseDeleteMST  ()   # This code is contributed by   # sanjeev2552   
  C#      // C# program to find Minimum Spanning Tree   // of a graph using Reverse Delete Algorithm   using     System  ;   using     System.Collections.Generic  ;   // class to represent an edge   public     class     Edge     :     IComparable   <  Edge  >     {      public     int     u       v       w  ;      public     Edge  (  int     u       int     v       int     w  )      {      this  .  u     =     u  ;      this  .  v     =     v  ;      this  .  w     =     w  ;      }      public     int     CompareTo  (  Edge     other  )      {      return     this  .  w  .  CompareTo  (  other  .  w  );      }   }   // Graph class represents a directed graph   // using adjacency list representation   public     class     Graph     {      private     int     V  ;     // No. of vertices      private     List   <  int  >  []     adj  ;      private     List   <  Edge  >     edges  ;      public     Graph  (  int     v  )     // Constructor      {      V     =     v  ;      adj     =     new     List   <  int  >  [     v     ];      for     (  int     i     =     0  ;     i      <     v  ;     i  ++  )      adj  [  i  ]     =     new     List   <  int  >  ();      edges     =     new     List   <  Edge  >  ();      }      // function to Add an edge      public     void     AddEdge  (  int     u       int     v       int     w  )      {      adj  [  u  ].  Add  (  v  );     // Add w to v’s list.      adj  [  v  ].  Add  (  u  );     // Add w to v’s list.      edges  .  Add  (  new     Edge  (  u       v       w  ));      }      // function to perform dfs      private     void     DFS  (  int     v       bool  []     visited  )      {      // Mark the current node as visited and print it      visited  [  v  ]     =     true  ;      // Recur for all the vertices adjacent to      // this vertex      foreach  (  int     i     in     adj  [  v  ])      {      if     (  !  visited  [  i  ])      DFS  (  i       visited  );      }      }      // Returns true if given graph is connected else false      private     bool     IsConnected  ()      {      bool  []     visited     =     new     bool  [  V  ];      // Find all reachable vertices from first vertex      DFS  (  0       visited  );      // If set of reachable vertices includes all      // return true.      for     (  int     i     =     1  ;     i      <     V  ;     i  ++  )     {      if     (  visited  [  i  ]     ==     false  )      return     false  ;      }      return     true  ;      }      // This function assumes that edge (u v)      // exists in graph or not      public     void     ReverseDeleteMST  ()      {      // Sort edges in increasing order on basis of cost      edges  .  Sort  ();      int     mst_wt     =     0  ;     // Initialize weight of MST      Console  .  WriteLine  (  'Edges in MST'  );      // Iterate through all sorted edges in      // decreasing order of weights      for     (  int     i     =     edges  .  Count     -     1  ;     i     >=     0  ;     i  --  )     {      int     u     =     edges  [  i  ].  u  ;      int     v     =     edges  [  i  ].  v  ;      // Remove edge from undirected graph      adj  [  u  ].  Remove  (  v  );      adj  [  v  ].  Remove  (  u  );      // Adding the edge back if removing it      // causes disconnection. In this case this      // edge becomes part of MST.      if     (  IsConnected  ()     ==     false  )     {      adj  [  u  ].  Add  (  v  );      adj  [  v  ].  Add  (  u  );      // This edge is part of MST      Console  .  WriteLine  (  '({0} {1})'       u       v  );      mst_wt     +=     edges  [  i  ].  w  ;      }      }      Console  .  WriteLine  (  'Total weight of MST is {0}'        mst_wt  );      }   }   class     GFG     {      // Driver code      static     void     Main  (  string  []     args  )      {      // create the graph given in above figure      int     V     =     9  ;      Graph     g     =     new     Graph  (  V  );      // making above shown graph      g  .  AddEdge  (  0       1       4  );      g  .  AddEdge  (  0       7       8  );      g  .  AddEdge  (  1       2       8  );      g  .  AddEdge  (  1       7       11  );      g  .  AddEdge  (  2       3       7  );      g  .  AddEdge  (  2       8       2  );      g  .  AddEdge  (  2       5       4  );      g  .  AddEdge  (  3       4       9  );      g  .  AddEdge  (  3       5       14  );      g  .  AddEdge  (  4       5       10  );      g  .  AddEdge  (  5       6       2  );      g  .  AddEdge  (  6       7       1  );      g  .  AddEdge  (  6       8       6  );      g  .  AddEdge  (  7       8       7  );      g  .  ReverseDeleteMST  ();      }   }   // This code is contributed by cavi4762   
  JavaScript      // Javascript program to find Minimum Spanning Tree   // of a graph using Reverse Delete Algorithm   // Graph class represents a directed graph   // using adjacency list representation   class     Graph     {      // Constructor      constructor  (  V  )     {      this  .  V     =     V  ;      this  .  adj     =     [];      this  .  edges     =     [];      for     (  let     i     =     0  ;     i      <     V  ;     i  ++  )     {      this  .  adj  [  i  ]     =     [];      }      }          // function to add an edge to graph      addEdge  (  u       v       w  )     {      this  .  adj  [  u  ].  push  (  v  );  // Add w to v’s list.      this  .  adj  [  v  ].  push  (  u  );  // Add w to v’s list.      this  .  edges  .  push  ([  w       [  u       v  ]]);      }      DFS  (  v       visited  )     {      // Mark the current node as visited and print it      visited  [  v  ]     =     true  ;      for     (  const     i     of     this  .  adj  [  v  ])     {      if     (  !  visited  [  i  ])     {      this  .  DFS  (  i       visited  );      }      }      }      // Returns true if given graph is connected else false      isConnected  ()     {      const     visited     =     [];      for     (  let     i     =     0  ;     i      <     this  .  V  ;     i  ++  )     {      visited  [  i  ]     =     false  ;      }          // Find all reachable vertices from first vertex      this  .  DFS  (  0       visited  );          // If set of reachable vertices includes all      // return true.      for     (  let     i     =     1  ;     i      <     this  .  V  ;     i  ++  )     {      if     (  !  visited  [  i  ])     {      return     false  ;      }      }      return     true  ;      }      // This function assumes that edge (u v)      // exists in graph or not      reverseDeleteMST  ()     {          // Sort edges in increasing order on basis of cost      this  .  edges  .  sort  ((  a       b  )     =>     a  [  0  ]     -     b  [  0  ]);          let     mstWt     =     0  ;  // Initialize weight of MST          console  .  log  (  'Edges in MST'  );          // Iterate through all sorted edges in      // decreasing order of weights      for     (  let     i     =     this  .  edges  .  length     -     1  ;     i     >=     0  ;     i  --  )     {      const     [  u       v  ]     =     this  .  edges  [  i  ][  1  ];          // Remove edge from undirected graph      this  .  adj  [  u  ]     =     this  .  adj  [  u  ].  filter  (  x     =>     x     !==     v  );      this  .  adj  [  v  ]     =     this  .  adj  [  v  ].  filter  (  x     =>     x     !==     u  );          // Adding the edge back if removing it      // causes disconnection. In this case this       // edge becomes part of MST.      if     (  !  this  .  isConnected  ())     {      this  .  adj  [  u  ].  push  (  v  );      this  .  adj  [  v  ].  push  (  u  );          // This edge is part of MST      console  .  log  (  `(  ${  u  }     ${  v  }  )`  );      mstWt     +=     this  .  edges  [  i  ][  0  ];      }      }      console  .  log  (  `Total weight of MST is   ${  mstWt  }  `  );      }   }   // Driver code   function     main  ()   {      // create the graph given in above figure      var     V     =     9  ;      var     g     =     new     Graph  (  V  );      // making above shown graph      g  .  addEdge  (  0       1       4  );      g  .  addEdge  (  0       7       8  );      g  .  addEdge  (  1       2       8  );      g  .  addEdge  (  1       7       11  );      g  .  addEdge  (  2       3       7  );      g  .  addEdge  (  2       8       2  );      g  .  addEdge  (  2       5       4  );      g  .  addEdge  (  3       4       9  );      g  .  addEdge  (  3       5       14  );      g  .  addEdge  (  4       5       10  );      g  .  addEdge  (  5       6       2  );      g  .  addEdge  (  6       7       1  );      g  .  addEdge  (  6       8       6  );      g  .  addEdge  (  7       8       7  );      g  .  reverseDeleteMST  ();   }   main  ();   
    
  Uitvoer   Edges in MST (3 4) (0 7) (2 3) (2 5) (0 1) (5 6) (2 8) (6 7) Total weight of MST is 37  
     Tijdcomplexiteit: O((E*(V+E)) + E log E)    waarbij E het aantal randen is.  
      Ruimtecomplexiteit: O(V+E)    waarbij V het aantal hoekpunten is en E het aantal randen. We gebruiken de aangrenzende lijst om de grafiek op te slaan, dus we hebben een ruimte nodig die evenredig is met O(V+E).  
      Opmerkingen:     
    De bovenstaande implementatie is een eenvoudige/naïeve implementatie van het Reverse Delete-algoritme en kan worden geoptimaliseerd tot O(E log V (log log V)  ³ ) [Bron :    Een week    ]. Maar deze geoptimaliseerde tijdscomplexiteit is nog steeds minder dan    Prim    En    Kruskal    Algoritmen voor MST.  
  De bovenstaande implementatie wijzigt de originele grafiek. We kunnen een kopie van de grafiek maken als de originele grafiek behouden moet blijven.  
 
     
         Quiz maken